Two Sum II - Input Array Is Sorted

Array, Two Pointers

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.

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 and Statements:

• 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.

Questions to Clarify:

• Negative Numbers: Can the input array contain negative numbers? Yes.

• Duplicate Numbers: Can the input array contain duplicate numbers? No.

• Unique Solution: Is it guaranteed that there will always be exactly one solution? Yes.

• Indices Required: Do we need to return the actual indices of the solution numbers, or just the numbers themselves? Actual indices of the solution numbers.

Additional Considerations:

• Array Size: What are the expected size limits for the input array?

• Time and Space Complexity: Are there any specific time or space complexity requirements for the solution? Yes, constant extra space and O(N) time Complexity.

Now, all requirements are clear: we can't use a hash table, and we need to solve this problem with O(N) time complexity. So, the nested loop is also not valid for this problem.

Solutions

As we know, array elements are already in sorted order, and with a sorted array, we can follow the two-pointer approach.

Approach – Two Pointers

---

Initialize two pointers at the beginning and at the end of the array and calculate sum of both pointers value if sum is equal to target number then return both pointers indices otherwise increment/decrement pointers based on sum value.

Steps

1. Initialize two pointers: left at the beginning and right at the end of the array.

2. Iterate while pointers haven't crossed:

   • Calculate the current sum of elements at left and right.

   • If the sum equals the target, return the indices (adding 1 for 1-indexing).

   • If the sum is less than the target, increment left to move towards larger values.

   • If the sum is greater than the target, decrement right to move towards smaller values.

3. If no solution found: Return an empty array.

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {

        int[] result = [0, 0];
        int left = 0;
        int right = nums.Length - 1;

        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum == target)
            {
                result[0] = left + 1; // adding 1 for 1-indexing as input is a 1-indexed array.
                result[1] = right + 1; // adding 1 for 1-indexing as input is a 1-indexed array.
                break;
            }
            else if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }

        return result;
    }

}

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(1)