Pair Sum in a Sorted & Rotated Array takes the classic two-pointer trick and bends it around a rotation. The array was sorted, then spun, so it is no longer globally ordered — but if we walk the pointers circularly, the same elegant scan still works.
Problem. Given an array nums that was sorted in increasing order and then rotated at some
pivot, and an integer target, decide whether two distinct elements add up to target.
Example: nums = [11, 15, 6, 8, 9, 10], target = 16 → True (because 6 + 10 = 16). The underlying
sorted order is [6, 8, 9, 10, 11, 15], rotated so the smallest value 6 lands at index 2.
The slow way first
The obvious idea: try every pair with two nested loops and check whether any sums to the target. That works, but it is O(n²) — far too slow for a large array, and it throws away the fact that the data is almost sorted.
The question to ask: the array is sorted, just rotated — can I still use the linear-time two-pointer scan that solves the sorted version? In a plain sorted array you put one pointer at the smallest value and one at the largest, then close in. The only thing the rotation breaks is where the smallest and largest live — so first we just need to find them.
The idea: find the pivot, then walk in a circle
Do it in two moves. First, locate the pivot — the index of the smallest element (the rotation point). Second, set lo to the pivot (smallest value) and hi to pivot − 1 (largest value), and run the usual two-pointer scan, except the pointers move circularly using modulo: lo = (lo + 1) % n to grow the sum, hi = (n + hi − 1) % n to shrink it.
The key insight: in the rotated order, the value just after the pivot is the next-smallest, and the value just before it (wrapping around) is the next-largest. Moving lo forward circularly always increases the value; moving hi backward circularly always decreases it — exactly the monotonic behavior the two-pointer scan needs.
Walk through it
Step through the animation. We first mark the pivot at index 2 (value 6). Then lo sits on 6 and hi on 15. The sum 21 is too big, so hi walks backward across the wrap to 11, then to 10. Now 6 + 10 = 16 hits the target, and we stop.
Pseudocode
n = length of nums
find pivot = index of the smallest element # binary search in O(log n)
lo = pivot # smallest value
hi = (pivot - 1 + n) % n # largest value, wrapping around
while lo != hi:
s = nums[lo] + nums[hi]
if s == target: return True # found the pair
if s < target: lo = (lo + 1) % n # too small -> bigger value
else: hi = (n + hi - 1) % n # too big -> smaller value
return FalseThe Python solution
def pair_in_rotated(nums, target):
n = len(nums)
pivot = 0
for k in range(n):
if nums[k] < nums[pivot]:
pivot = k
lo = pivot
hi = (pivot - 1 + n) % n
while lo != hi:
s = nums[lo] + nums[hi]
if s == target:
return True
if s < target:
lo = (lo + 1) % n
else:
hi = (n + hi - 1) % n
return False- Lines 3-6 find the pivot: the index of the smallest value. Shown as a linear scan for clarity, but in a sorted-rotated array this is a binary search in O(log n).
lo = pivotanchors the smallest value;hi = (pivot - 1 + n) % nanchors the largest value (the index just before the pivot, wrapping past index 0).while lo != hiruns until the pointers collide — every element gets considered at most once.s < targetmeans we need a bigger sum, solosteps forward circularly to the next-larger value.s > target(theelse) means we need a smaller sum, sohisteps backward circularly to the next-smaller value.- The
% nwrap is what lets the pointers glide across the rotation seam without special-casing the ends.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every pair) | O(n²) (slow) | two nested loops |
| Pivot + circular two pointers | O(n) (moderate) | O(log n) pivot, O(n) scan |
O(1) (fast)Finding the pivot by binary search is O(log n), and the circular two-pointer scan touches each element at most once, so it is O(n) overall with O(1) extra space. That beats the O(n²) brute force while using no extra memory.
When this pattern shows up
Whenever an array is sorted then rotated, think: find the rotation point first, then reuse the ordinary sorted-array technique — but index everything modulo n so the pointers can wrap. The same find-pivot-then-scan move powers search, minimum-finding, and pair-sum problems on rotated arrays.
Mind the wrap arithmetic. To step hi backward use (n + hi - 1) % n, not (hi - 1) % n — in Python a
bare negative would still wrap, but adding n first keeps the index non-negative and the intent clear.
Also stop the loop on lo != hi so the two pointers never reuse the same element.
Practice
For nums = [11, 15, 6, 8, 9, 10] with lo at value 6 and hi at value 15, the sum is 21. The target is 16. Which pointer moves, and to what value?
1. Why do plain two pointers from the literal ends of the array fail here?
2. Where do lo and hi start?
3. When the running sum is greater than the target, what happens?
4. What is the overall time and space complexity?