1. Two Sum

Problem Statement

The Two Sum problem is one of the most frequently asked coding interview questions. The problem is simple:

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

Constraints:

• Each input has exactly one solution.

• You may not use the same element twice.

• Return the answer in any order.

Intuition

To solve the Two Sum problem efficiently, we need to avoid the brute-force approach that checks every possible pair of elements — which takes O(n²) time. Instead, we use a hash table (or dictionary in Python) that allows for constant-time lookups on average — giving us a linear-time solution.

Core Idea

The main idea is to iterate through the array once, and for each number x, we:

1. Calculate the complement: y = target - x.

2. Check if this complement y already exists in our hash table.

   • If it does, we’ve found the pair: x + y = target.

   • If it doesn’t, we store x and its index in the hash table for future reference.

This strategy ensures that each number is processed only once, achieving O(n) time complexity and making the solution both fast and elegant.

Example Walkthrough

Let’s understand with an example:

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

Step-by-step:

• Start with an empty hash table: {}

• For i = 0, value = 2

  • target - 2 = 7 → not in hash table

  • Store: {2: 0}

• For i = 1, value = 7

  • target - 7 = 2 → 2 is in hash table

  • Found the answer: indices [0, 1]

Return: [0, 1]

Brute Force

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

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

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

Optimal Solution (Hash Map)

public int[] twoSum(int[] nums, int target) {
    Map<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[]{};
}

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement))
            return {map[complement], i};
        map[nums[i]] = i;
    }
    return {};
}

def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

Time and Space Complexity

Time Complexity: O(n)

The time complexity of this algorithm is O(n), where n is the number of elements in the nums array. This is because we traverse the array only once using a single loop. Each operation inside the loop—such as checking whether a key exists in the hash map and inserting a new key-value pair—takes constant time on average, i.e., O(1). Therefore, the total time taken scales linearly with the size of the input array.

Space Complexity: O(n)

The space complexity is also O(n). In the worst-case scenario, all elements in the nums array could be stored in the hash map. Since each element and its corresponding index are added only once, the additional space used by the map grows proportionally to the input size. Thus, the space usage increases linearly with the number of elements in the array.