Black Friday 50% off any plan, for life Ends Nov 30

Coding interview problems

Two Sum

Two Sum is the question interviewers open with. Finding the pair is expected. What gets you the strong hire is naming the O(n²) scan, spotting the complement and landing on a one-pass hash map before anyone nudges you. Then comes the sorted-array follow-up.

Write it yourself before they ask

Reading Two Sum is easy. Writing it while an interviewer watches is what gets you hired. Solve it yourself in the 14-day free trial, and the learning engine brings it back before you forget it.

14-day free trial. Cancel anytime with one click.

I have an account

The problem

Given an integer array arr and an integer target, return the indices of the two numbers that add up to target, smaller index first.

You can't use the same element twice. If no pair adds up to target, return an empty array.

Constraints

  • 0 <= arr.length <= 10^4: arr may be empty or contain a single number.
  • -10^9 <= arr[i] <= 10^9 and -10^9 <= target <= 10^9; values may repeat.
  • At most one pair adds up to target.

Example

Input
arr = [3, 8, 11, 5, 2, 7], target = 9
Output
[4, 5]

2 is at index 4 and 7 is at index 5, and 2 + 7 = 9.

  1. 0:00Two Sum
  2. 0:46The problem
  3. 1:26Brute force
  4. 2:35A better idea
  5. 3:19Walkthrough
  6. 4:38Complexity
  7. 5:00Code
  8. 6:01Follow-up: sorted
  9. 7:29Which one?
  10. 8:05Recap

How to solve it

The obvious answer is to try every pair. It never misses one, and on 10,000 numbers it's about 50 million sums. Say it out loud with its cost, O(n²), and move on.

When you reach a number n, its partner has to be target - n, its complement. So walk the array once and keep a hash map from the complement each earlier number needs to that number's index. If the current number is already a key, an earlier number was waiting for it: return that index and this one. Otherwise, store target - n with the current index and keep going.

Two Sum([-1,-2,-3,-4,-5], -8)

The run starts on [-1,-2,-3,-4,-5], -8.

Each number is checked against the map before its own complement goes in. That is why, with a target of -8, a single -4 can't pair with itself. If no number ever finds itself in the map, the loop ends and you return an empty list.

Expect the follow-up: what if the array is sorted? Put one pointer at each end. If the sum is too big, move the right pointer in; if it's too small, move the left one up. That's O(n) time with O(1) extra space. On an unsorted array, sorting first costs O(n log n) and scrambles the indices you have to return, so the hash map stays the answer.

Python solution

from typing import List


class Solution:
    def two_sum(self, arr: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, n in enumerate(arr):
            if n in num_dict:
                return [num_dict[n], i]
            else:
                num_dict[target - n] = i

        return []

Time and space complexity

Time O(n)
One pass, with one hash map lookup and at most one insert per number.
Space O(n)
In the worst case the map holds an entry for every number.

Be ready for the next one

Walk into the coding round ready

Practice 1,500+ real interview questions, built by former Meta, X and LinkedIn engineers. 50,000+ engineers have prepared with Firecode.

14-day free trial. Cancel anytime with one click.

Built by former engineers at

I have an account
50,000+engineers preparing with Firecode
1500+real interview questions from top tech companies
14languages, from Python to Rust
FAANG+offers landed at Google, Meta, Netflix, and more
Google Meta Amazon Apple Microsoft Netflix OpenAI Anthropic Stripe Nvidia Airbnb Uber Coinbase DoorDash Spotify Shopify Snowflake Cloudflare Bloomberg Dropbox