2426. Number of Pairs Satisfying Inequality

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort
Leetcode Link

Problem Description

In this problem, we are given two 0-indexed integer arrays nums1 and nums2, both of the same size n. We are also given an integer diff. Our goal is to find the number of pairs (i, j) that satisfy two conditions:

  1. The indices i and j are within the bounds of the arrays, and i is strictly less than j (that is, 0 <= i < j <= n - 1).
  2. The difference nums1[i] - nums1[j] is less than or equal to the difference nums2[i] - nums2[j] plus diff. In other words, the difference between the elements at positions i and j in nums1 is not greater than the difference between the corresponding elements in nums2 when diff is added to it.

We are asked to return the number of pairs that satisfy these conditions.

Intuition

The naive approach to solve this problem would be to check every possible pair (i, j) and count the number of pairs that satisfy the second condition. However, this approach would have a time complexity of O(n^2), which is inefficient for large arrays.

Instead, a more efficient solution is to use a Binary Indexed Tree (BIT), also known as a Fenwick Tree. This data structure is useful for problems that involve prefix sums, especially when the array is frequently updated.

The intuition behind the solution is to transform the second condition into a format that can be handled by BIT. Instead of directly comparing each pair (i, j), we can compute a value v = nums1[i] - nums2[i] for each element i and update the BIT with this value. When processing element j, we query the BIT for the number of elements i such that v = nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff. This simplifies the problem to counting the elements that have a value less than or equal to a certain value.

To accomplish this, the BIT needs to be able to handle both positive and negative index values. As such, a normalization step is added to map negative values to positive indices in the BIT.

The final solution iterates over the array only once, and for each element j, we get the count of valid i's using the BIT, which has O(log n) time complexity for both update and query operations. The result is a more efficient solution with a time complexity of O(n log n).

Learn more about Segment Tree, Binary Search, Divide and Conquer and Merge Sort patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Solution Approach

The code solution uses a Binary Indexed Tree (BIT) to manage the frequencies of the differences between the nums1 and nums2 elements. Here's a step-by-step walkthrough of the implementation:

  1. Initialization: Create a Binary Indexed Tree named tree which has a size that can contain all possible values after normalization (to take care of negative numbers).

  2. Normalization: A fixed number (40000, in this case) is added to all the indices to handle negative numbers, as BIT cannot have negative indices. This supports the update and query operations with negative values by shifting the index range.

  3. Update Procedure: For every element a in nums1 and b in nums2, calculate the difference v = a - b. Then, update the BIT (tree) with v - effectively counting this value.

  4. Query Procedure: For the same values a and b, the query will search for the count of all values in the BIT that are less than or equal to v + diff. This is because we're looking for all previous indices i, where nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

  5. Collecting Results: The query method returns the count of valid i indices leading up to the current index j, satisfying our pairs condition. This count is added to our answer ans for each j.

  6. Lowbit Function: A method named lowbit is defined statically in the BinaryIndexedTree class. It is used to calculate the least significant bit that is set to 1 for a given number x. In the context of the BIT, this function helps in navigating to parent or child nodes during update and query operations.

The BIT handles frequencies of indices that correspond to the differences within nums1 and nums2. Instead of re-computing the differences between nums1 and nums2 elements exhaustively, we leverage the BIT's ability to efficiently count the elements so far that satisfy the given constraint relative to the current element being considered.

Overall, this approach takes advantage of the BIT's efficient update and query operations, leading to an O(n log n) time complexity, which is a dramatic improvement over the naive O(n^2) approach.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following:

  • nums1 = [1, 4, 2, 6]
  • nums2 = [3, 1, 3, 2]
  • diff = 2

Follow these steps to understand how the solution works:

  1. Initialization: A Binary Indexed Tree (tree) would be created, but for simplicity in this example, we'll just mention it has been initialized and can handle the range of differences we'll encounter after normalization.

  2. Normalization: We normalize differences by adding 40000 to indices to deal with possible negative numbers. (The numbers themselves won't change, just how we index them in the BIT.)

  3. Update Procedure: We compute the differences for each element in nums1 and nums2:

    • For i=0: v = nums1[0] - nums2[0] = 1 - 3 = -2 (after normalization, index is -2 + 40000 = 39998)
    • Update tree at index 39998.

    We'll repeat this for each element i.

  4. Query Procedure: When examining each element j, we look for how many indices i have a difference v = nums1[i] - nums2[i] such that v <= nums1[j] - nums2[j] + diff.

    • For j=1: v = nums1[1] - nums2[1] = 4 - 1 = 3, so we query the tree for how many indices have a difference <= 3 + diff (remembering to normalize if necessary).

    We repeat this for each element j, moving forward through the arrays.

  5. Collecting Results:

    • For j=1, we query the tree and find there is 1 valid i (from index 0 with normalized difference 39998), so ans += 1.
    • We then move to j=2 and repeat the steps, updating the tree and querying for the range of valid i.

  6. Lowbit Function: (Explained in a general sense, as it’s a bit abstract for a concrete example.)

After iterating through all the elements in nums1 and nums2, we would have found all pairs (i, j) where i < j and nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. In this case, let's say we found two pairs that satisfy the conditions: (0, 1) and (0, 3), then our ans would be 2.

This walkthrough with a small example gives us a glimpse of how the BIT is used to efficiently manage and query the cumulative differences between the two arrays, optimizing the solution to an O(n log n) time complexity.

Solution Implementation

1class BinaryIndexedTree:
2    def __init__(self, n):
3        self.size = n
4        self.tree_array = [0] * (n + 1)  # Initializing the BIT with n+1 elements
5
6    @staticmethod
7    def lowbit(x):
8        # Static method to get the largest power of 2 that divides x
9        return x & -x
10
11    def update(self, index, delta):
12        # Convert the original index range to 1-based for BIT operations
13        index += 40000
14        while index <= self.size:
15            self.tree_array[index] += delta  # Update the tree_array by adding delta
16            index += BinaryIndexedTree.lowbit(index)  # Move to the next index to update
17
18    def query(self, index):
19        # Similar conversion to 1-based index
20        index += 40000
21        sum = 0
22        while index:
23            sum += self.tree_array[index]  # Sum the elements in the tree_array
24            index -= BinaryIndexedTree.lowbit(index)  # Move to the next index to query
25        return sum
26
27
28class Solution:
29    def numberOfPairs(self, nums1, nums2, diff):
30        tree = BinaryIndexedTree(10**5)  # Initialize the Binary Indexed Tree with a given size
31        count_pairs = 0
32        for a, b in zip(nums1, nums2):
33            value = a - b
34            count_pairs += tree.query(value + diff)  # Count pairs with difference less or equal to diff
35            tree.update(value, 1)  # Update the Binary Indexed Tree
36        return count_pairs
37
1class BinaryIndexedTree {
2    private int size; // Size of the original array
3    private int[] tree; // The Binary Indexed Tree array
4
5    // Constructor to initialize the Binary Indexed Tree with a given size
6    public BinaryIndexedTree(int size) {
7        this.size = size;
8        tree = new int[size + 1]; // Since the BIT indices start at 1
9    }
10
11    // Method to compute the least significant bit (LSB)
12    public static final int lowbit(int x) {
13        return x & -x;
14    }
15
16    // Update method for the BIT, increments the value at index x by delta
17    public void update(int x, int delta) {
18        while (x <= size) {
19            tree[x] += delta; // Increment the value at index x
20            x += lowbit(x); // Move to the next index to update
21        }
22    }
23
24    // Query method for the BIT, gets the prefix sum up to index x
25    public int query(int x) {
26        int sum = 0;
27        while (x > 0) {
28            sum += tree[x]; // Add the value at index x to the sum
29            x -= lowbit(x); // Move to the previous sum index
30        }
31        return sum;
32    }
33}
34
35class Solution {
36    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
37        // Initialize a Binary Indexed Tree with a sufficient range to cover possible values
38        BinaryIndexedTree tree = new BinaryIndexedTree(100000);
39        long ans = 0; // Variable to store the count of valid pairs
40      
41        // Loop through elements in the given arrays
42        for (int i = 0; i < nums1.length; ++i) {
43            int v = nums1[i] - nums2[i]; // Calculate the difference of elements at the same index
44            // Query the BIT for the count of elements that are at most 'v + diff' plus offset to handle negative indices
45            ans += tree.query(v + diff + 40000);
46            // Update the BIT to increment the count for the value 'v' with an offset to handle negative indices
47            tree.update(v + 40000, 1);
48        }
49      
50        return ans; // Return the total count of valid pairs
51    }
52}
53
1#include <vector>
2
3using std::vector;
4
5// BinaryIndexedTree supports efficient updating of frequencies
6// and querying of prefix sums.
7class BinaryIndexedTree {
8public:
9    int size;                  // Size of the array
10    vector<int> treeArray;     // Tree array
11
12    // Constructor initializes the Binary Indexed Tree with the given size.
13    BinaryIndexedTree(int size)
14        : size(size), treeArray(size + 1, 0) {}
15
16    // Updates the tree with the given value 'delta' at position 'index'.
17    void update(int index, int delta) {
18        while (index <= size) {
19            treeArray[index] += delta;
20            index += lowBit(index); // Move to the next index to be updated
21        }
22    }
23
24    // Queries the cumulative frequency up to the given position 'index'.
25    int query(int index) {
26        int sum = 0;
27        while (index > 0) {
28            sum += treeArray[index];
29            index -= lowBit(index); // Move to the previous index to continue the sum
30        }
31        return sum;
32    }
33
34private:
35    // Calculates and returns the least significant bit (low bit) of integer 'x'.
36    int lowBit(int x) {
37        return x & -x;
38    }
39};
40
41class Solution {
42public:
43    // Calculates the number of pairs of elements in nums1 and nums2 
44    // such that nums1[i] - nums2[i] is not greater than the given 'diff'.
45    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
46        const int offset = 40000; // Used to offset negative values for BIT
47        const int maxValue = 1e5; // Max value for which BIT is initialized
48      
49        // Initialize BinaryIndexedTree.
50        BinaryIndexedTree tree(maxValue);
51      
52        long long pairsCount = 0; // Initialize count of pairs
53      
54        // Loop through all elements
55        for (int i = 0; i < nums1.size(); ++i) {
56            int valueDifference = nums1[i] - nums2[i];
57          
58            // Query the cumulative frequency for the range [0, v + diff + offset]
59            pairsCount += tree.query(valueDifference + diff + offset);
60          
61            // Update the tree for 'valueDifference + offset' by 1
62            tree.update(valueDifference + offset, 1);
63        }
64      
65        // Returns the total count of valid pairs
66        return pairsCount;
67    }
68};
69
1// Type definition for the tree array
2type BinaryIndexedTreeArray = number[];
3
4let treeSize: number; // Size of the array
5let treeArray: BinaryIndexedTreeArray; // Tree array
6
7// Initializes the Binary Indexed Tree with the given size.
8function initializeBIT(size: number): void {
9    treeSize = size;
10    treeArray = Array(size + 1).fill(0);
11}
12
13// Updates the tree with the given value 'delta' at position 'index'.
14function updateBIT(index: number, delta: number): void {
15    while (index <= treeSize) {
16        treeArray[index] += delta;
17        index += lowBit(index); // Move to the next index to be updated
18    }
19}
20
21// Queries the cumulative frequency up to the given position 'index'.
22function queryBIT(index: number): number {
23    let sum = 0;
24    while (index > 0) {
25        sum += treeArray[index];
26        index -= lowBit(index); // Move to the previous index to continue summing
27    }
28    return sum;
29}
30
31// Calculates and returns the least significant bit (low bit) of integer 'x'.
32function lowBit(x: number): number {
33    return x & -x;
34}
35
36// Calculates the number of pairs of elements in nums1 and nums2
37// such that nums1[i] - nums2[i] is not greater than the given 'diff'.
38function numberOfPairs(nums1: number[], nums2: number[], diff: number): number {
39    const offset = 40000; // Used to offset negative values for BIT
40    const maxValue = 1e5; // Max value for which BIT is initialized
41
42    // Initialize BinaryIndexedTree
43    initializeBIT(maxValue);
44
45    let pairsCount: number = 0; // Initialize count of pairs
46
47    // Loop through all elements
48    for (let i = 0; i < nums1.length; i++) {
49        let valueDifference = nums1[i] - nums2[i];
50
51        // Query the cumulative frequency for the range [0, valueDifference + diff + offset]
52        pairsCount += queryBIT(valueDifference + diff + offset);
53
54        // Update the tree for 'valueDifference + offset' by 1
55        updateBIT(valueDifference + offset, 1);
56    }
57
58    // Returns the total count of valid pairs
59    return pairsCount;
60}
61
Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

The time complexity of the numberOfPairs method is O(n * log m), where n is the length of the nums1 and nums2 lists and m is the value after offsetting in the BinaryIndexedTree (10**5 in this case). The log m factor comes from the operations of the Binary Indexed Tree methods update and query, since each operation involves traversing up the tree structure which can take at most the logarithmic number of steps in relation to the size of the tree array c.

The space complexity of the code is O(m), where m is the size of the BinaryIndexedTree which is defined as 10**5. This is due to the tree array c that stores the cumulative frequencies, and it is the dominant term since no other data structure in the solution grows with respect to the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫