Two Sum || Array Sorted

PROBLEM

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1<=index1<index2<=numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1

*Input*: numbers = [2,7,11,15], target = 9
*Output*: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2

*Input*: numbers = [2,3,4], target = 6
*Output*: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3

*Input*: numbers = [-1,0], target = -1
*Output*: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints

• 2<=numbers.length<=3*104
• -1000<=numbers[i]<=1000
• numbers is sorted in non-decreasing order.
• -1000<=target<=1000
• The tests are generated such that there is exactly one solution.

SOLVING

We’ll use the Two Pointers method.

First Approach

Steps

• Left Pointer to 0 and Right Pointer to Left+1
• Get a tmp target equal to Nums[LeftPointer] - Target
• Move Right Pointer to the end of array:
  • If Nums[RightPointer]==tmp_target return Left and Right Pointer
  • If Nums[RightPointer] > tmp_target break loop, increase LeftPointer and RightPointer equal Left + 1 | We break because the other number will be bigger and so not the answer

Code

class Solution {
public:
  vector<int> twoSum(vector<int> &numbers, int target) {
    int size = numbers.size();

    for (int leftPtr = 0; leftPtr <= size - 2; leftPtr++) {
      int tmp_target = target - numbers[leftPtr];
      for (int rightPtr = leftPtr + 1; rightPtr < size; rightPtr++) {
	std::cout << leftPtr << " " << rightPtr << " " << target << std::endl;
	if (numbers[rightPtr] == tmp_target)
	  return {leftPtr + 1, rightPtr + 1};
	else if (numbers[rightPtr] > tmp_target)
	  break;
      }
    }
    return {0, 0};
  }
};

Conclusion

It Works !! BUT for LeetCode it’s a Time Exceeded for the largest test :(

Second Approach

Steps

• LeftPointer to the first element and RightPointer to the last element
• Loop until Left and Right Pointer cross each other:
  • If the sum of Nums[LeftPointer] and Nums[RightPointer] is equal to target, return the pointers;
  • If the sum is inferior, increase the Left Pointer
  • Otherwise increase the RightPointer

• Example

  Target = 9

   L             R
   ↓             ↓
  [1, 2, 7, 11, 15]
   1 + 15 = 17 (>9 so decrease RightPointer)
  
   L         R
   ↓         ↓
  [1, 2, 7, 11, 15]
   1 + 11 = 13 (>9 so decrease RightPointer)
  
   L     R
   ↓     ↓
  [1, 2, 7, 11, 15]
   1 + 7 = 8 (<9 so increase the LeftPointer)
  
      L  R
      ↓  ↓
  [1, 2, 7, 11, 15]
   2 + 9 = 9 (=9 so return the pointers)
  

Code

class Solution {
public:
  vector<int> twoSum(vector<int> &numbers, int target) {
    int size = numbers.size();
    int leftPointer = 0;
    int rightPointer = size - 1;

    while (leftPointer < rightPointer) {
      int sum = numbers[leftPointer] + numbers[rightPointer];

      if (sum == target)
	return {leftPointer + 1, rightPointer + 1};
      else if (sum < target)
	leftPointer++;
      else
	rightPointer--;
    }
    return {0, 0};
  }
};

Conclusion

It works too and it’s FASTER

• TWOPOINTERS
• PROBLEM