167. Two Sum II – Input Array Is Sorted· LeetCode Solutions solve Now

Two Sum II - Input Array Is Sorted
Two Sum II – Input Array Is 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 index2added 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.

The process to solve Two Sum II – Input Array Is Sorted problem

  • This problem is one of the popular two-pointer problems. Before solving Two Sum II my suggestion would be to get familiar with its first part Two Sum.
  • Create two variables start and end which will point start of the array and the end of the array respectively.
  • Go in while statement until start is less than end. (i.e. start < end)
  • Create one more variable to store value of sum of start position and end position index.
  • Check if sum is equal to target. If it is return new array. (Make sure to increase 1 value in both start and end index because the question expect us to show the solution in human readable format. (Index start at 0 in computer but for regular human it starts at 0)
  • if sum value is more than target, decrease the end pointer value. (Assuming in sorted array, end will always be bigger and if sum > target we are looking for smaller value.
  • If sum value is less than target, increase the start pointer value. (Again here we are assuming in sorted array, our starting position value will be smaller than our end side and if sum < target we are looking for bigger value)
  • If you follow all these step, you will solve Two Sum II problem. If you are facing difficulty just look at example code below and try to understand the process.

Solution For Two Sum Two

I have used c# here just for readability. If you use any other language than c#, It will also be a great practice to convert c# code into your respective language. Good luck!

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.Length - 1;
        while(start < end)
        {
            int sum = numbers[start] + numbers[end];
            if(sum == target)
            {
                return new[] {start+1, end+1};
            } else if(sum > target)
            {
                end--;
            }else{
                start++;
            }
        }
        return new[]{0,0};

    }
}

Conclusion

Like any other two pointers problem, Two sum II also follows the same pattern. We create two pointers start and end, and apply a while statement. While statement will contain some logic that will increase start pointer or decrease end pointer or do both sometime. Make sure to look for pattern and draw out your solution before touching your idea or keyboard. Once you grab the pattern, you will start solving problem on your own.

Leave a Reply

Your email address will not be published. Required fields are marked *