<Devtools/>daily Tools Cheatsheets Interview
Problems Blog Pricing

Ctrl + K

Solution for interview question: Two Sum

1. Understanding the Problem

You are given an array of integers and a target sum.
The task is to find two distinct numbers in the array that add up to the target.
You should return their indices as a result.

2. Brute Force Approach (Inefficient)

Start by considering a brute force approach where you check every possible pair.
For each number, iterate through the remaining numbers and check if they add up to the target.
This approach has O(n²) time complexity.

def two_sum(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]
    return None

3. Identifying the Core Operation

The core operation is checking whether two numbers in the array add up to the target.
For each number num, check if there’s another number complement such that: num + complement = target
The complement can be calculated as complement = target - num.

4. Using a Hash Map for Efficient Lookup

Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

5. Initializing the Hash Map

Create an empty hash map to store numbers and their indices as you iterate through the array.

def two_sum(nums, target):
    hash_map = {}  # Initialize an empty dictionary
    return hash_map

6. Iterate Through the Array and Calculate Complement

Loop through the array.
For each number, calculate its complement (the difference between the target and the current number).
The complement is calculated as target - num.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num  # Calculate the complement
    return None

7. Check if the Complement Exists in the Hash Map

For each number, check if the complement exists in the hash map.
If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
Return the indices of the current number and its complement.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:  # Check if complement exists
            return [hash_map[complement], i]  # Return the indices
    return None

8. Store the Current Number in the Hash Map

If the complement is not found in the hash map, store the current number and its index in the hash map.
This ensures that it can be checked as a complement for future numbers.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i  # Store current number
    return None

9. Handle Edge Cases

Ensure that the input array has at least two numbers.
Return None if no solution is found.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None  # Return None if no solution is found

PrivacyTermsFAQChangelogContact Us © Monkey SkatesHave kids?