EasyArrayHash TableUpdated Sep 2026

1. Two Sum

Asked at Google, Meta, Amazon, Apple and 10 more

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Array

Companies

14

Problem

You are given an array of numbers and a target number. Find the two positions in the array whose values add up to the target, and return those two positions.

Every input has exactly one answer, and you may not use the same position twice. You can return the two indices in any order.

What the problem asks

nums2711150123target = 9 → 2 + 7 = 9, so the answer is [0, 1]
Two positions whose values add up to the target — the indices are the answer, not the values.

Constraints

  • ●2 <= nums.length <= 10^4
  • ●-10^9 <= nums[i] <= 10^9
  • ●-10^9 <= target <= 10^9
  • ●Exactly one valid answer exists

Examples

Example 1
Inputnums = [2,7,11,15], target = 9
Output[0,1]
Whynums[0] + nums[1] = 2 + 7 = 9, so the two positions are 0 and 1.
Example 2
Inputnums = [3,2,4], target = 6
Output[1,2]
Why2 + 4 = 6. Position 0 is not used, because 3 + 3 would mean reusing the same element.
Example 3
Inputnums = [3,3], target = 6
Output[0,1]
WhyThe same value can appear twice, as long as the two positions are different.

Asked At

14 companies
CompanyDifficulty
GoogleEasyView all Google questions →
MetaEasyView all Meta questions →
AmazonEasyView all Amazon questions →
AppleEasyView all Apple questions →
MicrosoftEasyView all Microsoft questions →
OracleEasyView all Oracle questions →
UberEasyView all Uber questions →
AtlassianEasyView all Atlassian questions →
WalmartEasyView all Walmart questions →
BloombergEasyView all Bloomberg questions →
Goldman SachsEasyView all Goldman Sachs questions →
TikTokEasyView all TikTok questions →
NVIDIAEasyView all NVIDIA questions →
JPMorganEasyView all JPMorgan questions →

How to Think About It

1

Brute force: try every pair. Use two nested loops — for each element i, check every element j after it. If nums[i] + nums[j] == target, return [i, j]. This works but is O(n²) time because you check n*(n-1)/2 pairs. The interviewer will immediately ask you to optimize.

2

Key insight: for each number, you already know what its partner must be. If the current number is 7 and the target is 10, the partner must be 3. You don't need to search for it — just check if you've seen 3 before. That's a hash table lookup: O(1).

3

The pattern: as you walk through the array once, store each number and its index in a hash map. At each step, calculate the complement (target - current). If the complement is already in the map, you found both indices. If not, store the current number and keep going.

4

Why this works: the brute force checks "for each i, does any j exist?" The hash table flips it to "for each j, did I already see its complement?" Same question, but now each lookup is O(1) instead of O(n).

5

Edge cases: the problem guarantees exactly one solution, so you will always find a pair. If the interviewer asks "what if there are multiple valid pairs?" — that's a follow-up (return all pairs). Also handle: target = 0 with negative numbers, single element array.

Optimal Approach

Initialize an empty hash map. Iterate through the array with index i and value num. Calculate complement = target - num. Check if complement exists in the hash map. If yes, return [hash_map[complement], i]. If no, store num: i in the hash map and continue.

Walkthrough with example: nums = [2, 7, 11, 15], target = 9.

  • i=0, num=2, complement=7. Map empty. Store {2: 0}.
  • i=1, num=7, complement=2. Map has 2 at index 0. Return [0, 1].

Time: O(n) — one pass through the array. Space: O(n) — hash map stores up to n elements.

One pass with a hash map

nums2711150123i = 0Step 1 — partner is 9 − 2 = 7. Not seen yet, so store2.seen (value → index)valueindex20nums2711150123i = 1Step 2 — partner is 9 − 7 = 2, and 2 is already in themap.2 was stored at index 0→ return [0, 1]
At each number you already know its partner. Look the partner up first, then store the current number.
ComplexityTime O(n)Space O(n)One pass over the array, with a hash map holding at most n entries.

What Trips People Up in Real Interviews

1

Jumping straight to code without stating the brute-force first. Interviewers want to hear you reason about O(n²) before optimizing to O(n). Say: "My first thought is to check every pair, which is O(n²). I can do better with a hash map."

2

Confusing "return the indices" with "return the values." The problem asks for indices, not the numbers themselves. Re-read the return type before coding — this is the #1 careless mistake on Two Sum.

3

Forgetting that the same element cannot be used twice. If nums = [3, 3] and target = 6, you need two different indices. Your hash map must store the index and check it after storing the current element.

4

Trying two pointers on an unsorted array. Two pointers requires sorted input, and sorting loses the original indices. The hash map one-pass approach is the correct fit here.

5

Not handling the edge case where complement equals the current number. If target = 6 and current = 3, you need another 3 at a different index. Store the current element first, then check for complement on the next iteration.

Solution Code

O(n) time
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Two Sum problem?

Two Sum asks you to find two numbers in an array that add up to a target value, then return their indices. It is one of the most frequently asked opening questions in FAANG interviews — used to gauge how you think about time and space tradeoffs before moving to harder problems.

How do you solve Two Sum?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Two Sum?

Two Sum is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Uber, Atlassian, Walmart, Bloomberg, Goldman Sachs, TikTok, NVIDIA, JPMorgan. It is a easy difficulty problem.

What are common mistakes on Two Sum?
  • Jumping straight to code without stating the brute-force first. Interviewers want to hear you reason about `O(n²)` before optimizing to `O(n)`. Say: "My first thought is to check every pair, which is `O(n²)`. I can do better with a `hash map`."
  • Confusing "return the indices" with "return the values." The problem asks for indices, not the numbers themselves. Re-read the return type before coding — this is the #1 careless mistake on Two Sum.
  • Forgetting that the same element cannot be used twice. If `nums = [3, 3]` and `target = 6`, you need two different indices. Your `hash map` must store the index and check it after storing the current element.
  • Trying two pointers on an unsorted array. Two pointers requires sorted input, and sorting loses the original indices. The `hash map` one-pass approach is the correct fit here.
  • Not handling the edge case where complement equals the current number. If `target = 6` and `current = 3`, you need another 3 at a different index. Store the current element first, then check for complement on the next iteration.