Skip to main content

1. Two Sum

easyAsked at GitHub

Find indices of two numbers in an array that sum to a target — GitHub uses this to gauge hash-map intuition before diving into Git ref lookup problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution; you may not use the same element twice.

Constraints

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

Examples

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]

Approaches

1. Brute force

Check every pair with nested loops.

Time
O(n^2)
Space
O(1)
for (let i=0;i<nums.length;i++)
  for (let j=i+1;j<nums.length;j++)
    if (nums[i]+nums[j]===target) return [i,j];

Tradeoff:

2. Hash map single-pass

Store seen values mapped to their index; for each element check if (target - value) is already in the map. Single pass, constant lookup.

Time
O(n)
Space
O(n)
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

Tradeoff:

GitHub-specific tips

GitHub interviewers explicitly link this to Git's SHA-to-object hash table — narrate map operations as O(1) ref lookups.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Two Sum and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →