Pairs Within a Shifted Gap

Hard

You are given two integer arrays first and second of the same length n and an integer slack. Return the number of index pairs (i, j) with 0 ≤ i < j ≤ n - 1 such that first[i] - first[j] ≤ second[i] - second[j] + slack. Checking all pairs in O(n²) is too slow for n up to 10⁵.

Example 1

first=[4, 1, 6], second=[1, 1, 3], slack=0 → 2

Pair (0, 1): 4 − 1 = 3 versus 1 − 1 + 0 = 0, no. Pair (0, 2): −2 ≤ −2, yes. Pair (1, 2): −5 ≤ −2, yes. That makes 2.

Example 2

first=[2, 2, 2], second=[1, 2, 3], slack=1 → 2

The left side is always 0. The right side is 0 for (0, 1), −1 for (0, 2) and 0 for (1, 2). Pairs (0, 1) and (1, 2) qualify.

Example 3

first=[0, 5], second=[0, 0], slack=-6 → 0

Constraints

n == len(first) == len(second)
2 ≤ n ≤ 10⁵
-10⁴ ≤ first[i], second[i] ≤ 10⁴
-10⁴ ≤ slack ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

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

Similar problems

Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Triples Both Rankings Agree On Hard

Input

first=[4, 1, 6], second=[1, 1, 3], slack=0

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.