Introduction

The Pair Sum in Sorted Array problem involves checking whether there exists a pair of elements whose sum equals a given target value.

Given a sorted array arr[] and an integer target, the task is to determine whether any pair exists such that:

 arr[i] + arr[j] = target

This problem helps in understanding:

  •  Two Pointer Technique
  • sorted array optimization
  • pair searching
  • efficient traversal logic
Example
Input: arr[] = [1,2,4,6,10]target = 8
Output: true
Explanation:
2 + 6 = 8
Therefore, valid pair exists.

Input: arr[] = [1,3,5,7]
target = 12
Output: true
Explanation:
5 + 7 = 12

Constraints

 1 <= n <= 10^5-10^9 <= arr[i] <= 10^9
-10^9 <= target <= 10^9
Array is sorted

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all possible pairs
  2. Calculate their sum
  3. Check whether the sum equals target

This approach is easy to understand but checking all pairs increases time complexity.

Steps

  1. Traverse the array using index i.
  2. For every index:
    • traverse remaining elements using j
  3. Calculate pair sum.
  4. If sum equals target:
    • return true
  5. Otherwise:
    • continue traversal

Dry Run

Input Array: [1,2,4,6,10]target = 8Check 1 + 2:
Sum = 3
Not equal to target
Check 1 + 4:
Sum = 5
Check 2 + 6:
Sum = 8
Target found
Return true

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Every possible pair is checked.

Space Complexity: O(1)
Explanation:
No extra data structures are used.


Approach 2 : Optimized Solution (Two Pointer Technique)

Explanation

Since the array is already sorted, we can use the Two Pointer Technique.

The idea is:

  1. Place:
    • left pointer at beginning
    • right pointer at end
  2. Calculate current sum.
  3. If:
    • sum == target:
      • pair found
    • sum < target:
      • move left pointer
    • sum > target:
      • move right pointer

This avoids unnecessary pair generation.

Steps

  1. Initialize:
    • left = 0
    • right = n - 1
  2. While left < right:
    • calculate current sum
  3. If sum equals target:
    • return true
  4. If sum smaller than target:
    • move left pointer
  5. If sum greater than target:
    • move right pointer
  6. If traversal ends:
    • return false

Dry Run

Input Array: [1,2,4,6,10]target = 8

Initially:
left = 0 → 1
right = 4 → 10

Current Sum:
1 + 10 = 11
11 > 8
Move right pointer
right = 3 → 6

Current Sum:
1 + 6 = 7
7 < 8
Move left pointer
left = 1 → 2

Current Sum:
2 + 6 = 8
Target found
Return true

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each pointer moves at most once.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Edge Cases

  1. No valid pair exists
  2. Multiple valid pairs exist
  3. Array contains duplicates
  4. Array contains negative numbers
  5. Target equals sum of extreme elements

Why This Problem is Important

This problem helps in understanding:

  1. Two Pointer Technique
  2. Sorted array optimization
  3. Pair searching logic
  4. Pointer movement strategy
  5. Efficient traversal

It is one of the most important beginner-level two pointer interview problems.

Real-World Applications

Pair searching concepts are used in:

  1. Financial transaction systems
  2. Recommendation engines
  3. Search optimization
  4. Matching algorithms
  5. Analytics systems

Common Mistakes

  1. Moving wrong pointer
  2. Forgetting sorted property
  3. Incorrect loop conditions
  4. Wrong sum calculations

Interview Tips

Interviewers often expect:

  1. O(n) solution
  2. Two Pointer optimization
  3. Proper pointer movement explanation

Always explain why sorted arrays allow efficient pair searching.

Related Questions

  1. Two Sum
  2. Three Sum
  3. Container With Most Water
  4. Remove Duplicates II
  5. Trapping Rain Water

Final Takeaway

The Pair Sum in Sorted Array problem is a fundamental two pointer problem that teaches efficient pair searching and pointer movement strategies. Understanding this problem builds a strong foundation for advanced traversal and optimization interview problems.