deepSWE.io

Two Sum

ArrayHashingTwo Pointers

5-10 min

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.

Visual Example

Example 1:

Input Array:

idx 0

idx 1

idx 2

idx 3

Target:9

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

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

Output:[0, 1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

-10⁹ ≤ target ≤ 10⁹
Only one valid answer exists

Approach 1: Brute Force

The most straightforward solution is to check every pair of numbers in the array to see if they add up to the target. This is done using nested loops.

Interactive Brute Force Visualization

Step 0 of 21 • Comparisons: 0 • Target: 9

Array:nums

🔍 Checking all pairs...

Click 'Next' to start the brute force approach.

Algorithm Steps

Iterate through the array with a pointer i from the first to the last element.
For each element, iterate through the rest of the array with a pointer j from i + 1 to the last element.
Check if nums[i] + nums[j] equals the target.
If it does, return the indices [i, j].

Complexity Analysis

Time Complexity: O(n²). For each element, we iterate through the rest of the array.
Space Complexity: O(1). We are not using any extra space.

Brute Force Solution


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        # Iterate through each element in the array
        for i in range(n):
            # Iterate through the rest of the array
            for j in range(i + 1, n):
                # If the pair sums up to the target, return their indices
                if nums[i] + nums[j] == target:
                    return [i, j]

Approach 2: Hash Map

A more efficient approach is to use a hash map to store the numbers we've seen and their indices. This allows us to find the complement of each number in constant time.

Interactive Hash Map Visualization

Step 0 of 7 • Target: 9

Array:nums

Hash Map0 entries

Empty hash map

🔍 Searching...

Click 'Next' to start the visualization.

Algorithm Steps

Create an empty hash map.
Iterate through the array with a pointer i.
For each element nums[i], calculate the complement (target - nums[i]).
Check if the complement exists in the hash map.
If it does, we have found our pair. Return the index of the complement from the map and the current index i.
If it doesn't, add the current number and its index to the hash map.

Complexity Analysis

Time Complexity: O(n). We iterate through the array only once.
Space Complexity: O(n). In the worst case, we store all n elements in the hash map.

Hash Map Solution


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Create a hash map to store value -> index pairs
        num_map = {}
        # Iterate through the list with index and value
        for i, num in enumerate(nums):
            # Calculate the complement needed to reach the target
            complement = target - num
            # If the complement exists in the map, we found the solution
            if complement in num_map:
                return [num_map[complement], i]
            # Otherwise, store the current number's index in the map
            num_map[num] = i