Google | Onsite | Number of Pairs Sum Greater or Equal Target
7746

Given a sorted list of numbers and a target Z, return the number of pairs according to following definition: (X,Y) where X+Y >= Z

Example 1:

Input: arr = [1, 3, 7, 9, 10, 11], Z = 7
Output: 14
My java solution
public static int countPairs(int[] arr, int target) {
    int count = 0;
    for (int lo = 0, hi = arr.length - 1; lo < hi; ) {
        if (arr[lo] + arr[hi] >= target) {
            count += hi - lo;
            hi--;
        } else  {
            lo++;
        }
    }
    return count;
}
Comments (15)