Solving the Two Sum Problem Using a Dictionary in Python

Introduction

The Two Sum problem is one of the most commonly asked coding interview questions. It helps build a strong understanding of arrays, loops and hash maps (dictionaries in Python).

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 the target.

Assumptions:

• Each input has exactly one solution
• You cannot use the same element twice

Example

Input:

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

Output:

[0, 1]

Explanation:

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

Approach

A brute force approach would check all pairs, which takes O(n^2) time.

Instead, we can use a dictionary to reduce the time complexity to O(n).

Key Idea

• As we iterate through the list, we store each number and its index in a dictionary

• For each number, we calculate its complement:

target - current number

• If the complement already exists in the dictionary, we have found the solution

Python Implementation

class Solution:
    def twoSum(self, nums, target):
        seen = {}  # value -> index

        for i in range(len(nums)):
            complement = target - nums[i]

            if complement in seen:
                return [seen[complement], i]

            seen[nums[i]] = i

Conclusion

Using a dictionary makes the Two Sum problem efficient and easy to solve. This approach is a great example of how choosing the right data structure can significantly improve performance.

Understanding this pattern will help in solving many similar problems in coding interviews.