Two Sum II (Sorted Input)
Easy About 10 min Free, no account needed
Two Sum again - but the array is sorted, and that changes everything.
The brief
Given an integer array numbers sorted in ascending order and a target,
return the indices (0-based, ascending) of the two values that add up to
target.
- Exactly one valid answer exists; an element may not be used twice.
The obvious approach is the same O(n2) double loop that plain Two Sum starts with; it ignores the sort entirely. The hidden test has 200,000 elements with the answer at the far end, so it's too slow. You need O(n), and the input already being sorted is the lever, ideally with no extra memory.
Starter code
using System;
public class Solution
{
// TODO: return the indices (ascending) of the two values summing to target. Input is sorted.
public int[] TwoSumSorted(int[] numbers, int target)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
Related katas
- Happy Number Easy Free Does repeatedly summing squared digits reach 1 - and how do you KNOW it will not?
- Merge Sorted Arrays Easy Free Merge two sorted arrays into one - without destroying what makes them special.
- Move Zeroes Easy Free Push all zeros to the end while keeping the other values in order.
- Remove Duplicates From Sorted Array Easy Free Deduplicate a sorted array without forgetting that it is sorted.