Skip to main content

1. Two Sum

easyAsked at Expedia

Given an array of nums and a target, return indices of two numbers that add up to target.

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

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, and you may not use the same element twice.

Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • Exactly 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 of indices.

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 one-pass

Store seen values in a map. For each num, check if target-num exists. This is what Expedia expects for fast price-pair lookups across supplier inventories.

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

Tradeoff:

Expedia-specific tips

Expedia values clean one-pass solutions; mention how this scales when checking complementary fares across millions of flight-hotel bundle combinations.

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 Expedia interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →