1. Two Sum

The Two Sum problem is one of the most fundamental and frequently asked coding interview questions. It appears early in interview prep because it tests more than basic syntax. Companies like Google, Meta, Amazon, and Microsoft often use it as a warm-up to assess problem-solving clarity.

Although the problem statement looks simple, interviewers are less interested in a brute-force answer and more focused on whether you can identify and apply the hashing pattern efficiently.

Problem statement

You are given an array of integers nums and an integer target. Your task is to return the indexes of the two distinct numbers such that their sum equals target.

You may assume that:

• Exactly one valid solution exists.
• You may not use the same element twice.
• The order of the returned indexes does not matter.

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Examples

Brute force approach

An easy way to solve this problem is to treat it as a direct search over all possible pairs.

The logic: For every number in the array, check whether there exists another number later in the array such that their sum equals the target. This leads to a simple nested loop strategy where each element is paired with every element that comes after it.

If we find a pair nums[i] + nums[j] == target, we immediately return their indexes [i, j].

The drawback: This approach performs redundant work. Even after checking a value once, we may compare it again and again against many other elements. As the array grows, the number of comparisons increases rapidly, making the solution inefficient.

Time complexity: The time complexity becomes O(n²) due to the nested loops.

Space complexity: O(1)

Key observation

At its core, Two Sum asks a simple question:

If the current number is x, then the required counterpart is: target − x

The challenge is finding that counterpart quickly. Searching the entire array for every element is inefficient. This is where a hash map becomes the natural choice as it allows constant-time lookups.

Instead of checking pairs explicitly, we remember what we have already seen and use that memory to make fast decisions.

Optimized approach using Hash Map

To eliminate the repeated searching present in the naive solution, we introduce a hash map to store information about the numbers we have already seen.

Instead of asking, “Does a matching pair exist somewhere else in the array?”, we reframe the problem to ask a more efficient question at each step:

As we iterate through the array from left to right, we keep a hash map that maps each number to its index. For the current number x, we compute its required counterpart as target − x. If that value already exists in the map, we have found our answer.

This approach replaces repeated linear searches with constant-time lookups. As a result, the problem is transformed from a quadratic process into a single-pass solution.

Step-by-step algorithm

Here’s the detailed algorithm that we’ll use to solve the given problem:

1. Create an empty hash map, seen, to store numbers we have already processed along with their indexes.
2. Traverse the input array, nums, one element at a time using an index i.
3. For the current element num in nums, calculate the complement using target − num.
   1. If the complement exists in seen, return the pair of indexes.
   2. Otherwise, store the current number, num, and its index, i, in seen.
4. Keep iterating once the target is found.

As the problem guarantees exactly one valid solution, the algorithm will always terminate as soon as the correct pair is found.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 4

Code implementation

Let’s look at the code for this solution below:

def twoSum(nums, target):
    # Hash map to store numbers we have already seen
    # Key   -> number value
    # Value -> index of that number in the array
    seen = {}

    # Traverse the array once
    for i, num in enumerate(nums):
        # Calculate the value needed to reach the target sum
        complement = target - num

        # Check if this required value has already been seen
        # If yes, we have found the two indexes that sum to target
        if complement in seen:
            return [seen[complement], i]

        # Otherwise, store the current number and its index
        # This allows future elements to pair with it
        seen[num] = i

def main():
    testCases = [
        ([3, 8, 12, 4], 16),
        ([5, -2, 9, 11], 7),
        ([0, 6, 3, 0], 0),
        ([1, 7, 15, 2], 9)
    ]

    for i, (nums, target) in enumerate(testCases, 1):
        print(i, ".  Input nums = ", nums, ", target = ", target, sep="")
        print("    Output indexes: ", twoSum(nums, target), sep="")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

We traverse the array once, and each hash map operation takes O(1) on average. So, the overall time complexity for this solution becomes O(n).

Space complexity

The space complexity is also O(n) as, in the worst case, we may store all elements of the array in the hash map.

Common pitfalls and interview tips

• Using the same element twice: Always store the current element after checking for its complement.
• Sorting the array first: Sorting breaks index tracking unless additional bookkeeping is done. Hashing is simpler and cleaner.
• Returning values instead of indexes: Read the problem carefully the output requires indexes, not values.