Introduction

The Two Sum in Sorted Array problem involves finding two numbers in a sorted array whose sum is equal to a given target value.

Given a sorted array arr[] and an integer target, the task is to find two elements such that:

 arr[i] + arr[j] = target

This is one of the most important Two Pointer Technique problems and helps in understanding:

  • pair-based searching
  • sorted array optimization
  • pointer movement logic
  • efficient traversal techniques

Example

Input: arr[] = [1, 2, 4, 6, 10]target = 8
Output: [2, 6]
Explanation:
2 + 6 = 8
Therefore, the required pair is:
[2, 6]

Input: arr[] = [2, 3, 5, 8, 11]
target = 14
Output: [3, 11]
Explanation:
3 + 11 = 14

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 repeated pair generation increases time complexity.

Steps

  1. Traverse the array using index i.
  2. For every index:
    • traverse remaining elements using j.
  3. Calculate:
    • arr[i]+arr[j]
  4. If sum equals target:
    • return the pair

Dry Run

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

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
Every possible pair is generated and 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:
      • move left pointer forward
    • sum > target:
      • move right pointer backward
    • sum == target:
      • pair found

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 pair
  4. If sum smaller than target:
    • move left pointer
  5. If sum greater than target:
    • move right pointer

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:
[2, 6]

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is processed at most once using two pointers.

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

Edge Cases

  1. Array contains negative numbers
  2. Multiple valid pairs exist
  3. No valid pair exists
  4. Array contains duplicate elements
  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-based searching
  4. Pointer movement logic
  5. Efficient traversal

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

Real-World Applications

Two pointer searching is used in:

  1. Financial transaction systems
  2. Recommendation systems
  3. Pair matching algorithms
  4. Data analysis systems
  5. Search optimization engines

Common Mistakes

  1. Incorrect pointer movement
  2. Forgetting sorted array property
  3. Infinite loop conditions
  4. Wrong sum calculations

Interview Tips

Interviewers often expect:

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

Always explain why sorted arrays make two pointer traversal possible.

Related Questions

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

Final Takeaway

The Two Sum in Sorted Array problem is a fundamental Two Pointer problem that teaches efficient pair searching and pointer movement techniques. Understanding this problem builds a strong foundation for advanced two pointer and sorted array interview problems.