Pair Sum in Sorted Array Algorithm Solution

The pair sum in sorted array problem requires finding two elements that add up to a target sum efficiently. This classic algorithm demonstrates the power of two-pointer techniques in sorted data structures.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected time complexity constraint? Are we looking for O(n) or O(n log n) solution?
2. Can we modify the input array, or must we preserve the original array?
3. What should we return if no valid pair exists? Should we return null or throw an exception?
4. Are there any constraints on the input array size (e.g., maximum 10^6 elements)?
5. Should we return indices or values of the pair?

Restated problem in my own words: Given a sorted array of integers and a target sum, find two distinct elements in the array whose sum equals the target. Return either their indices or values.

Clarified inputs, outputs, and constraints:

• Input: A sorted array of integers (ascending order) and a target integer sum
• Output: Two elements (or their indices) that sum to the target, or null/empty if no such pair exists
• Constraints: Array is sorted, array length can be up to 10^6 elements, elements can be negative, zero, or positive

Assumptions I'm making:

• The array is guaranteed to be sorted in ascending order
• We can return either the values or indices of the pair (I'll return values for simplicity)
• There exists at most one valid pair (or we return any valid pair if multiple exist)
• The array can be mutated if needed

Data shape and hidden structure: The key insight is that since the array is sorted, we can leverage the ordering property to avoid checking all possible pairs. This creates a "two-pointer" pattern where we can move pointers based on whether current sum is less than or greater than target, effectively reducing search space.

The sorted nature implies that:

• If we fix one element and want to find its complement, we can use binary search
• But since it's already sorted, we can do better with two pointers approach

2. Pattern Recognition

The most likely pattern here is the Two Pointers Technique.

The wording that signals this pattern includes:

• "Sorted array" - the sorted property is a key indicator for two-pointer approaches
• "Pair sum" - when looking for combinations that sum to a target value in a sorted structure, two pointers is often optimal
• "Return indices" - this suggests we need to track positions rather than just values

This problem fits the two-pointer pattern because:

1. We have a sorted array, which allows us to make directional decisions
2. We're looking for a specific sum relationship between elements
3. The sorted nature means we can eliminate search space efficiently by moving pointers

The core insight is that in a sorted array, if we have two pointers at the start and end of the array:

• If the current sum is less than target, we need a larger sum, so we move left pointer right
• If the current sum is greater than target, we need a smaller sum, so we move right pointer left
• If equal, we found our answer

This approach leverages the sorted property to systematically narrow down possibilities without needing to check all pairs.

The pattern is also reminiscent of the "Two Sum" problem family, but with the added constraint that we must return indices rather than just whether a pair exists.

This is not a binary search pattern because we're not searching for a single element, but rather finding a pair that satisfies a sum condition.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every pair of elements to see if they sum to the target, but that's O(n²) because for each element I'd need to scan all remaining elements. Let me think about how to optimize this.

I notice that the array is sorted, which is a key insight! This means I can use two pointers - one starting from the beginning and one from the end. If the sum is too large, I move the right pointer left to reduce the sum. If the sum is too small, I move the left pointer right to increase the sum.

This approach maintains the invariant that we're always looking at a valid range of elements that could potentially sum to our target. Since we never revisit elements and move pointers toward each other, we have at most O(n) operations.

Let me trace through this more carefully: if I have a sorted array and two pointers at positions i and j, where i < j, then:

• If nums[i] + nums[j] = target, we found our answer
• If nums[i] + nums[j] > target, we need a smaller sum, so we move j left (decrease the larger element)
• If nums[i] + nums[j] < target, we need a larger sum, so we move i right (increase the smaller element)

This is optimal because we process each element at most once, and we're leveraging the sorted property to avoid checking all pairs.

The key optimization here is recognizing that with a sorted array, we don't need to check all combinations - we can systematically narrow down our search space by moving pointers based on the comparison with target sum.

The final approach is to use two pointers from both ends of the sorted array, moving inward based on whether the current sum is greater than or less than the target. This gives us O(n) time and O(1) space complexity, which is optimal for this problem.

4. Data Structure Choice

For this problem, I'll use a two-pointer approach with the original array as my primary data structure.

Primary Data Structures:

• int[] - The input array itself, which is already sorted per problem constraints
  • Why needed: We need to access elements by index to implement the two-pointer technique
  • Time/Spatial impact: O(1) additional space for indices, O(n) for the array itself
  • No mutation required, so we can safely read from it

Why This Choice Is Optimal: The sorted nature of the input array allows us to use two pointers efficiently without requiring additional data structures like hash maps or sets. Since we're looking for a pair that sums to a target value, and the array is already sorted, we can leverage the ordering property to eliminate search space systematically.

Helper Structures:

• No additional helper data structures needed beyond the two integer pointers (left and right indices)
• The solution uses O(1) extra space for variables, which is optimal for this problem

This approach directly exploits the sorted property of the input array and avoids the need for any additional space to store intermediate results or mappings. The two-pointer technique is a classic pattern that works perfectly with sorted arrays, making it the ideal choice for this specific problem structure.

5. Algorithm Walkthrough

Let me trace through the two-pointer approach with the example array [1, 2, 3, 4, 5] and target sum 6.

Step 1: Initialize pointers - left = 0 (points to 1), right = 4 (points to 5)

Step 2: Calculate current sum = 1 + 5 = 6, which equals target sum

Step 3: Since we found a match, return indices [0, 4] or values [1, 5]

Let me trace through a case where no match exists: array [1, 2, 3, 4, 5] with target 10

Step 1: left = 0 (points to 1), right = 4 (points to 5) Step 2: Current sum = 1 + 5 = 6 < 10, so move left pointer right Step 3: left = 1 (points to 2), right = 4 (points to 5) Step 4: Current sum = 2 + 5 = 7 < 10, so move left pointer right Step 5: left = 2 (points to 3), right = 4 (points to 5) Step 6: Current sum = 3 + 5 = 8 < 10, so move left pointer right Step 7: left = 3 (points to 4), right = 4 (points to 5) Step 8: left = right, so we terminate without finding a match

The algorithm correctly handles both successful and unsuccessful cases. Edge cases like empty arrays or single elements are handled by the loop condition that requires left < right.

public int[] 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 new int[]{left, right};
        } else if (currentSum < target) {
            left++; // Need larger sum, move left pointer right
        } else {
            right--; // Sum too large, move right pointer left
        }
    }
    
    return new int[]{-1, -1}; // No pair found
}

6. Java Solution

public class PairSum {
    /**
     * Find two numbers in a sorted array that sum to the target.
     * Uses two pointers approach for O(n) time and O(1) space.
     * 
     * @param nums   sorted array of integers
     * @param target sum to find
     * @return       indices of the two numbers, or [-1, -1] if not found
     */
    public int[] twoSum(int[] nums, int target) {
        // Handle edge cases
        if (nums == null || nums.length < 2) {
            return new int[]{-1, -1};
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        // Two pointers approach - start from both ends
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            
            if (currentSum == target) {
                return new int[]{left, right};
            } else if (currentSum < target) {
                // Sum too small, move left pointer right to increase sum
                left++;
            } else {
                // Sum too large, move right pointer left to decrease sum
                right--;
            }
        }
        
        // No pair found
        return new int[]{-1, -1};
    }
}

The solution uses the classic two-pointer technique on a sorted array. Since the array is guaranteed to be sorted, we can efficiently search for pairs by maintaining pointers at both ends and moving them based on whether the current sum is too small or too large. This approach avoids the need for additional space and achieves optimal linear time complexity.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses the two-pointer technique where each element is visited at most once by either the left or right pointer. Since we move either left++ or right-- in each iteration and the pointers start at opposite ends, we have at most n iterations where n is the length of the array. Each operation inside the loop (comparisons and arithmetic) takes constant time, making the overall time complexity linear.

Space Complexity: O(1)

The solution only uses a constant amount of extra space for the two integer variables left and right, plus a constant number of temporary variables for comparisons. No additional data structures like arrays, hash maps, or stacks are required, making the space complexity constant.

Why These Bounds Are Correct:

The linear time complexity is optimal for this problem because we must examine each element at least once to determine if any pair sums to the target. Since the array is already sorted, we cannot do better than O(n) time complexity. The constant space complexity follows from the fact that we're only maintaining a fixed number of pointers and variables regardless of input size.

The solution is optimal because:

1. We cannot do better than O(n) time since we need to examine elements
2. We cannot use less than O(1) space since we only have constant state to maintain
3. The algorithm achieves both optimal time and space complexity simultaneously

This makes the solution near-optimal for the constraints given.

8. Edge Cases & Pitfalls

Edge cases that require careful handling:

Empty input and single element arrays:

• Empty array should return no valid pairs (return empty result or handle appropriately)
• Single element array cannot form any pairs, so return empty result
• These cases should be handled before entering the main logic to avoid index out of bounds errors

Duplicate values in array:

• The algorithm must correctly handle duplicate elements
• When duplicates exist, multiple valid pairs may be possible
• The solution should return all valid combinations, not just unique sums

Boundary conditions:

• When target sum equals the smallest possible sum (first two elements)
• When target sum equals the largest possible sum (last two elements)
• When target sum is outside the valid range of sums that can be formed

Common implementation pitfalls:

• Off-by-one errors in loop conditions when using two pointers
• Not properly handling the case where left and right pointers meet
• Incorrectly incrementing/decrementing pointers after finding a match
• Failing to account for the fact that we want all pairs, not just one pair

Integer overflow considerations:

• When summing large integers, ensure proper handling to avoid overflow
• Though not a primary concern for this specific problem, it's worth noting in production code

Return format consistency:

• Ensure that the returned pairs maintain consistent ordering (e.g., always return smaller element first)
• Handle cases where the same pair might be found in different orders

The solution must guard against these edge cases to ensure correctness across all valid inputs.

9. Alternative Approaches

There are several alternative approaches to solving the pair sum problem in a sorted array, 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 its complement (target - current_element) exists in a HashSet. This approach works for both sorted and unsorted arrays but requires additional space.

public boolean hasPairWithSum(int[] arr, int target) {
    Set<Integer> seen = new HashSet<>();
    for (int num : arr) {
        if (seen.contains(target - num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

2. Binary Search Approach (O(n log n) time, O(1) space) For each element in the array, perform a binary search for (target - current_element). This approach maintains the sorted property requirement but increases time complexity due to repeated binary searches.

public boolean hasPairWithSum(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];
        if (binarySearch(arr, i + 1, arr.length - 1, complement)) {
            return true;
        }
    }
    return false;
}

private boolean binarySearch(int[] arr, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

3. Three-Pointer Approach (O(n²) time, O(1) space) If we want to find all pairs rather than just checking existence, we could use three pointers - one fixed, and two moving from both ends. This is less efficient than our chosen approach but handles the case where we need to return actual pairs.

The two-pointer approach is preferred because it's optimal for the specific problem requirements - O(n) time and O(1) space while maintaining simplicity and readability. The hash set approach is better when we need to handle unsorted arrays or want to find all pairs rather than just checking existence.

10. Test Cases

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

Sample Test Case Analysis:

Basic Valid Case: {2, 7, 11, 15}, target=9 → Expected: [0, 1]
No Valid Pair: {1, 2, 3, 4}, target=10 → Expected: null
Duplicate Values: {2, 2, 3, 4}, target=4 → Expected: [0, 1]
Single Element: {5}, target=10 → Expected: null
Empty Array: {}, target=0 → Expected: null
Negative Numbers: {-1, 0, 1, 2}, target=1 → Expected: [0, 3]
Boundary Case: {1, 2, 3, 4}, target=7 → Expected: [2, 3]
Large Numbers: {1000000, 2000000}, target=3000000 → Expected: [0, 1]

These test cases cover all major edge conditions including empty inputs, single elements, duplicates, negative numbers, and boundary value scenarios. The solution should handle all these cases correctly while maintaining O(n) time complexity.

11. Final Summary

The core idea is to leverage the sorted property of the input array to efficiently find if any two elements sum to the target using the two-pointer technique. This approach works because we can systematically eliminate impossible candidates by moving pointers based on whether the current sum is too large or too small, rather than checking all possible pairs.

The solution is optimal with O(n) time and O(1) space complexity, making it significantly better than the brute force O(n²) approach. The key insight is that in a sorted array, we can use the ordering property to guide our search and avoid redundant comparisons.

What makes this solution efficient is the combination of:

• Early termination when target sum is found
• Constant space usage by avoiding hash maps or additional data structures
• Linear time complexity by making one pass through the array with two pointers
• Clear invariants maintained throughout the algorithm (left pointer only moves right, right pointer only moves left)