Number of Pairs Satisfying Inequality - Practice Coding Problems

Number of Pairs Satisfying Inequality - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

You are given two 0-indexed integer arrays nums1 and nums2, each of size n, and an integer diff. Find the number of pairs (i, j) such that:

0 <= i < j <= n - 1 and
nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

Return the number of pairs that satisfy the conditions.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [3,2,5], nums2 = [2,1,1], diff = 1

› Output: 3

💡 Note: Check all pairs: (0,1): 3-2 ≤ 2-1+1 → 1 ≤ 2 ✓, (0,2): 3-5 ≤ 2-1+1 → -2 ≤ 2 ✓, (1,2): 2-5 ≤ 1-1+1 → -3 ≤ 1 ✓. All 3 pairs satisfy the condition.

Example 2 — No Valid Pairs

$ Input: nums1 = [3,2,5], nums2 = [2,1,1], diff = -1

› Output: 0

💡 Note: With diff = -1, none of the pairs satisfy the inequality: (0,1): 1 ≤ 1 ✗, (0,2): -2 ≤ 1 ✗, (1,2): -3 ≤ 0 ✗

Example 3 — Two Elements

$ Input: nums1 = [1,2], nums2 = [3,1], diff = 5

› Output: 1

💡 Note: Only one pair (0,1): 1-2 ≤ 3-1+5 → -1 ≤ 7 ✓. The pair satisfies the condition.

Constraints

n == nums1.length == nums2.length
1 ≤ n ≤ 10⁵
-10⁴ ≤ nums1[i], nums2[i] ≤ 10⁴
-10⁴ ≤ diff ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays nums1, nums2 and difference value diff

Transform

Rearrange inequality to work with difference arrays

Count

Find number of valid pairs satisfying the condition

Key Takeaway

🎯 Key Insight: Transform the inequality algebraically to use efficient divide-and-conquer counting

Asked in

G Google 15 M Microsoft 12 f Facebook 8 a Amazon 6

The key insight is to transform the inequality by rearranging terms to create a difference array, then use merge sort to efficiently count valid pairs. The optimal approach uses merge sort with counting to achieve O(n log n) time complexity instead of the brute force O(n²) approach.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all possible pairs (i,j) where i < j
Merge Sort with Counting	O(n log n)	O(n)	Transform inequality and use merge sort to count inversions efficiently

Brute Force — Algorithm Steps

Iterate through all pairs (i,j) with i < j
Check inequality condition for each pair
Count pairs that satisfy the condition

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Initialize arrays and difference value

Check Pairs

For each pair (i,j), evaluate inequality

Count

Count valid pairs that satisfy condition

Code -

solution.c — C

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

int solution(int* nums1, int* nums2, int n, int diff) {
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    int nums1[1000], nums2[1000];
    int n1 = 0, n2 = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums1[n1++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums2[n2++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int diff;
    scanf("%d", &diff);
    
    printf("%d\n", solution(nums1, nums2, n1, diff));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n(n-1)/2 pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters

✓ Linear Space

23.4K Views

Medium Frequency

~35 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler