Two Sum Leetcode Solution

In this problem, we have to find a pair of two distinct indices in a sorted array that their values add up to a given target. We can assume that the array has only one pair of integers that add up to the target sum. Note that the array is sorted in a non-decreasing manner.

Example

Array = {1 , 2 , 3 , 4 , 5}
Target = 6

1 5

Array = {1 , 4 , 5 , 11 , 12}
Target = 9

2 3

Approach(Brute Force)

This approach is straightforward. We can check for every pair in the array and if their sum is equal to the given target, print their indices. This kind of Brute Force solution needs to check every possible pair and number of possible pairs in the array = n * (n – 1) / 2. So, in the worst-case, this approach can be slow.

Algorithm

1. Run a loop to maintain the first index of the solution in the array
2. Run another loop to maintain a second index of the solution for every first integer
3. If at any point, the sum of values of two indices is equal to the target
   • Print its indices

Implementation of Two Sum Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int n = a.size();
    for(int i = 0 ; i < n - 1 ; i++)
        for(int j = i + 1 ; j < n ; j++)
        {
            if(a[i] + a[j] == target)
                return {i + 1 , j + 1};
        }
    return {};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

Java Program

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        for(int i = 0 ; i < a.length - 1 ; i++)
            for(int j = i + 1 ; j < a.length ; j++)
            {
                if(a[i] + a[j] == target)
                    return new int[]{i + 1 , j + 1};
            }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}

2 3

Complexity Analysis of Two Sum Leetcode Solution

Time Complexity

O(N * N), where N =  size of the array. As we check for possible pair, and the total number of pairs are: N * (N – 1) / 2.

Space complexity

O(1). Only constant space for variables is used.

Approach(Two Pointer)

Algorithm

The give array is sorted. This is a special case because we know that if we have fixed a first index then the required value to fulfill the target an be found ahead in the array using binary search. 

A similar approach can be used: We can use two pointers: left and right, intially at the first and the last element of the array respectively. We can then compare the sum of these two pointer values to the target. If the sum of values and target are equal, then we have found the only solution. So, we return this index pair. Otherwise, if the sum of values is less than the target, we need to increment or dec rement one of the pointers. Obviously, we are bringing the right pointer from the end only. So, we should increment the left pointer and check for the same condition. Similarly, if sum of values is more than target, we decrement the right pointer.

Implementation of Two Sum Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int left = 0 , right = int(a.size()) - 1 , tempSum;
    while(left < right)
    {
        tempSum = a[left] + a[right];
        if(tempSum == target)
            return {left + 1 , right + 1};
        if(tempSum > target)
            right--;
        else
            left++;
    }
    return {-1 , -1};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

Java Program

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        int left = 0 , right = a.length - 1 , tempSum;
        while(left < right)
        {
            tempSum = a[left] + a[right];
            if(tempSum == target)
                return new int[]{left + 1 , right + 1};
            if(tempSum > target)
                right--;
            else
                left++;
        }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}

2 3

Complexity Analysis of Two Sum Leetcode Solution

Time Complexity

O(N), as even in the worst case, we visit all the elements in the array only once.

Space complexity

O(1). We use constant space for variables.