How do you find two numbers that sum to k in a rotated sorted array?

The 30 second answer

A hash set solves it in one pass with linear time and space. To use constant space, I find the rotation point with binary search, which is the index of the smallest element. Then I run the usual two-pointer search, starting at the smallest and the largest elements and moving the pointers around the array with modulo arithmetic. That keeps linear time and constant extra space.

Reported. A 2022 Zalando backend candidate got this in the final coding round. They gave a hash-map solution first, then the two-pointer version with binary search for the rotation point, and wrote working code in a shared document.

Approach 1: hash set. For each value x, check whether k - x was seen, then add x. O(n) time, O(n) space, and it works on any array.

Approach 2: constant space. A sorted array rotated at an unknown point is still sorted if you start reading at its smallest element.

Find the smallest element with binary search: if a[mid] > a[hi], the minimum is to the right of mid; otherwise it is at mid or to its left. That is O(log n) when the values are distinct.
Two pointers on the circle: l starts at the smallest element and r just before it, at the largest. If the sum is too small, move l forward; if too large, move r back, both modulo n. Stop when they meet. O(n) time, O(1) space.

import java.util.*;

public class RotatedTwoSumShow {
    // Index of the smallest element in a rotated sorted array of distinct values: O(log n).
    static int minIndex(int[] a) {
        int lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] > a[hi]) lo = mid + 1;   // the minimum is to the right of mid
            else hi = mid;                      // mid could be the minimum
        }
        return lo;
    }

    // Two pointers that wrap around the rotation point: O(n) time, O(1) extra space.
    static int[] pairWithSum(int[] a, int k) {
        int n = a.length;
        if (n < 2) return null;
        int l = minIndex(a);              // smallest
        int r = (l - 1 + n) % n;          // largest
        while (l != r) {
            int sum = a[l] + a[r];
            if (sum == k) return new int[] {a[l], a[r]};
            if (sum < k) l = (l + 1) % n;
            else r = (r - 1 + n) % n;
        }
        return null;
    }

    public static void main(String[] args) {
        int[] a = {11, 15, 26, 38, 9, 10};
        System.out.println(Arrays.toString(pairWithSum(a, 35)));   // 9 + 26
        System.out.println(Arrays.toString(pairWithSum(a, 45)));   // none
        System.out.println(Arrays.toString(pairWithSum(new int[] {1, 2, 3, 4}, 7)));  // not rotated

    }
}

Verified with OpenJDK 21.0.13: it prints [9, 26], null and [3, 4]. A brute-force cross-check on 10,000 random rotated arrays found no mismatch.

Follow-ups to expect.

Duplicates: when a[mid] == a[hi], binary search cannot tell which side holds the minimum, so step hi back by one. The worst case becomes O(n), which still fits inside the O(n) total.
Count all pairs, or return indices: keep moving both pointers after a match; return positions instead of values.
Which to choose: say the hash set is simpler and fine unless memory matters, then offer the constant-space version. Interviewers usually want both and the trade-off.

Sources (2)