Two-sum on a sorted price ladder

Question

You are given an already sorted list of price levels and a target. Two of them should add up to the target exactly. Return the indices of any two distinct entries that sum to the target, or None if none exists. Use O(n) time and O(1) extra space.

Accepted Answer

Put one pointer at each end. If the pair sums above the target, the largest element is too big for any partner, so move the right pointer inward; if below, the smallest element is too small for any partner, so move the left pointer inward. Each step permanently discards one element, so the pointers meet in one pass. Tracing [1, 3, 4, 5, 7, 11], target 9: 1 + 11 = 12 9 so hi--; 1 + 7 = 8 < 9 so lo++; 3 + 7 = 10 9 so hi--; 3 + 5 = 8 < 9 so lo++; 4 + 5 = 9, return (2, 3). Time O(n), space O(1). This beats the hash-map version on space, but it only works because the input is sorted; if you had to…

Two-sum on a sorted price ladder

Your answer

More Coding questions