2935. Maximum Strong Pair XOR II
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 relationshipy ≤ 2x
, we start by sorting thenums
array. This sorting makes it easy to iterate over potentialy
values and maintain the ‘window’ ofx
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
or1
. The binary trie supports three main operations:insert(x: int)
: Adds the binary representation ofx
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 withx
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 ofx
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 usingsearch(y)
after ensuring all numbers that cannot form a strong pair with the currenty
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 potentialy
values. Another pointer,i
, marks the start of the window wherex
values are valid for the currenty
. If the smallestx
is too small for the currenty
(nums[i] * 2 < y
), it's removed from the trie, andi
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 EvaluatorExample 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 of2
with these numbers is2 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 is3 XOR 5 = 6
.
Next y
at index 2:
- Now
y
is 5, and we discard 3 from our window since3 * 2 < 5
(no longer a strong pair). The updated window is[5, 8]
. We get5 XOR 8 = 13
as the maximum.
Finally, with y
at index 3:
y
is 8, we discard 5 from our window since5 * 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 ofO(n log n)
, wheren
is the number of elements innums
. -
Inserting elements into the Trie: The insertion is done by traversing 21 bits for each of the
n
elements, leading to a time complexity ofO(n * 21)
which simplifies toO(n log M)
, whereM
is the maximum value of an integer in the array which is assumed to be2^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 storingn
different numbers, the space complexity becomesO(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.
Which data structure is used to implement priority queue?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.