493. Reverse Pairs

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort
Leetcode Link

Problem Description

The problem requires us to find the number of reverse pairs in an integer array nums. A reverse pair is defined by a pair of indices (i, j) where i is less than j and the element at the i-th position of the array is more than twice the element at the j-th position. In other words, we need to count the number of times where nums[i] > 2 * nums[j] for 0 <= i < j < nums.length.

Intuition

This problem is a variant of the classic "counting inversions" problem, which is a common problem in sorting and can be solved by a modified merge-sort algorithm. However, in this case, due to the condition nums[i] > 2 * nums[j], we cannot directly apply a standard merge-sort approach.

The intuition behind the solution is to use a data structure that enables us to efficiently update and query the number of elements that meet the reverse pair criteria. A Binary Indexed Tree (BIT), which is also known as a Fenwick Tree, or a Segment Tree could be used for this purpose. These structures allow us to perform both update and query operations in logarithmic time, which is ideal for problems like this one where we have range query requirements and update needs.

The core of the solution is to iterate over the elements in reverse, and for each element, query how many elements before it are considered to be in a reverse pair with it (using the BIT or Segment Tree to do this efficiently). Finally, we update our data structure with the current element to account for future queries. We also preprocess the elements to create a mapping of elements to their ranks (as indices in BIT or Segment Tree) because these data structures typically require zero-based or continuous indexing.

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：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution approach involves using a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to efficiently count the reverse pairs. The BIT is a data structure that allows us to perform get and update prefix sums in logarithmic time complexity. Here's a step-by-step breakdown of how the solution works:

  1. Preprocessing:

    • We create a set of unique values twice - once with all current elements and once with their double value. This step is important to avoid dealing with the potential issue of large values in the BIT.
    • We then sort these values to assign a rank or index to each distinct value. The use of indexing is crucial because BITs operate on indices, and this also helps compress the values to a smaller range.

  2. Mapping:

    • A mapping is created from the actual value in the array to the rank/position in our sorted set. This allows us to translate the elements of our original array to the indices that we'll use in the BIT, as BITs are index-based.

  3. BIT Initialization:

    • We initialize our BIT with the number of unique ranks as its size.

  4. Iterating and Updating BIT:

    • We iterate through the original array in reverse order.
    • For each element num, we perform a query (get prefix sum) operation for m[num] - 1 on our BIT. This gives us the count of reverse pairs found so far for that particular element.
      • The reason for querying m[num] - 1 is to get the count of all the elements that are less than the current element num. Since we're querying in reverse, this would give us the number of previous elements that num could form a reverse pair with.
    • Next, we update our BIT with m[num * 2], incrementing the count at this rank/index, preparing for future queries that might pair with double the current element.

  5. Return Answer:

    • The variable ans is updated at every iteration with the result of each query, cumulatively storing the total number of reverse pairs. After iterating through all the elements, ans contains the final count of reverse pairs, which we return.

By leveraging the BIT, the time complexity is reduced to O(nlogn), as both updates and queries to the BIT are O(logn). This is in contrast to a brute force solution that would be O(n^2) due to nested loops for comparing elements.

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

To illustrate the solution approach, let's consider a small example with the integer array nums = [5, 3, 1, 2].

Step 1: Preprocessing

First, we need to consider all the elements and their double value:

  • Original elements: [5, 3, 1, 2]
  • Double values: [10, 6, 2, 4]

Combine and remove duplicates: [5, 3, 1, 2, 10, 6, 4]

Next, we sort these values to determine the rank of each one:

  • Sorted: [1, 2, 3, 4, 5, 6, 10]

Step 2: Mapping

We map each original value to its rank in the sorted array:

  • 1 -> 0
  • 2 -> 1
  • 3 -> 2
  • 5 -> 4

Step 3: BIT Initialization

Initialize a BIT with a length equal to the number of unique values (7 in this case).

Step 4: Iterating and Updating BIT

Now iterate through nums in reverse order, and for each element num:

  1. Perform a BIT query to get the count of elements less than num (ranking-wise). These counts correspond to the number of reverse pairs found for that element.
  2. Update the BIT with the double of num to prepare for future queries.

Let's walk through the steps:

  • Starting with element 2:

    • Perform BIT query for elements less than 2 (which is of rank 1): BIT_query(0) – found 0 pairs.
    • Update BIT with 4 (the double of 2, which is of rank 3): BIT_update(3, 1).

  • Next, 1:

    • Perform BIT query for elements less than 1 (which is of rank 0): BIT_query(-1) – found 0 pairs. (Note: querying -1 effectively means we are looking for nothing, thus always 0)
    • Update BIT with 2 (the double of 1, which is of rank 1): BIT_update(1, 1).

  • Then, 3:

    • Perform BIT query for elements less than 3 (which is of rank 2): BIT_query(1) – found 1 pair (previously updated by 1).
    • Update BIT with 6 (the double of 3, which is of rank 5): BIT_update(5, 1).

  • Finally, 5:

    • Perform BIT query for elements less than 5 (which is of rank 4): BIT_query(3) – found 1 pair (previously updated by 2).
    • Update BIT with 10 (the double of 5, which is not in the array but would be of the last rank 6): BIT_update(6, 1).

Step 5: Return Answer

  • The variable ans is updated at every iteration with the result of each query, which are 0, 0, 1, and 1, respectively, so ans = 2. After completing the iteration, we return ans as the total count of reverse pairs, which is 2 for this example.

The answers derived in this walkthrough correspond to the pairs (i, j) such that nums[i] > 2 * nums[j]: (2, 1) and (3, 1) (note that the indices are based on 0-indexing).

Solution Implementation

1# Import the List type from the typing module for type hints.
2from typing import List
3
4# Define the BinaryIndexedTree class for performing efficient 
5# frequency queries and updates on an array.
6class BinaryIndexedTree:
7    # Initialize the binary indexed tree with size n.
8    def __init__(self, n: int):
9        self.size = n
10        self.tree_array = [0] * (n + 1)
11
12    # Define a static method to get the lowest set bit of a number.
13    @staticmethod
14    def lowbit(x: int) -> int:
15        return x & -x
16
17    # Update method for increasing the value at index x by 'delta'.
18    def update(self, x: int, delta: int):
19        while x <= self.size:
20            self.tree_array[x] += delta
21            x += BinaryIndexedTree.lowbit(x)
22
23    # Query method to calculate the prefix sum up to index x.
24    def query(self, x: int) -> int:
25        sum_ = 0
26        while x > 0:
27            sum_ += self.tree_array[x]
28            x -= BinaryIndexedTree.lowbit(x)
29        return sum_
30
31
32# Define the Solution class which will use the BinaryIndexedTree to solve problems.
33class Solution:
34    # The reversePairs function counts the number of important reverse pairs in nums.
35    def reversePairs(self, nums: List[int]) -> int:
36        all_values = set()  # Use a set to store all unique numbers and their double.
37      
38        # Populate the set with each number and its double.
39        for num in nums:
40            all_values.add(num)
41            all_values.add(num * 2)
42      
43        # Sort and enumerate the unique values starting from index 1.
44        sorted_values = sorted(all_values)
45        index_mapping = {value: index for index, value in enumerate(sorted_values, 1)}
46      
47        # Initialize the answer counter to 0.
48        ans = 0
49        tree = BinaryIndexedTree(len(index_mapping))
50      
51        # Iterate through nums in reverse order.
52        for num in reversed(nums):
53            # Query the tree to find how many numbers are smaller than num.
54            ans += tree.query(index_mapping[num] - 1)
55            # Update the tree to indicate another number that is double the current number.
56            tree.update(index_mapping[num * 2], 1)
57      
58        # Return the final count of important reverse pairs.
59        return ans
60
1public class Solution {
2    // A method for reversing pairs in the array and returning the count
3    public int reversePairs(int[] nums) {
4        // TreeSet to store unique numbers and their double values
5        TreeSet<Long> treeSet = new TreeSet<>();
6        for (int num : nums) {
7            treeSet.add((long) num);
8            treeSet.add((long) num * 2);
9        }
10
11        // Mapping each unique number to its index position
12        Map<Long, Integer> indexMapping = new HashMap<>();
13        int index = 0;
14        for (long num : treeSet) {
15            indexMapping.put(num, ++index);
16        }
17
18        // Using a Binary Indexed Tree (Fenwick Tree) for maintaining prefix sums
19        BinaryIndexedTree binaryIndexedTree = new BinaryIndexedTree(indexMapping.size());
20      
21        // The count of reverse pairs
22        int count = 0;
23      
24        // Traverse the array from right to left
25        for (int i = nums.length - 1; i >= 0; --i) {
26            int x = indexMapping.get((long) nums[i]);
27            // Query the count of elements smaller than the current number
28            count += binaryIndexedTree.query(x - 1);
29            // Update the count of elements which are double the current number
30            binaryIndexedTree.update(indexMapping.get((long) nums[i] * 2), 1);
31        }
32        return count; // Return the total count of the reverse pairs
33    }
34}
35
36// Class representing the Binary Indexed Tree (Fenwick Tree)
37class BinaryIndexedTree {
38    private int size; // Size of the tree
39    private int[] tree; // Actual tree represented as an array
40
41    // Constructor to initialize the tree with the given size
42    public BinaryIndexedTree(int size) {
43        this.size = size;
44        tree = new int[size + 1]; // One extra index for easier calculations
45    }
46
47    // Method to update the tree with the given value (delta) at the given index (x)
48    public void update(int index, int delta) {
49        while (index <= size) {
50            tree[index] += delta; // Add delta to the current index
51            index += lowbit(index); // Move to the next index that needs to be updated
52        }
53    }
54
55    // Method to query the prefix sum up to the given index (x)
56    public int query(int index) {
57        int sum = 0;
58        while (index > 0) {
59            sum += tree[index]; // Add the value at the current index to sum
60            index -= lowbit(index); // Move to the parent index
61        }
62        return sum;
63    }
64
65    // Utility method to calculate the lowest bit (-x) of a number (x)
66    public static int lowbit(int x) {
67        return x & -x;
68    }
69}
70
1#include <vector>
2#include <set>
3#include <unordered_map>
4using namespace std;
5
6class BinaryIndexedTree {
7public:
8    int size;
9    vector<int> tree_array;
10
11    // Constructor to initialize the Binary Indexed Tree with a given size
12    BinaryIndexedTree(int _size)
13        : size(_size)
14        , tree_array(_size + 1) {}
15
16    // Increment the value at index x in the Binary Indexed Tree by 'delta'
17    void update(int x, int delta) {
18        while (x <= size) {
19            tree_array[x] += delta;
20            x += lowbit(x); // Go to the next index to update
21        }
22    }
23
24    // Compute the prefix sum up to index x
25    int query(int x) {
26        int sum = 0;
27        while (x > 0) {
28            sum += tree_array[x]; // Add the value at index x to the sum
29            x -= lowbit(x); // Move to the previous index
30        }
31        return sum;
32    }
33
34    // Helper function to get the lowest bit of the binary representation of x
35    int lowbit(int x) {
36        return x & -x;
37    }
38};
39
40class Solution {
41public:
42    int reversePairs(vector<int>& nums) {
43        set<long long> all_numbers;
44        // Store each number and its double in the set to normalize the values
45        for (int num : nums) {
46            all_numbers.insert(num);
47            all_numbers.insert(static_cast<long long>(num) * 2);
48        }
49      
50        unordered_map<long long, int> value_to_index;
51        int index = 0;
52        // Assign a unique index to each number in the normalized set
53        for (long long num : all_numbers) value_to_index[num] = ++index;
54
55        // Instantiate a Binary Indexed Tree with the normalized index size
56        BinaryIndexedTree tree(m.size());
57        int pairs_count = 0; // Initialize pairs counter
58      
59        // Iterate over the numbers from the end to the beginning
60        for (int i = nums.size() - 1; i >= 0; --i) {
61            // Query the number of elements less than current number.
62            pairs_count += tree.query(value_to_index[nums[i]] - 1);
63            // Update the BIT with the current number's double
64            tree.update(value_to_index[static_cast<long long>(nums[i]) * 2], 1);
65        }
66      
67        return pairs_count; // Return the final count of reverse pairs
68    }
69};
70
1// Define the size of the binary indexed tree
2let size: number;
3// An array to represent the binary indexed tree
4let treeArray: number[];
5
6// Function to initialize the Binary Indexed Tree with a given size
7function initializeBIT(_size: number): void {
8  size = _size;
9  treeArray = new Array(_size + 1).fill(0);
10}
11
12// Function to increment the value at index `x` in the Binary Indexed Tree by `delta`
13function update(x: number, delta: number): void {
14  while (x <= size) {
15    treeArray[x] += delta;
16    x += lowbit(x); // Go to the next index to update
17  }
18}
19
20// Function to compute the prefix sum up to index `x`
21function query(x: number): number {
22  let sum = 0;
23  while (x > 0) {
24    sum += treeArray[x]; // Add the value at index `x` to `sum`
25    x -= lowbit(x); // Move to the previous index
26  }
27  return sum;
28}
29
30// Helper function to get the lowest bit of the binary representation of `x`
31function lowbit(x: number): number {
32  return x & -x;
33}
34
35// Function to count the reverse pairs in the array `nums`
36function reversePairs(nums: number[]): number {
37  const allNumbers = new Set<number>();
38  // Store each number and its double in the set to normalize the values
39  nums.forEach(num => {
40    allNumbers.add(num);
41    allNumbers.add(num * 2);
42  });
43
44  const valueToIndex = new Map<number, number>();
45  let index = 0;
46  // Assign a unique index to each number in the normalized set
47  allNumbers.forEach(num => {
48    valueToIndex.set(num, ++index);
49  });
50
51  // Instantiate a Binary Indexed Tree with the normalized index size
52  initializeBIT(allNumbers.size);
53  let pairsCount = 0; // Initialize pairs counter
54
55  // Iterate over the numbers from the end to the beginning
56  for (let i = nums.length - 1; i >= 0; --i) {
57    // Query the number of elements less than the current number
58    pairsCount += query(valueToIndex.get(nums[i])! - 1);
59    // Update the BIT with the current number's double
60    update(valueToIndex.get(nums[i] * 2)!, 1);
61  }
62
63  return pairsCount; // Return the final count of reverse pairs
64}
65
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The given Python code implements a solution to count reverse pairs in an array using a Binary Indexed Tree (also known as a Fenwick Tree). Let's analyze its time and space complexity:

Time Complexity

  1. Initialization: Creating the BinaryIndexedTree object takes O(n) time as it initializes self.c with n+1 zeros.

  2. Creating set and sorting:

    • Adding every num and num*2 to the set s takes O(n) time, where n is the number of elements in nums.
    • The sorted(s) function then sorts the unique elements, which takes O(u log u) time, where u represents the number of unique elements (after considering both num and num*2 for every num).

  3. HashMap Creation: Creating the hashmap m (to assign ranks) takes O(u) given that u is the number of elements in alls.

  4. Loop Through nums and Update Tree:

    • The for loop iterates n times since it enumerates all elements in nums.
    • Inside the loop, the tree.query function calls take O(log n) time each (because the range of the Binary Indexed Tree is based on the number of unique elements u, and u can be at most 2n).
    • The tree.update function is also called within the loop which similarly takes O(log n) time per call.

    Therefore:

    • The time for all the queries is O(n log n).
    • The time for all the updates is also O(n log n).

If n is the number of elements in the input nums and u is the number of unique elements after considering both num and num*2, the overall time complexity is O(n + u log u + u + n log n). Since u can be at most 2n, the time complexity simplifies to O(n log n).

Space Complexity

  1. Space for the BinaryIndexedTree: The tree uses an array of size n+1 for storing the cumulative frequencies which results in O(n) space complexity.

  2. Space for Set and HashMap: The set and hashmap together take up O(u) space where u is the number of unique elements after considering both num and num*2.

  3. Space for Sorted List: The sorted call produces a sorted list of all unique elements which occupies O(u) space.

Since u can be at most 2n, the overall space complexity of the code is O(n) (since O(n + u) simplifies to O(n) if u <= 2n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

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 👨‍🏫