Skip to main content

21. Two Sum II - Input Array Is Sorted

easyAsked at Snowflake

Two-sum when input is already sorted, asking for the two indices. Snowflake uses this to test whether you exploit the sortedness — the same instinct a query planner uses to pick a merge-join over a hash-join when inputs are already sorted.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team screens use this to set up join-algorithm discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad onsites.

Problem

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. Your solution must use only constant extra space.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

Examples

Example 1

Input
numbers = [2,7,11,15], target = 9
Output
[1,2]

Example 2

Input
numbers = [2,3,4], target = 6
Output
[1,3]

Approaches

1. Hash map

Same as Two Sum I — ignore the sortedness.

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

Tradeoff: Violates the O(1) space constraint. Mention to acknowledge but move on.

2. Two pointers (optimal)

Left from start, right from end. If sum > target, decrement right; if sum < target, increment left.

Time
O(n)
Space
O(1)
function twoSum(numbers, target) {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    const sum = numbers[l] + numbers[r];
    if (sum === target) return [l + 1, r + 1];
    if (sum < target) l++;
    else r--;
  }
  return [];
}

Tradeoff: O(1) space — the sortedness lets you converge without a hash map. This is the merge-join's primitive.

Snowflake-specific tips

Snowflake interviewers want you to recognize that sortedness changes the optimal algorithm — same input data, different algorithm. Bonus signal: explain when their planner picks merge-join over hash-join (sorted inputs from clustered storage, memory pressure, skewed keys).

Common mistakes

  • Reusing the unsorted Two Sum hash-map solution and violating the O(1) space.
  • Off-by-one with 1-indexed output — easy to forget the +1.
  • Comparing numbers[l] < numbers[r] when you should compare sum to target.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Three Sum (LC 15) — generalizes this with an outer loop.
  • Two-pointer Two Sum on a BST.
  • When does merge-join beat hash-join in Snowflake's planner?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does two-pointer work here but not on unsorted input?

Sortedness guarantees that moving left up increases sum and moving right down decreases sum, so each comparison eliminates one possibility — that's the monotonicity that makes two-pointer correct.

When does Snowflake choose merge-join?

When both inputs are already sorted on the join key (e.g., from clustered storage), or when memory is tight enough that hash-join would spill. Merge-join is also more resilient to key skew.

Practice these live with InterviewChamp.AI

Drill Two Sum II - Input Array Is Sorted and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →