GoogleAlgorithmsEasy
Two Sum Problem
AlgorithmsArrayHashMapTwo Pointers
Question
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Interview Answer
Use a HashMap to store values and their indices while iterating once through the array. For each number, check if its complement (target - num) already exists in the map.
Explanation
Two Sum can be solved in O(n^2) brute force, but HashMap reduces it to O(n) by turning complement lookup into average O(1). Key point: check complement first, then store current number index.
Key Points
- HashMap gives O(1) average lookup per element
- Single-pass approach reduces time complexity to O(n)
- Store value -> index mapping for complement checks
- Return indices, not values
Common Mistakes
- Adding current item before complement check in duplicate-sensitive variants
- Returning values instead of indices
- Forgetting edge cases like no valid pair in generic versions
Likely Follow-Up Questions
- How would you solve if array is sorted?
- How do you return all valid pairs instead of one?
- What changes if duplicate pairs must be avoided?
Interview Timing
Target speaking time: about 3 minutes.