The Classic...Two Sum Problem

Introduction

Two Sum is the most classic problem, Leetcode # 1 problem
It gives us an array of integers and an integer target, and asks us to return indices of two numbers such that they add to target
Now this problem might seem easy but optimization is still something to think hard on.
Before that, let's see it's brute force, that is, solving it without caring about efficiency and constraints.

Brute Force

Brute force would be to check for every pair in array and see if they sum to target, if so, we will return their indices, if not, we'll return empty array

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {}; // No solution found
    }
}

Basically let's say array given was {2,4,7,6} and target was 10
Then we'd start with 2, and check its sum with remaining elements...
2+4, 2+7, 2+6 and none of them sums to target value, so we move ahead, now 4, 4+7, 4+6 HERE we have our answer...4+6=10
So we'll return [1,3]
But it's time complexity is O(n^2) which is very slow if input is large. It's like we have some ingredients and we're checking every possible combination to see if our dish is tasty..works on small number but when there's thousand ingredients, it's very slow

That's where the usage of Data Structure comes in
We will use HashMap to keep a compliment that will check if we've seen our partner..

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0 ; i<nums.length ; i++){
            int compliment = target - nums[i];

            if(map.containsKey(compliment)){
                return new int[] {map.get(compliment), i};
            }
            // Store the current number and its index
            map.put(nums[i], i);
        }
        return new int[] {}; 
    }
}

Here TC = O(n)