Two Sum

🔗 Problem Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution Approach

Given an array of integers and a target value. We need to find out two numbers from the array which will sum the target value. To do this in the brute-force approach we can easily check all possible cases to find two numbers which will get us the target sum. But this approach will cost O(n^2) time. We can minimize this time complexity by using a hash-table. We'll iterate through the array and for each number we'll store the subtracted value from the target and the index to the hash-table. And in each iteration we'll check if the current number exists in the hash-table. If we get the value in hash-table that means we've found the two values that will give us the target sum!

Suppose, given -

nums = [2, 3, 5, 7]
target = 9

Let's have our HashMap M and visualize what we're doing in each iteration -

i = 0:
check nums[i] = 2 exists in M
[NO] Insert 9 - 2 = (7 -> 0) in M
     M = { 7: 0 }

i = 1
check nums[i] = 3 exists in M
[NO] Insert 9 - 3 = (6 -> 1) in M
     M = { 7: 0, 6: 1 }

i = 2
check nums[i] = 5 exists in M
[NO] Insert 9 - 5 = (4 -> 2) in M
     M = { 7: 0, 6: 1, 4: 2 }

i = 3
check nums[i] = 7 exists in M
[YES] return { i, M[7] } = { 3, 0 }

That's basically the illustration of our thought process, let's now try to code -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        unordered_map<int, int> M;

        for(int i=0; i<size; i++) {
            int diff = target - nums[i];
            if(M.find(nums[i]) != M.end()) {
                return { M[nums[i]], i };
            }

            M[diff] = i;
        }

        return {};
    }
};

This solution has linear time-complexity and linear space-complexity i.e. O(n). Can we achieve this in constant space by not using any additional data-structure? We can do that if the given array is sorted, then we can use an invariant to solve that in constant space! Having two pointers e.g. i and j, pointing to the 0th index and the n-1th index of the array! In each iteration we'll check if we can get A[i] + A[j] == target, because that's the result we want! But, what will happen when there will be inequality, or what will be the policy to move the indexes? Here, we'll be using the invariants. If we get A[i] + A[j] < target, we know that we cannot get the target by moving i forward, because it'll give us another larger value then the current A[i] as the array is sorted; so, we'll move j by decrementing the value, by this way we'll have a chance of minimizing the A[i] + A[j] and take closer to the target value. Otherwise, when A[i] + A[j] > target, if we understand the previous invariant then we can easily go with this, which is moving i forward because our sum i.e. A[i] + A[j] is lower than the target, if we move the ithe index forward we'll get a higher value. Let's go through an illustration of our solution approach -

A = [2, 5, 7, 9, 13]
target = 14

i = 0, j = 4
A[i] + A[j] ::= 2 + 13 ::= 15 > target ::= 15 > 14
Decrement j ::= 3

i = 0, j = 3
A[i] + A[j] ::= 2 + 9 ::= 11 < target ::= 11 < 14
Increment i ::= 1

i = 1, j = 3
A[i] + A[j] ::= 5 + 9 ::= 14 = target ::= 14 = 14
Done, return { i, j } ::= { 1, 3 }

Here's the code of this solution -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0, j = nums.size() - 1; i < j; ) {
            if(nums[i] + nums[j] == target) {
                return { i, j };
            } else if(nums[i] + nums[j] > target) {
                j--;
            } else {
                i++;
            }
        }

        return {};
    }
};

Complexity Analysis

Time Complexity O(n)

Linear time; as we need to iterate the whole array in the worst case

Space Complexity O(1)

Constant space; no additional data-structure applied