2935. Maximum Strong Pair XOR II

HardBit ManipulationTrieArrayHash TableSliding Window

Problem Description

In this problem, you have an array of integers, nums, with a 0-based index. Your task is to find out a pair of integers (x, y) from the array that forms a strong pair and has the maximum bitwise XOR value among all possible strong pairs. A strong pair is defined by a pair (x, y) where the absolute difference between the two numbers is less than or equal to the smaller of the two numbers. In other words, if x ≤ y, then y - x ≤ x. Additionally, you are allowed to select the same integer twice to form a pair if needed.

Intuition

The key point to the problem is the condition for a strong pair: |x - y| ≤ min(x, y). If we assume x ≤ y, which we can do without loss of generality, this simplifies to y - x ≤ x, or further to y ≤ 2x. This insight is the starting point for our solution: if we sort nums in ascending order, then for any given y we know that x must be in the range [y / 2, y] if (x, y) is to be a strong pair.

With the array sorted, we can iterate over it as potential y values for our strong pairs. As we consider each y, we maintain a 'window' of x values that are within the range [y / 2, y]. To quickly find the x that will maximize y XOR x, we can use a binary trie, also known as a prefix tree. Each node in the trie represents a bit position in the binary representation of numbers. As we add numbers to the trie, we increment a count at each node to know how many numbers have a particular bit set or unset.

As we iterate over potential y values, we insert y into the trie and then remove the leftmost (smallest) x values that no longer fall within the strong pair range relative to the current y. We can do this effectively by comparing the smallest x in the window with y / 2 and removing it if it's too small. After this, we query the trie for the maximum XOR value using the current y, which computes the maximum XOR by trying to pick the opposite bit at each level of the trie, and update our answer for the maximum XOR value seen so far.

By carefully maintaining our window and the trie, we ensure we only consider valid (x, y) pairs and can find the maximum XOR in O(1) time for each y we consider. This process ultimately provides us with the maximum XOR value for a strong pair in the array.

Learn more about Trie and Sliding Window patterns.

Solution Approach

The solution approach for maximizing the XOR of a strong pair involves sorting, binary trie, and a two-pointer technique. The implementation is done in the following way based on the given reference solution approach:

Sorting: To manage the x values efficiently and enforce the strong pair relationship y ≤ 2x, we start by sorting the nums array. This sorting makes it easy to iterate over potential y values and maintain the ‘window’ of x values within the specified range.
Binary Trie: A binary trie, which is a specialized data structure used to handle bitwise operations efficiently, is implemented to store integers' binary representations. It's a tree where each node's children represent whether a bit at a certain position in the binary representation of the numbers is 0 or 1. The binary trie supports three main operations:
- insert(x: int): Adds the binary representation of x to the trie, incrementing the counter at each node representing the presence of a bit.
- search(x: int) -> int: Finds the maximum XOR value obtainable with x and the numbers in the trie by traversing the trie and always choosing the opposite bit if possible, thus maximizing the XOR value.
- remove(x: int): Removes the binary representation of x from the trie, decrementing the counter at each node.
Maximizing XOR: With the trie built, each time a new y is considered, it's inserted into the trie. The maximum XOR is queried using search(y) after ensuring all numbers that cannot form a strong pair with the current y are removed—this is where the two-pointer technique comes into play.
Two-Pointer Technique: Two pointers are used to maintain the window of valid x values. One pointer runs over the array for potential y values. Another pointer, i, marks the start of the window where x values are valid for the current y. If the smallest x is too small for the current y (nums[i] * 2 < y), it's removed from the trie, and i is moved forward.

The combination of these techniques allows the algorithm to efficiently update the window and the trie to always contain valid x values for each y and calculate the maximum XOR in O(log max_num) time per number, where max_num is the maximum value in the input array. The log max_num factor comes from the maximum number of bits needed to represent the numbers in the binary trie.

Overall, by iterating through each number as a potential y, inserting it into the trie, maintaining the window of x values, and querying the trie for the maximum XOR, we're able to find the maximum XOR among all strong pairs in the array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example array of integers nums = [3, 8, 2, 5] to illustrate the solution approach.

Step 1: Sorting

First, we sort the array nums in ascending order, which will be [2, 3, 5, 8] after sorting.

Step 2: Binary Trie

Next, we set up a binary trie to keep track of binary bit patterns of our x values.

Step 3: Maximizing XOR

We now iterate over the sorted array to consider each number as a potential y value while using a two-pointer approach to maintain a window of x values.

For simplicity, let's assume we use a naive approach instead of a trie to find the maximum XOR for the current y by iterating over the current window of x values.

Step 4: Two-Pointer Technique

We start with y at index 0 and x window including numbers at and after index 0:

Current y is 2 and the window is [2, 3, 5, 8]. We find that the maximum XOR of 2 with these numbers is 2 XOR 3 = 1.

As we move y to index 1:

Now y is 3, and we update our window to [3, 5, 8]. The maximum XOR is 3 XOR 5 = 6.

Next y at index 2:

Now y is 5, and we discard 3 from our window since 3 * 2 < 5 (no longer a strong pair). The updated window is [5, 8]. We get 5 XOR 8 = 13 as the maximum.

Finally, with y at index 3:

y is 8, we discard 5 from our window since 5 * 2 < 8. The updated window only includes [8]. The maximum XOR in this case (8 XOR 8) remains 0 since we can choose the same number twice if needed.

Throughout this example, the maximum XOR value we found was 5 XOR 8 = 13. Note that in a real implementation, the trie would allow for much faster determination of the maximum XOR, and the window update would occur in O(1) time by effectively removing nodes from the trie when numbers no longer fall in the y/2 <= x <= y range.

As a result, we identify (5, 8) as the strong pair which gives us the maximum XOR of 13 in this case.

Solution Implementation

1from typing import List, Optional
2
3class Trie:
4    __slots__ = ("children", "count")
5
6    def __init__(self):
7        # Initialize each trie node with two possible children (for 0 and 1) and a counter
8        self.children: List[Optional['Trie']] = [None, None]
9        self.count = 0
10
11    def insert(self, number: int):
12        # Insert a number into the trie
13        node = self
14        for i in range(20, -1, -1):
15            bit = (number >> i) & 1
16            if node.children[bit] is None:
17                node.children[bit] = Trie()
18            node = node.children[bit]
19            node.count += 1  # Increment the counter for each node traversed
20
21    def search(self, number: int) -> int:
22        # Search for the maximum XOR pair for the given number
23        node = self
24        max_xor = 0
25        for i in range(20, -1, -1):
26            bit = (number >> i) & 1
27            opposite_bit = bit ^ 1
28            if node.children[opposite_bit] and node.children[opposite_bit].count:
29                max_xor |= 1 << i  # Set the corresponding bit in the resulting XOR
30                node = node.children[opposite_bit]
31            else:
32                node = node.children[bit]
33        return max_xor
34
35    def remove(self, number: int):
36        # Remove a number from the trie
37        node = self
38        for i in range(20, -1, -1):
39            bit = (number >> i) & 1
40            node = node.children[bit]
41            node.count -= 1  # Decrement the counter for each node traversed
42
43
44class Solution:
45    def maximumStrongPairXor(self, nums: List[int]) -> int:
46        nums.sort()
47        trie = Trie()
48        max_xor = 0
49        index = 0
50      
51        for y in nums:
52            trie.insert(y)
53            # Remove elements from the trie that do not satisfy the strong pair condition (y > 2 * nums[index])
54            while y > nums[index] * 2:
55                trie.remove(nums[index])
56                index += 1
57            # Update the maximum XOR with the current number y
58            max_xor = max(max_xor, trie.search(y))
59          
60        return max_xor
61

1class Trie {
2    private Trie[] children = new Trie[2]; // Trie children to represent binary digits 0 and 1
3    private int count = 0; // Variable to keep track of the presence of numbers
4
5    public Trie() {
6        // Constructor for initialization
7    }
8
9    // Function to insert a number into the Trie
10    public void insert(int number) {
11        Trie node = this;
12        // Starting from the 20th bit moving towards the least significant bit
13        for (int i = 20; i >= 0; --i) {
14            int bit = (number >> i) & 1; // Extract the bit at the current position
15            // If there is no Trie node for this bit, create one
16            if (node.children[bit] == null) {
17                node.children[bit] = new Trie();
18            }
19            node = node.children[bit]; // Move to the child node representing the current bit
20            ++node.count; // Increment the count at the current Trie node
21        }
22    }
23
24    // Function to find the maximum XOR with the given number
25    public int search(int number) {
26        Trie node = this;
27        int maximumXor = 0; // Store the result for maximum XOR value
28        // Iterate over the bits of the number
29        for (int i = 20; i >= 0; --i) {
30            int bit = (number >> i) & 1; // Extract the bit at the current position
31            // Check if the complementary bit exists and has a positive count
32            if (node.children[bit ^ 1] != null && node.children[bit ^ 1].count > 0) {
33                maximumXor |= 1 << i; // Set the bit in the answer to 1
34                node = node.children[bit ^ 1]; // Move to the child node having the complementary bit
35            } else {
36                node = node.children[bit]; // Otherwise move to the child node having the same bit
37            }
38        }
39        return maximumXor; // Return the calculated maximum XOR value
40    }
41
42    // Function to remove a number from the Trie
43    public void remove(int number) {
44        Trie node = this;
45        // Iterate over the bits of the number to remove it from the Trie
46        for (int i = 20; i >= 0; --i) {
47            int bit = (number >> i) & 1; // Extract the bit at the current position
48            node = node.children[bit]; // Move to the child node representing the current bit
49            --node.count; // Decrement the count at the current node
50        }
51    }
52}
53
54class Solution {
55    // Method to find the maximum XOR pair from the given array such that the second number is not more than twice the first
56    public int maximumStrongPairXor(int[] nums) {
57        Arrays.sort(nums); // Sort the input array
58        Trie trie = new Trie(); // Initialize a Trie
59        int result = 0; // Variable to store the result
60        int i = 0; // Initialize the pointer for the sliding window
61        for (int number : nums) {
62            trie.insert(number); // Insert the number into the Trie
63            // If the current number is more than twice the smallest number in the current sliding window, remove the smallest number
64            while (number > nums[i] * 2) {
65                trie.remove(nums[i++]);
66            }
67            // Update the result with the maximum XOR found so far
68            result = Math.max(result, trie.search(number));
69        }
70        return result; // Return the maximum XOR value found
71    }
72}
73

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Trie {
6public:
7    Trie* children[2]; // binary trie nodes for 0 and 1
8    int count; // count of numbers that have passed through this node 
9
10    Trie() : count(0) {
11        children[0] = nullptr;
12        children[1] = nullptr;
13    }
14
15    // Inserts an integer into the trie
16    void insert(int number) {
17        Trie* node = this;
18        for (int i = 20; i >= 0; --i) {
19            int bit = (number >> i) & 1; // extract the i-th bit of the number
20            if (node->children[bit] == nullptr) {
21                node->children[bit] = new Trie();
22            }
23            node = node->children[bit];
24            ++node->count; // increment the passage count
25        }
26    }
27
28    // Searches for the maximum XOR of an integer with the trie
29    int search(int number) {
30        Trie* node = this;
31        int max_xor = 0; // variable to store the maximum XOR value
32        for (int i = 20; i >= 0; --i) {
33            int bit = (number >> i) & 1;
34            // check if there is a complementary bit to maximize XOR
35            if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->count > 0) {
36                max_xor |= 1 << i; // update maximum XOR value
37                node = node->children[bit ^ 1]; // move to complementary bit if available
38            } else {
39                node = node->children[bit]; // else move to same bit
40            }
41        }
42        return max_xor; // return the maximum XOR found
43    }
44
45    // Removes an integer from the trie
46    void remove(int number) {
47        Trie* node = this;
48        for (int i = 20; i >= 0; --i) {
49            int bit = (number >> i) & 1;
50            node = node->children[bit];
51            --node->count; // decrement the passage count
52        }
53    }
54};
55
56class Solution {
57public:
58    // Finds the maximum XOR of two distinct elements in the array such that the second element is not greater than twice the first element
59    int maximumStrongPairXor(vector<int>& nums) {
60        sort(nums.begin(), nums.end()); // sort the input numbers
61        Trie* trie = new Trie();
62        int max_xor = 0; // variable to store the maximum XOR
63        int i = 0; // two pointers
64
65        for (int y : nums) {
66            trie->insert(y);
67            // keep removing elements while the condition (y > nums[i] * 2) is true
68            while (y > nums[i] * 2) {
69                trie->remove(nums[i++]);
70            }
71            max_xor = max(max_xor, trie->search(y)); // update maximum XOR value
72        }
73        return max_xor; // return the maximum XOR found among pairs
74    }
75};
76

1// Define the structure of a Trie node with children array and count.
2interface TrieNode {
3    children: (TrieNode | null)[];
4    count: number;
5}
6
7// Function to create a new Trie node initialized with children set to null and count set to 0.
8function createTrieNode(): TrieNode {
9    return { children: [null, null], count: 0 };
10}
11
12// Function to insert a number into the Trie.
13function insertIntoTrie(root: TrieNode, x: number): void {
14    let node = root;
15    for (let i = 20; i >= 0; i--) {
16        const bit = (x >> i) & 1;
17        if (node.children[bit] === null) {
18            node.children[bit] = createTrieNode();
19        }
20        node = node.children[bit]!;
21        node.count++;
22    }
23}
24
25// Function to search the Trie for the maximum XOR of a number with elements in the Trie.
26function searchTrie(root: TrieNode, x: number): number {
27    let node = root;
28    let maxXor = 0;
29    for (let i = 20; i >= 0; i--) {
30        const bit = (x >> i) & 1;
31        const oppositeBit = bit ^ 1;
32        if (node.children[oppositeBit] !== null && node.children[oppositeBit]!.count > 0) {
33            maxXor |= 1 << i;
34            node = node.children[oppositeBit]!;
35        } else {
36            node = node.children[bit]!;
37        }
38    }
39    return maxXor;
40}
41
42// Function to remove a number from the Trie.
43function removeFromTrie(root: TrieNode, x: number): void {
44    let node = root;
45    for (let i = 20; i >= 0; i--) {
46        const bit = (x >> i) & 1;
47        node = node.children[bit]!;
48        node.count--;
49    }
50}
51
52// Function to calculate the maximum XOR of a "strong pair" in an array.
53// A pair (i, j) is strong if i < j and nums[i] is at most twice as small as nums[j].
54function maximumStrongPairXor(nums: number[]): number {
55    // Sort the array in non-decreasing order.
56    nums.sort((a, b) => a - b);
57    const trieRoot = createTrieNode();
58    let maxPairXor = 0;
59    let leftIndex = 0;
60
61    for (const current of nums) {
62        insertIntoTrie(trieRoot, current);
63
64        // Ensure we only consider "strong pairs".
65        while (current > nums[leftIndex] * 2) {
66            removeFromTrie(trieRoot, nums[leftIndex]);
67            leftIndex++;
68        }
69
70        // Update the maximum XOR of a strong pair.
71        maxPairXor = Math.max(maxPairXor, searchTrie(trieRoot, current));
72    }
73
74    return maxPairXor;
75}
76

Time and Space Complexity

The time complexity of the given code can be analyzed based on the main operations performed: sorting the array, inserting elements into the Trie, searching in the Trie, and removing elements from the Trie.

Sorting the input array: Sorting is done using the sort() method with a time complexity of O(n log n), where n is the number of elements in nums.
Inserting elements into the Trie: The insertion is done by traversing 21 bits for each of the n elements, leading to a time complexity of O(n * 21) which simplifies to O(n log M), where M is the maximum value of an integer in the array which is assumed to be 2^20.
Removing elements from the Trie: Similarly, the removal operation is done by traversing 21 bits for each of the elements that are removed, which in the worst case can be all elements, leading to a O(n log M) complexity.
Searching in the Trie: The search is performed by traversing 21 bits for the current element and is invoked every time an element is processed. This also leads to a O(n log M) complexity.

Thus, each of these operations contributes to the total time complexity of the algorithm, and when combined, result in a time complexity of O(n log M), accounting for the most expensive repeated operations, which is inserting and searching in the Trie.

The space complexity comes from:

Storing the sorted array: In-place sorting does not add to the space complexity which remains O(n).
Storing the Trie: The Trie data structure in the worst case can contain all the unique elements represented in a binary form consisting of log M levels. Since each node stores a fixed number of children (2 in a binary trie) and a count, and considering the potential of storing n different numbers, the space complexity becomes O(n log M).

Based on the above analysis, the time complexity and space complexity of the code are O(n log M) each.

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

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

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know