Pair Sum in Sorted Arrays Algorithm

The pair sum problem in sorted arrays is a classic algorithmic challenge where we need to find all pairs of elements that sum to a target value efficiently. This solution demonstrates the optimal two-pointer approach with O(n) time complexity and O(1) space complexity.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size range of the input array? (e.g., up to 10^6 elements)
2. Are duplicates allowed in the input array? If so, how should they be handled?
3. What format should the result take? (e.g., return indices, return boolean, return all pairs)
4. Can we modify the input array during processing?
5. What is the target time complexity for follow-up? (e.g., O(n) vs O(n log n))

Restatement of the pattern: The pair sum in sorted arrays pattern involves finding two elements in a sorted array that sum to a target value. This is a classic two-pointer technique where we leverage the sorted property to efficiently search for pairs without needing nested loops.

Signal words and constraint shape:

• "sorted array" or "given sorted input"
• "find two elements that sum to target"
• "return indices" or "return boolean"
• "array is already sorted" (implying we don't need to sort first)
• "two sum" or "pair sum" in problem title

Assumptions made:

• The input array is sorted in ascending order
• We're looking for exactly one pair (or all pairs) that sum to target
• Array elements can be negative, zero, or positive
• We can modify the input array if needed (though we'll avoid this when possible)

Scenario fit: This pattern is best suited for static scenarios where the entire input is available upfront and we're looking for a fixed relationship between pairs of elements. It's not ideal for streaming data where new elements arrive continuously, as we'd need to rebuild our search structure each time.

The pattern works because the sorted property allows us to use a two-pointer approach that systematically eliminates possibilities, making it more efficient than checking every pair combination.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Given a sorted array" or "array is already sorted"
• "Find two elements that sum to target"
• "Return indices" or "return values"
• "Exactly one valid answer exists"
• "Array may contain duplicates"

Why this pattern fits better than alternatives: This pattern leverages the sorted property to achieve O(n) time complexity, whereas a brute force approach would require O(n²) time. Compared to hash map approaches (which work on unsorted arrays), this method is more space-efficient and takes advantage of the inherent ordering.

Conditions where variations apply:

• For unsorted arrays, use hash map approach with O(n) time and space
• For finding all pairs (not just one), use three-pointer technique or hash set approach
• For k-sum problems, extend to k pointers or recursive approach

Core insight: The key insight is that in a sorted array, we can use two pointers (left and right) to efficiently explore all potential pairs while maintaining the sorted property. If the current sum is too small, we move the left pointer right to increase the sum; if too large, we move the right pointer left to decrease the sum. This greedy approach works because the array is sorted and we're guaranteed exactly one valid answer.

The pattern is ideal for static scenarios where the array is already sorted and we're looking for a specific pair sum relationship. It's not suitable for streaming data where the array is constantly changing, or when we need to find all valid pairs rather than just one solution.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible pair in the array, which would be O(n²) time complexity. But that's inefficient because I'm doing redundant work - for each element, I'm checking all subsequent elements even though the array is sorted. Let me think about how to optimize this.

I notice that if I maintain a two-pointer invariant, I can reduce it to O(n) time by leveraging the sorted property. Specifically, if I have a left pointer at the start and right pointer at the end of the array, I can compare their sum to the target. If the sum is too small, I move the left pointer right to increase the sum; if it's too large, I move the right pointer left to decrease the sum. This works because the array is sorted, so moving pointers in a specific direction maintains the necessary ordering.

The key insight is that since the array is already sorted, I don't need to check all combinations. Instead, I can systematically eliminate possibilities by moving my pointers based on the comparison between current sum and target.

Brute-force approach: The naive approach would be to check every pair (i,j) where i < j, compute their sum, and compare with target. This gives O(n²) time complexity and O(1) space complexity. It's not ideal because it doesn't leverage the sorted nature of input array and performs redundant computations.

Improved approach: I can use two pointers technique starting from both ends of the sorted array. This reduces time complexity to O(n) by taking advantage of the sorted property and avoiding redundant pair checking.

Final approach with step-by-step reasoning:

1. Initialize left pointer at index 0 and right pointer at last index
2. While left < right:
   • Calculate sum of elements at left and right pointers
   • If sum equals target, we found our answer
   • If sum is less than target, move left pointer right to increase sum
   • If sum is greater than target, move right pointer left to decrease sum
3. Continue until pointers meet or cross

Important invariants that must hold:

• Left pointer always stays to the left of right pointer (left < right)
• At each step, we either find a match or eliminate one element from consideration
• The sorted property ensures that moving pointers in the correct direction maintains valid search space reduction

4. Data Structure Choice

For the pair sum in sorted arrays problem, the primary data structure is a two-pointer approach using the input array itself.

Primary Data Structures Used

1. Input Array (int[])

   • Used directly for the sorted array input
   • No additional space needed for storage beyond input
   • Allows O(1) access to elements by index

2. Two Integer Pointers (int left, int right)

   • left pointer starts at index 0
   • right pointer starts at the last index (length - 1)
   • These serve as the primary working variables for the two-pointer technique

Why Each Data Structure Is Needed

The input array is essential because:

• It's the sorted input that enables the two-pointer optimization
• We can leverage the ordering property to eliminate search space efficiently
• No additional array allocation is needed since we're only reading elements

The two pointers are critical because:

• They maintain the invariant that we're always examining pairs from both ends of the sorted array
• They allow us to move toward the target sum by either increasing or decreasing our current sum
• They provide O(1) space complexity while maintaining O(n) time complexity

Time and Space Impact

• Time Complexity: O(1) additional space for the two pointers (constant extra space)
• Space Complexity: O(1) overall - only using a constant amount of extra memory beyond the input array
• No additional data structures are needed, making this approach highly space-efficient

Helper Structure

No helper structures are required beyond the two pointers. The algorithm works entirely with the existing array elements and maintains its own state through pointer movement.

This minimal data structure approach is optimal for this problem since we're only looking for a pair of indices that sum to the target, not storing any intermediate results or additional data.

5. Algorithm Walkthrough

Let me trace through the two-pointer approach with a concrete example:

Example: nums = [2, 7, 11, 15], target = 9

Step-by-step execution:

1. Initialization:

   • left = 0 (points to 2)
   • right = 3 (points to 15)

2. First iteration:

   • Sum = nums[0] + nums[3] = 2 + 15 = 17
   • Since 17 > 9, we move right pointer left: right = 2
   • Now left = 0, right = 2

3. Second iteration:

   • Sum = nums[0] + nums[2] = 2 + 11 = 13
   • Since 13 > 9, we move right pointer left: right = 1
   • Now left = 0, right = 1

4. Third iteration:

   • Sum = nums[0] + nums[1] = 2 + 7 = 9
   • Since 9 == 9, we found our answer!
   • Return indices [0, 1]

Key observations:

• The algorithm maintains the invariant that left < right throughout execution
• At each step, we either move left pointer forward (to increase sum) or right pointer backward (to decrease sum)
• Because the array is sorted, we can safely eliminate portions of the search space
• The algorithm terminates when either a match is found or pointers cross

Edge case handling:

• If the array has fewer than 2 elements, we return empty result
• If no pair sums to target, we return empty result
• The algorithm handles duplicate values correctly since we're looking for any valid pair

public List<Integer> twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left < right) {
        int currentSum = nums[left] + nums[right];
        if (currentSum == target) {
            return Arrays.asList(left, right);
        } else if (currentSum < target) {
            left++; // Need larger sum, move left pointer right
        } else {
            right--; // Need smaller sum, move right pointer left
        }
    }
    
    return new ArrayList<>(); // No pair found
}

6. Java Solution

public class PairSumInSortedArray {
    
    /**
     * Find if there exists a pair of elements in sorted array that sum to target
     * Uses two-pointer technique for O(n) time and O(1) space
     * 
     * @param nums sorted array of integers
     * @param target sum to find
     * @return true if pair exists, false otherwise
     */
    public boolean hasPairWithSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            
            if (currentSum == target) {
                return true;
            } else if (currentSum < target) {
                // Sum is too small, move left pointer right to increase sum
                left++;
            } else {
                // Sum is too large, move right pointer left to decrease sum
                right--;
            }
        }
        
        return false;
    }
    
    /**
     * Find the actual pair of elements that sum to target
     * Returns array containing the two elements, or null if none exists
     * 
     * @param nums sorted array of integers
     * @param target sum to find
     * @return array containing the pair, or null if no such pair exists
     */
    public int[] findPairWithSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return null;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            
            if (currentSum == target) {
                return new int[]{nums[left], nums[right]};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return null;
    }
    
    /**
     * Find all pairs that sum to target (returns list of pairs)
     * 
     * @param nums sorted array of integers
     * @param target sum to find
     * @return list of pairs that sum to target
     */
    public List<int[]> findAllPairsWithSum(int[] nums, int target) {
        List<int[]> result = new ArrayList<>();
        
        if (nums == null || nums.length < 2) {
            return result;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            
            if (currentSum == target) {
                result.add(new int[]{nums[left], nums[right]});
                left++;
                right--;
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
}

7. Complexity Analysis

Time Complexity: O(n)

The two-pointer approach processes each element at most once. The left pointer starts at index 0 and moves right, while the right pointer starts at the last index and moves left. Since each pointer can only move in one direction and each element is visited at most once, the total number of operations is linear in the size of the input array.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space for the two pointers (left and right) and the result variable. No additional data structures are created that scale with input size, making it space-efficient.

Why These Bounds Are Correct:

The linear time complexity stems from the fact that we never revisit elements once they've been considered by either pointer. Each iteration of the while loop processes exactly one element from either end, ensuring that we make progress toward convergence. The space complexity is constant because we're only using a fixed number of variables regardless of input size.

Optimality:

This solution is optimal for the problem as stated. Since we must examine each element at least once to determine if any pair sums to the target, O(n) time complexity is the theoretical lower bound. The solution achieves this bound exactly, making it near-optimal for the given constraints.

The algorithm's efficiency comes from leveraging the sorted nature of the input array to eliminate the need for nested loops or additional data structures, achieving both optimal time and space complexity.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: The algorithm should handle nums.length == 0 gracefully, returning an empty result or throwing an appropriate exception
• Single element: When nums.length == 1, no valid pairs can be formed, so the solution must handle this case
• Two elements: This is a valid edge case that should be tested - the only possible pair exists at indices 0 and 1

Duplicate Values and Repeated States

• Duplicate numbers: When the array contains duplicates, the algorithm must correctly identify all valid pairs that sum to target
• Duplicate pairs: If multiple pairs have the same elements (e.g., nums = [1, 2, 2, 3], target = 4), ensure the solution handles them consistently
• Same element twice: When nums[i] + nums[i] == target, this is valid but requires careful handling in the two-pointer approach

Boundary Conditions

• Integer overflow: When nums[i] + nums[j] might exceed Integer.MAX_VALUE or go below Integer.MIN_VALUE
• Index bounds: Ensure that left < right and array indices don't go out of bounds
• Target value extremes: Very large or very small target values that might cause issues with the two-pointer logic

Common Implementation Mistakes

• Incorrect pointer movement: Moving the wrong pointer when sum equals target (should move both to avoid missing pairs)
• Off-by-one errors: Forgetting to include the last element or processing elements twice
• Not handling negative numbers properly: The two-pointer approach assumes sorted array, but doesn't handle all negative number combinations correctly without proper bounds checking
• Modifying input array: If the problem requires preserving the original array, ensure the solution doesn't mutate it
• Missing edge case in loop condition: Using left <= right instead of left < right can cause infinite loops or duplicate processing

Testing Strategy

The solution should be tested with:

1. Empty array: [] with target = 0
2. Single element: [5] with target = 10
3. Two elements: [2, 7] with target = 9
4. Array with duplicates: [1, 2, 2, 3] with target = 4
5. Negative numbers: [-1, 0, 1, 2] with target = 1
6. Large numbers: [Integer.MAX_VALUE - 1, 1] with target = Integer.MAX_VALUE
7. All same elements: [3, 3, 3, 3] with target = 6

9. Alternative Approaches

There are several alternative approaches to solving the pair sum problem in sorted arrays, each with different trade-offs:

1. Hash Set Approach (O(n) time, O(n) space): Instead of using two pointers, we can iterate through the array once and for each element check if (target - current_element) exists in a hash set. This approach works for both sorted and unsorted arrays but requires additional space.

2. Binary Search Approach (O(n log n) time, O(1) space): For each element in the array, we can perform a binary search for (target - current_element) in the remaining portion of the array. This is efficient in terms of space but increases time complexity due to the binary search operations.

3. Brute Force with Early Termination (O(n²) time, O(1) space): A simple nested loop approach where we check all pairs. We can optimize by breaking early when we exceed the target sum, but this still remains O(n²) in worst case.

4. Three Pointer Technique (for 3-sum): When extending to finding triplets that sum to target, we can use a three-pointer approach where one pointer is fixed and two pointers move from both ends.

The chosen two-pointer technique is preferred because it's optimal for the sorted array case, achieving O(n) time with O(1) space complexity. The hash set approach is better when the array isn't sorted, while binary search works well for unsorted arrays but with higher time complexity. The brute force approach should be avoided due to its quadratic complexity.

The two-pointer approach is particularly effective because it leverages the sorted nature of the input array to eliminate unnecessary comparisons, making it more efficient than alternatives that don't take advantage of the sorted property.

10. Test Cases

public class PairSumTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic valid case
        int[] arr1 = {1, 2, 3, 4, 5};
        int target1 = 6;
        // Expected: [1, 4] or [2, 3] - any valid pair
        
        // Test case 2: No valid pairs
        int[] arr2 = {1, 2, 3};
        int target2 = 10;
        // Expected: null or empty result
        
        // Test case 3: Duplicate values
        int[] arr3 = {1, 2, 2, 3, 4};
        int target3 = 4;
        // Expected: [1, 3] or [2, 2] - any valid pair
        
        // Test case 4: Negative numbers
        int[] arr4 = {-2, 0, 1, 3, 5};
        int target4 = 3;
        // Expected: [-2, 5] or [1, 2] - any valid pair
        
        // Test case 5: Empty array
        int[] arr5 = {};
        int target5 = 5;
        // Expected: null or empty result
        
        // Test case 6: Single element array
        int[] arr6 = {5};
        int target6 = 10;
        // Expected: null or empty result
        
        // Test case 7: Target equals zero with negative/positive pairs
        int[] arr7 = {-3, -1, 0, 1, 3};
        int target7 = 0;
        // Expected: [-3, 3] or [-1, 1] - any valid pair
        
        // Test case 8: Large numbers
        int[] arr8 = {1000000, 2000000, 3000000};
        int target8 = 4000000;
        // Expected: [1000000, 3000000]
    }
}

Sample Test Cases:

1. Basic valid case: arr = [1,2,3,4,5], target = 6 → Expected: [1,4] or [2,3]
2. No valid pairs: arr = [1,2,3], target = 10 → Expected: null/empty result
3. Duplicate values: arr = [1,2,2,3,4], target = 4 → Expected: [1,3] or [2,2]
4. Negative numbers: arr = [-2,0,1,3,5], target = 3 → Expected: [-2,5] or [1,2]
5. Edge case - empty array: arr = [], target = 5 → Expected: null/empty result

Tricky case:

• arr = [-3,-1,0,1,3], target = 0 → Valid pairs: [-3,3] or [-1,1]

Boundary case:

• arr = [5], target = 10 → No valid pairs since array has only one element

11. Final Summary

The core idea is to leverage the sorted property of the array to efficiently find pairs that sum to a target value using the two-pointer technique, achieving linear time complexity. This solution works because we can systematically eliminate possibilities by moving pointers based on the current sum comparison with the target, making it both optimal and intuitive for sorted input arrays.

The efficiency comes from avoiding nested loops by maintaining the invariant that we only move pointers when we know the current pair cannot be valid, resulting in O(n) time and O(1) space complexity. This approach is superior to brute force methods that would require O(n²) time, and it's more efficient than hash-based solutions for sorted arrays where we can take advantage of the ordering property.