Pair with given sum in a sorted array

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Check if sorted array has pair summing to target.

See our study guide for structured GFG and LeetCode practice.

Intuition

Check if sorted array has pair summing to target. Two pointers.

Algorithm

1Left=0, right=n-1. If sum==target: found. If sum<target: left++. If sum>target: right--.

Common Pitfalls

• Classic two-pointer on sorted array. O(n). Same as LC 167.

Pair with given sum in a sorted array.java

Java

// Approach: Two pointers starting from both ends. Move left right if sum < target, move right left if sum > target.
// Time: O(n) Space: O(1)
class Solution {

    int countPairs(int arr[], int target) {
        int st = 0;
        int ed = arr.length - 1;
        int count = 0;
        while (st < ed) {
            int sum = arr[st] + arr[ed];
            if (sum < target)
                st++;
            else if (sum > target)
                ed--;
            else {
                int cnt1 = 0, cnt2 = 0;
                int elem1 = arr[st], elem2 = arr[ed];
                while (st <= ed && arr[st] == elem1) {
                    cnt1++;
                    st++;
                }
                while (st <= ed && arr[ed] == elem2) {
                    cnt2++;
                    ed--;
                }
                if (elem1 == elem2)
                    count += (cnt1 * (cnt1 - 1)) / 2;
                count += (cnt1 * cnt2);
            }
        }
        return count;
    }
}

Was this solution helpful?