Solving the Classic Two Sum Problem (FAANG-Style)
One of the most common problems that shows up in coding interviews—especially at FAANG-level companies—is the Two Sum problem. It’s simple at first glance, but it gives interviewers a window into how you approach problem-solving, trade-offs, and optimization.
📌 The Problem
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.
- You cannot use the same element twice.
- You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Exactly one valid answer exists.
🐢 Brute Force Approach
The most straightforward solution is to check all pairs:
class Solution(object):
def twoSum(self, nums, target):
i = 0
rtype = []
while (rtype == [] and i < len(nums) - 1):
n = i + 1
while (rtype == [] and n < len(nums)):
if target == nums[i] + nums[n]:
rtype = [i,n]
else:
n += 1
i += 1
return rtype
- ✅ Correct
- ❌ Time Complexity: O(n²) (bad for large arrays)
⚡ Optimized Hash Map Solution
At FAANG-level interviews, the expectation is that you recognize the inefficiency and move toward an optimized solution.
Key idea: Use a hash map (dictionary) to remember numbers we’ve seen. For each number, compute its complement (target - num). If the complement is already in the map, we’ve found the solution.
class Solution(object):
def twoSum(self, nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
Walkthrough:
- Input:
nums = [2,7,11,15], target = 9
- i=0, num=2 → complement=7 → not in seen → store
{2:0}
- i=1, num=7 → complement=2 → found in seen → return
[0,1]
Result: [0,1]
Complexity:
- Time: O(n)
- Space: O(n)
🔄 Alternative: Two Pointers (When Sorted)
If the array is sorted, we can use a two-pointer approach:
def twoSumSorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left, right]
elif s < target:
left += 1
else:
right -= 1
return []
- Time: O(n)
- Space: O(1)
- Note: Only works when
numsis sorted.
🎯 Why This Problem Matters
This is more than just a toy problem:
- Tests your ability to optimize from naive → efficient.
- Tests knowledge of data structures (hash maps, pointers).
- Sets the stage for more advanced interview questions (like “What if the array is too large for memory?” or “What if it’s a stream of numbers?”).
At FAANG-level interviews, it’s not just about solving the problem—it’s about:
- Explaining trade-offs (brute force vs. optimized).
- Writing clean, readable code.
- Communicating your thought process clearly.
💡 Takeaway: Always start with the brute force to show understanding, then optimize with a hash map or two-pointer strategy depending on the input constraints.
✍️ I’m building a series on interview prep with coding, SQL, and system design case studies. Follow along if you’re preparing for data engineer / software engineer interviews!