Count the Number of Fair Pairs - Practice Coding Problems

Count the Number of Fair Pairs - Problem

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6

› Output: 6

💡 Note: Valid pairs: (0,3)→4, (0,4)→4, (0,5)→5, (1,3)→5, (1,4)→5, (1,5)→6. All sums are between 3 and 6 inclusive.

Example 2 — No Valid Pairs

$ Input: nums = [1,7,9,2,5], lower = 11, upper = 11

› Output: 1

💡 Note: Only one pair sums to 11: (2,3) where nums[2]=9 and nums[3]=2, giving 9+2=11.

Example 3 — All Pairs Valid

$ Input: nums = [1,2,3], lower = 3, upper = 5

› Output: 3

💡 Note: All pairs are valid: (0,1)→3, (0,2)→4, (1,2)→5. Each sum is in range [3,5].

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i], lower, upper ≤ 10⁹
lower ≤ upper

Visualization

Tap to expand

Understanding the Visualization

Input

Array with lower and upper bounds for pair sums

Process

Find all pairs whose sum falls in the given range

Output

Count of valid pairs

Key Takeaway

🎯 Key Insight: Sorting the array enables efficient range queries using binary search or two pointers, reducing time from O(n²) to O(n log n)

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to sort the array first, which enables efficient partner finding using binary search or two pointers. Instead of checking all O(n²) pairs, we can find valid partner ranges in O(log n) per element. Best approach is Sort + Binary Search with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Optimization	O(n log n)	O(1)	Sort array, then use two pointers to efficiently count pairs in valid range
Sort + Binary Search	O(n log n)	O(1)	Sort array first, then for each element use binary search to count valid partners
Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair (i,j) where i < j and count those with sum in [lower, upper]

Two Pointers Optimization — Algorithm Steps

Sort the array
For each element nums[i]
Use left pointer to find first valid partner (≥ lower - nums[i])
Use right pointer to find last valid partner (≤ upper - nums[i])
Count valid partners between pointers

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Enable pointer-based range finding

Set Pointers

Left pointer finds first valid partner, right finds last

Count Range

All elements between pointers are valid partners

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int lower, int upper) {
    qsort(nums, numsSize, sizeof(int), compare);
    int count = 0;
    
    for (int i = 0; i < numsSize - 1; i++) {
        long long targetLow = (long long)lower - nums[i];
        long long targetHigh = (long long)upper - nums[i];
        
        // Find leftmost j where nums[j] >= targetLow
        int left = i + 1;
        while (left < numsSize && nums[left] < targetLow) {
            left++;
        }
        
        // Find rightmost j where nums[j] <= targetHigh
        int right = numsSize - 1;
        while (right > i && nums[right] > targetHigh) {
            right--;
        }
        
        if (left <= right) {
            count += right - left + 1;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ']' && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int lower, upper;
    scanf("%d", &lower);
    scanf("%d", &upper);
    
    int result = solution(nums, numsSize, lower, upper);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n log n) for sorting + O(n) for two pointer traversal

⚡ Linearithmic

Space Complexity

O(1)

Only using two pointer variables and constants

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler