Two Sum - Leetcode 1 - HashMap - Python

Main ideas / lesson conveyed

Problem (LeetCode: Two Sum)

• You’re given:
  • an input array
  • a target sum (example: 9)
• Find two numbers in the array whose sum equals the target.
• Return their indices.
  • Example: numbers 2 and 7 sum to 9 → return indices 0 and 1.
• It’s guaranteed there is exactly one solution, so you can ignore:
  • “no solution” handling
  • multiple-solution handling

Brute force approach (baseline concept)

• Check every pair of elements:
  • For each first value, scan through the rest of the array to find a second value that completes the sum.

• Efficiency note:

  • When checking pairs that start with a given element, you don’t need to re-check combinations already considered earlier.

• Time complexity: (O(n^2)) (worst case)

• This is the brute force approach.

Optimized approach using a HashMap (core concept)

• Key observation:
  • For a current number x, the required partner must be:
    • difference = target - x
• Use a hash map to store:
  • value → index
• Important constraint:
  • You cannot reuse the same array element, so index tracking matters.

“Clever” one-pass HashMap trick (methodology)

Instead of preloading the entire array:

1. Start with an empty hash map.
2. Iterate through the array left to right.
3. For each element n at index i:
   • Compute difference = target - n
   • Check if difference already exists in the hash map:
     • If yes, return:
       • the stored index for difference
       • the current index i
   • If not found, store:
     • map[n] = i

• Why one pass works:
  • When you reach the second element of the correct pair, the first element has already been visited and is already present in the hash map.

Complexity of the HashMap method

• Time complexity: (O(n))
  • Each iteration does constant-time hash lookups/insertions.
• Space complexity: (O(n))
  • The hash map may store up to all values.

Implementation outline in Python (instructions / steps)

• Initialize an empty dictionary previous_map (hash map of value → index).
• Loop over the array with index i and value n:
  • Compute difference = target - n
  • If difference is in previous_map:
    • return indices:
      • previous_map[difference] (first index)
      • i (second index)
  • Otherwise:
    • set previous_map[n] = i
• Since the problem guarantees a solution exists, you typically won’t reach a “no solution” case.

Speakers / sources featured

• No specific speakers or external sources are identified in the provided subtitles (only general narration of the algorithm).