Print Array Index of two sum equals to given Target from Sorted Array | Java and Python Solution

Two Sum Leetcode in Java and Python | Find pair of two values is equal to given Target

Problem Description :

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.

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

For solution of this problem, we will seen two approach. 

1. Using brute force (Check all value one by one using two for loop). This is very time consuming approach. so you get time exceeding error.
   
2. Using two pointers.
   

Solution 1 : Two Sum in Java using Two Pointers

class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
       
        while (left < right) {
            if (numbers[left]+numbers[right] == target) {
                break;
            } else if (numbers[left]+numbers[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{left+1, right+1};
    }
}

Solution explanation :

• Given array is sorted and we have to print or return only 1 solution. 
• So we can use 2 pointers left and right for checking target sum.
• Define left as 0 and right as array length-1. 
• Loop until both indexes does not cross each other.
• If left and right index value is target value then break loop and return array index values.
• If sum is smaller than target increase left index by one. Otherwise decrease right index.

Output explanation :

numbers : [2, 7, 11, 15]
target : 9

• left = 0, right = 3
• left < right becomes true
• If condition | 2 + 15 = 17 | 17 == 9 becomes false
• Else If | 2 + 15 = 17 | 17 < 9 becomes false
• Else right = 2
• 0 < 2 becomes true
• 2 + 11 == 9 becomes false
• 2 + 11 < 9 becomes false
• right = 1
• 0 < 1 becomes true
• 2 + 7 == 9 becomes true
• Break while loop
• Return left+1 and right+1 | [1, 2] 

Solution 2 : Using two for loop (Brute force technique)

This solution is very time consuming than above solution. 

class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = new int[2];
    
        outerloop:
        for (int i = 0; i < numbers.length-1; i++) {
            for (int j = i+1; j < numbers.length; j++) {
                if (numbers[i]+numbers[j] == target) {
                    ans[0] = i+1;
                    ans[1] = j+1;
                    break outerloop;
                }
            }
        }
        return ans;
    }
}

Now lets see Python solution for this problem. We will seen 3 solutions for this problem.

1. Using two pointer
2. Using binary search
3. Using dictionary

Solution 3 : Two Sum solution in Python using two pointers

class Solution(object):
    def twoSum(self, numbers, target):
    left, right = 0, len(numbers)-1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1

Solution 4 : Two Sum solution in Python using binary search

class Solution(object):
    def twoSum(self, numbers, target):
        for i in xrange(len(numbers)):
            left, right = i+1, len(numbers)-1
            tmp = target - numbers[i]
            while left <= right:
                mid = left + (right - left) / 2
                if numbers[mid] == tmp:
                    return [i+1, mid+1]
                elif numbers[mid] < tmp:
                    left = mid+1
                else:
                    right = mid-1

Solution 5 : Two Sum solution in Python using dictionary

class Solution(object):
    def twoSum(self, numbers, target):
        dic = {}
        for i, num in enumerate(numbers):
            if target-num in dic:
                return [dic[target-num]+1, i+1]
            dic[num] = i

 

Other articles :

• Recursive Digit Sum HackerRank solution in Java with Explanation
  
• Rotate Array LeetCode solution in Java with explanation | Rotate array without extra array
• Check If N and Its Double Exist Leetcode solution in Java  
• Balanced Brackets HackerRank Solution in Java and Python with Explanation