Two Sum | HashMap Pattern

#algorithms #interview #java #leetcode

Problem Link: https://leetcode.com/problems/two-sum/

The Two Sum problem is one of the most frequently asked coding interview questions. While the brute force solution is straightforward, the real interview discussion revolves around identifying the complement pattern and optimizing it using a HashMap.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

Example

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Because:

nums[0] + nums[1] = 2 + 7 = 9

Brute Force Approach

Intuition

The most straightforward way is to check every possible pair.

For each element, iterate through all elements after it and verify whether their sum equals the target.

This works but performs many unnecessary comparisons.

Time & Space Complexity

Time Complexity: O(N²)
Space Complexity: O(1)

Java Solution

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[]{-1, -1};
    }
}

Optimizing the Solution

In the brute force approach, we're repeatedly searching for a number that can complete the target sum.

Instead of searching again and again, we can store previously seen numbers in a HashMap.

For every element:

Calculate the required complement.
Check if that complement already exists in the map.
If yes, we've found our answer.
Otherwise, store the current number and its index.

Since HashMap lookups take O(1) on average, we can solve the problem in a single pass.

Optimal Approach (HashMap)

Time & Space Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Java Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];

            if(map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{-1, -1};
    }
}