Leetcode 167. Two Sum II - Input array is sorted

Problem Explanation:

We are given a sorted list of numbers and a target number. The task is to find two numbers from the list that sum up to the target number. We are required to return the indices of these numbers where the index of the smaller number is less than the index of the larger number. Note that the index is not zero-based but starts from 1.

Let's look at an example: Suppose the input list is [2,7,11,15] and the target is 9. The two numbers that add up to 9 are 2 and 7. The indices of 2 and 7 are 1 and 2 respectively. So, the output of this example will be [1,2].

Solution Approach:

The fact that the given list is sorted can be used to solve this problem more efficiently. We can start with two pointers - one at the beginning of the list (left pointer) and one at the end of the list (right pointer). Then, we add the numbers at the locations of the two pointers. If the sum is less than the target, we need to increase the sum, so we increase the left pointer. If the sum is more than the target, we need to decrease the sum, so we decrease the right pointer. We proceed like this until we find two numbers that add up to the target number.

Here's how this approach works for our example:

  • Initially, left pointer is at 2 (index 1) and right pointer is at 15 (index 4). Sum = 2 + 15 = 17. This is more than the target (9), so we decrease the right pointer.
  • Now, left pointer is at 2 (index 1) and right pointer is at 11 (index 3). Sum = 2 + 11 = 13. Again, this is more than the target, so we decrease the right pointer.
  • Now, left pointer is at 2 (index 1) and right pointer is at 7 (index 2). Sum = 2 + 7 = 9. This is equal to the target, so we have found our two numbers. We return their indices [1,2].

Solution:

Python Solution:

1
2python
3class Solution:
4  def twoSum(self, numbers, target):
5    l = 0
6    r = len(numbers) - 1
7
8    while numbers[l] + numbers[r] != target:
9      if numbers[l] + numbers[r] < target:
10        l += 1
11      else:
12        r -= 1
13
14    return [l + 1, r + 1]

Java Solution:

1
2java
3class Solution {
4    public int[] twoSum(int[] numbers, int target) {
5        int l = 0, r = numbers.length - 1;
6        while (numbers[l] + numbers[r] != target) {
7            if (numbers[l] + numbers[r] < target)
8                l++;
9            else
10                r--;
11        }
12        return new int[]{l + 1, r + 1};
13    }
14}

Javascript Solution:

1
2javascript
3var Solution = function() {};
4Solution.prototype.twoSum = function(numbers, target) {
5    let l = 0, r = numbers.length - 1;
6    while (numbers[l] + numbers[r] != target) {
7        if (numbers[l] + numbers[r] < target)
8            l++;
9        else
10            r--;
11    }
12    return [l + 1, r + 1];
13};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<int> twoSum(vector<int>& numbers, int target) {
6        int l = 0;
7        int r = numbers.size() - 1;
8
9        while (numbers[l] + numbers[r] != target)
10          if (numbers[l] + numbers[r] < target)
11            ++l;
12          else
13            --r;
14
15        return {l + 1, r + 1};
16    }
17}

C# Solution:

1
2csharp
3public class Solution {
4    public int[] TwoSum(int[] numbers, int target) {
5        int l = 0, r = numbers.Length - 1;
6        while (numbers[l] + numbers[r] != target) {
7            if (numbers[l] + numbers[r] < target)
8                l++;
9            else
10                r--;
11        }
12        return new int[] {l + 1, r + 1};
13    }
14}

When applied, these codes will quickly locate the two values that, when added together, equal the target number specified. This is achieved by effectively using the sorted nature of the input list to our advantage. Always remember to return the answer in a format that aligns with the problem requirements. In this case, the indices needed to be one-based and ordered from smallest to largest.

Nevertheless, it is important to note that the time complexity of this solution is O(n), where n is the length of the input list. This is because in the worst case scenario, we are iterating through the list once. The space complexity, on the other hand, is O(1) because we are not using any additional space that grows with the input size.

Finally, while the provided solutions should work for most scenarios, always carefully understand the problem's constraints and edge cases. For instance, the problem assumes that there is exactly one solution. If there were no such guarantee, additional checks would be necessary to handle cases where no solution exists. Similarly, the problem explicitly states that the input list is sorted. If it were not sorted, we would need to either sort it first (increasing the time complexity) or use a different approach altogether.

Thus, it is crucial to understand the problem fully before starting to code, and keep in mind the nature of the input, the required output, and the constraints of the problem.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫