Two Sum
Tags: codinginterview, problemsolving, cpp, leetcode
Published: 2020-05-11 11:51:07

---
title: Two Sum
published: true
tags: coding-interview, problem-solving, cpp, leetcode
series: Blind75 - Array
cover_image: https://images.unsplash.com/photo-1509228627152-72ae9ae6848d?ixlib=rb-1.2.1&ixid=eyJhcHBfaWQiOjEyMDd9&auto=format&fit=crop&w=1650&q=80
---
## [🔗](https://leetcode.com/problems/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 -

```cpp
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 `0`th index and the `n-1`th 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 `i`the 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 -

```cpp
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