Interview Question – “Two Sum” problem

One of the most popular programming interview questions at Google is the “Two Sum” problem. The problem is simple in theory but requires a well-structured and optimized solution. The question asks for an algorithm that can find two numbers in an array that add up to a target sum.

Problem Statement:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example:



Input: nums = [2,7,11,15], target = 9 
Output: [0,1] 
Explanation: The sum of 2 and 7 is 9. Therefore index 0 and index 1 are returned.

1

2

3

4

5

6

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

Output: [0,1]

Explanation: The sum of 2 and 7 is 9. Therefore index 0 and index 1 are returned.

Solution:

The brute-force solution to this problem is to have two nested loops, where the outer loop will iterate through each element of the array, and the inner loop will iterate through the rest of the elements to check if any two numbers add up to the target sum. This solution has a time complexity of O(n^2), which is not very efficient for large inputs.

A more optimized solution is to use a HashMap to store the previously encountered numbers and their indices. We iterate through the array once and for each element, we check if its complement (i.e., the difference between the target and the current element) exists in the HashMap. If it does, we return the current index and the index of the complement from the HashMap. Otherwise, we add the current element and its index to the HashMap.

Here is the implementation of the optimized solution in Java:



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);
    }
    throw new IllegalArgumentException("No two sum solution");
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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);

}

throw new IllegalArgumentException("No two sum solution");

}

The time complexity of this solution is O(n), as we are iterating through the array only once, and the space complexity is O(n), as we are using a HashMap to store the numbers and their indices.

In conclusion, the “Two Sum” problem is a classic interview question that tests a candidate’s problem-solving skills and their ability to write an optimized algorithm. By using a HashMap to store previously encountered numbers, we can find the solution to this problem in linear time complexity, which is an efficient and optimized approach.