ToolMight LogoToolMight
EasyArrays & HashingPattern: Hash MapPattern: Complement Lookup

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

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

Examples & Constraints

Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 2 + 7 == 9, we return [0, 1].
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: Because nums[1] + nums[2] == 2 + 4 == 6, we return [1, 2].
Constraints
  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Select Approach (2 Solutions)

Brute Force (Nested Loops)

Time:O(n²)
Space:O(1)

Inspect every possible pair of elements using two nested loops to check if their sum equals the target.

Time ComplexityO(n²)

Nested loops examine every pair: (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 iterations.

Space ComplexityO(1)

No extra memory buffers or data structures are allocated beyond primitive loop index variables.

Underlying algorithmic logic

The Naive Instinct: Check Every Pair

The first instinct when solving Two Sum is exhaustive search: try pairing every single number with every other number after it.

  1. Pick an element nums[i] using an outer loop.
  2. In an inner loop, check every subsequent element nums[j] (where j > i).
  3. If nums[i] + nums[j] == target, return [i, j].

Why Engineers Must Optimize This

While O(1) memory sounds nice, checking all pairs evaluates roughly N * (N - 1) / 2 ≈ N² / 2 combinations.

  • For N = 100, that is ≈ 5,000 operations (instant).
  • For N = 100,000, that is ≈ 5,000,000,000 operations (several seconds to timeout in production).

In system design and interviews, quadratic O(n²) time is a red flag: we should ask ourselves, "Can we trade a small amount of memory to drop this from quadratic to linear time?"

Step-by-step execution walkthrough

1
Outer Pointer at Index 0

Pick nums[0] = 2. We now need to search remaining elements for (9 - 2) = 7.

i = 0 (val: 2)
2
Inner Scan at Index 1

Inspect nums[1] = 7. Calculate sum: 2 + 7 = 9. Exactly equals target!

nums[0] + nums[1] == 9 -> Match!
3
Return Indices

Return [0, 1]. Solution pair identified without checking remaining elements.

Result: [0, 1]
Advantages
  • •Zero auxiliary memory overhead
  • •Simple to reason about and implement
Trade-offs
  • •Very slow on large inputs (timeouts for N > 10,000)
  • •Redundant pairwise recalculations

Code Implementations

Copy & paste production-ready solutions for Brute Force (Nested Loops) in your language of choice

File: solution.py
Python
def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    print("Indices:", two_sum(nums, target))
Interactive visualizer available

Understand Hash Table Visually

Visualize key hashing functions, index mapping arrays, and hash collision resolution techniques. Test live edge cases and watch memory state transitions step-by-step.

Launch Hash Table Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Valid Anagram

Determine whether two strings have the exact same character frequencies. A core problem demonstrating the power of fixed-size frequency buckets over O(n log n) sorting.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Linear Search

The foundational search algorithm for unsorted collections. Scans elements one by one until a match is found or the list is exhausted.

2 approaches(O(n))
Learn logic
EasySliding Window
Visualizer

Best Time to Buy and Sell Stock

Determine the maximum single-transaction profit from daily stock prices. A classic demonstration of how tracking a running minimum transforms an O(n²) pair search into an O(n) single pass.

1 approach(O(n))
Learn logic