Skip to main content

Two Sum

— Prerna Sharma

Two Sum

Three approaches: nested loops → two pointers → hash map. Learn all three!

Easy Array Hash Map Two Pointers

Problem Statement

Given

An integer array nums and an integer target. Return the indices of the two numbers that add up to target.

Example

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  →  because nums[0] + nums[1] = 2 + 7 = 9

Constraints: Exactly one valid answer exists. You cannot use the same element twice.

Think of It Like This 🧠

Imagine you're looking at a price list and you have ₹9 to spend on exactly 2 items. You want to find which 2 items cost exactly ₹9 together.

Array: [2, 7, 11, 15]  |  Target: 9

2idx 0
7idx 1
11idx 2
15idx 3

2 + 7 = 9 ✅ → Answer: [0, 1]

Approach 1 — Brute Force (Nested Loops)

The simplest idea: try every possible pair of numbers. Pick one, then scan all the rest to see if any of them completes the target.

🐌 Brute Force

Two nested loops checking every pair

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

🔵 Two Pointers

Sort array, shrink from both ends

Time: O(n log n) Space: O(n)

⚡ Hash Map

One pass with a hash map storing complements

Time: O(n) Space: O(n)

How Brute Force Works

For every element at index i, scan all elements at index j where j > i. If nums[i] + nums[j] == target, return [i, j].



  
🔍 Dry Run — Brute Force

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

  

    

      
ijnums[i]nums[j]Sum== 9?

      
        
01279✅ Return [0,1]

      
    

  

  
Lucky! Found on first try. But with [15, 11, 7, 2], it would check all pairs before finding the answer — O(n²) in the worst case.


  
Approach 2 — Hash Map (Optimal) ⚡

  
Instead of looking forward for a match, we ask: "Have I already seen the number I need?"

  
For each element nums[i], we calculate complement = target - nums[i]. If that complement is already in our hash map, we found the answer!


  

    
HashMap: { value → index }

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

    

      i=0, val=2
      complement = 9-2 = 7 → not in map
      → store {2:0}
    

    

      i=1, val=7
      complement = 9-7 = 2 → 
      ✅ 2 IS in map at index 0!
    

    

      
Final Map State at i=1

      
2→index 0// stored from i=0

    

    
Return [map.get(2), 1] = [0, 1] ✅

  


  
  


  
🔍 Dry Run — Hash Map Approach

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

  

    

      
inums[i]complementIn Map?Map after step

      
        
029-2=7❌ No{2:0}

        
179-7=2✅ Yes (idx 0)Return [0, 1]

      
    

  


  
Approach 3 — Two Pointers (Sort + Squeeze)

  
Sort a copy of the array (preserving original indices), then place one pointer at the left end and one at the right end. Squeeze them inward based on the sum.


  

    ⚠️ Important Catch: Sorting rearranges elements, so we lose original indices. We must sort a copy that carries original indices. LeetCode #1 asks for indices, so we need to track them through the sort.
  


  

    
Example: nums = [2, 7, 11, 15], target = 9 → sort with indices tracked

    

      
2orig: 0

      
7orig: 1

      
11orig: 2

      
15orig: 3

    

    

      

        
2L

        
LEFT →

      

      
7-

      
11-

      

        
15R

        
← RIGHT

      

    

    

      
sum = 2 + 15 = 17  → 17 > 9, too big → move RIGHT left

      
sum = 2 + 11 = 13  → 13 > 9, still too big → move RIGHT left

      
sum = 2 + 7 = 9  → 9 == 9 ✅ → return original indices [0, 1]

    

  


  
The Three Rules

  

    
sum vs targetActionReason

    
      
sum == targetReturn the pair ✅Found it!

      
sum > targetright-- (move right left)Need a smaller number on the right

      
sum < targetleft++ (move left right)Need a bigger number on the left

    
  


  
  


  
🔍 Dry Run — Two Pointers

  
Input: nums = [3, 2, 4], target = 6

  
After sorting with indices: [(2,idx1), (3,idx0), (4,idx2)]

  

    

      
leftrightsorted[L]sorted[R]sumAction

      
        
022 (orig:1)4 (orig:2)6✅ Return [1, 2]

      
    

  

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

  
After sorting with indices: [(2,idx0), (7,idx1), (11,idx2), (15,idx3)]

  

    

      
leftrightsorted[L]sorted[R]sumAction

      
        
032 (orig:0)15 (orig:3)17sum > 9 → right--

        
022 (orig:0)11 (orig:2)13sum > 9 → right--

        
012 (orig:0)7 (orig:1)9✅ Return [0, 1]

      
    

  


  
Time & Space Complexity

  

    
ApproachTimeSpaceNote

    
      
Brute ForceO(n²)O(1)Nested loops, checks all pairs

      
Two PointersO(n log n)O(n)Sort dominates; O(n) extra for index tracking

      
Hash MapO(n)O(n)Single pass, map stores up to n elements

    
  


  

    Key Insight: Two Pointers works beautifully when the problem gives you a sorted array or doesn't need original indices. For this exact problem (return indices), Hash Map is the true optimal since sorting costs O(n log n) and needs a copy. But the Two Pointers pattern is fundamental — you'll see it constantly in 3Sum, 4Sum, and container-with-most-water!
  


  
Code — All Approaches × All Languages


  
  

    

      Approach 1
      🐌 Brute Force — Nested Loops
      O(n²) O(1)
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 2
      🔵 Two Pointers — Sort + Squeeze
      O(n log n) O(n)
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 3
      ⚡ Hash Map — One Pass
      O(n) O(n)
    

    

      
      
      
      
    

    

    

    

    

  


  

  

    🎯 Interview Tip: Know all three approaches and when to use each. "What if the array were already sorted?" → Two Pointers. "Most time-efficient?" → Hash Map O(n). "Memory constrained?" → Two Pointers. Two Pointers also directly generalizes to 3Sum, 4Sum, and Container with Most Water!