Pair with given sum in a sorted array

JavaView on GFG

Time: O(n)

Space: O(1)

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?