# Maximum Strong Pair XOR II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-strong-pair-xor-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-strong-pair-xor-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, Trie
**Companies:** [ZScaler](https://scaleengineer.com/companies/zscaler)
---
## Problem
You are given a **0-indexed** integer array `nums`. A pair of integers `x` and `y` is called a **strong** pair if it satisfies the condition:

* `|x - y| <= min(x, y)`

You need to select two integers from `nums` such that they form a strong pair and their bitwise `XOR` is the **maximum** among all strong pairs in the array.

Return _the **maximum**_ `XOR` _value out of all possible strong pairs in the array_ `nums`.

**Note** that you can pick the same integer twice to form a pair.

**Example 1:**

**Input:** nums = [1,2,3,4,5]
**Output:** 7
**Explanation:** There are 11 strong pairs in the array `nums`: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

**Example 2:**

**Input:** nums = [10,100]
**Output:** 0
**Explanation:** There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

**Example 3:**

**Input:** nums = [500,520,2500,3000]
**Output:** 1020
**Explanation:** There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `1 <= nums[i] <= 220 - 1`

# Approaches
## Brute-Force Approach
The most straightforward approach is to check every possible pair of numbers from the input array. For each pair, we verify if it meets the 'strong pair' criteria. If it does, we compute their XOR value and update our maximum XOR result if the current pair's XOR is greater.
**Time:** O(N^2), where N is the number of elements in `nums`. We have two nested loops, each iterating up to N times. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** It's simple to understand and implement.; It requires no extra space, making its space complexity minimal.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 5 * 10^4), and this solution will likely result in a 'Time Limit Exceeded' error.
### Explanation
This method involves a nested loop to generate all unique pairs `(nums[i], nums[j])` where `i <= j`. For each pair, we test the strong pair condition: `|nums[i] - nums[j]| <= min(nums[i], nums[j])`. If the pair is strong, we calculate its XOR value. We maintain a variable, `max_xor`, initialized to zero, which is updated whenever a larger XOR value from a strong pair is found. This process continues until all pairs have been examined, and the final `max_xor` is the answer.

```java
class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int n = nums.length;
        int max_xor = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int x = nums[i];
                int y = nums[j];
                if (Math.abs(x - y) <= Math.min(x, y)) {
                    max_xor = Math.max(max_xor, x ^ y);
                }
            }
        }
        return max_xor;
    }
}
```
### Algorithm
1. Initialize a variable `max_xor` to 0.
2. Iterate through each element `x` of the array `nums` using an outer loop (from `i = 0` to `n-1`).
3. For each `x`, iterate through each element `y` from index `i` to the end of the array using an inner loop (from `j = i` to `n-1`). This ensures every pair is considered once, including pairs where the element is paired with itself.
4. For each pair `(x, y)`, check if it's a strong pair by evaluating the condition `|x - y| <= min(x, y)`.
5. If the condition is true, calculate their bitwise XOR `x ^ y`.
6. Update `max_xor = max(max_xor, x ^ y)`.
7. After checking all pairs, return `max_xor`.

## Trie with Sliding Window
A more efficient solution involves sorting the array and using a combination of a sliding window and a Trie (Prefix Tree). The strong pair condition `|x - y| <= min(x, y)` simplifies to `y <= 2x` if we assume `x <= y`. By sorting the array, we can process elements in increasing order. We use a sliding window to maintain a set of candidate numbers that can form a strong pair with the current element. A Trie is used on this set of candidates to find the number that yields the maximum XOR value with the current element in logarithmic time relative to the value of the numbers.
**Time:** O(N log N + N * K), which simplifies to O(N log N) because K (20) is a small constant. Sorting takes O(N log N). The main loop runs N times, and each Trie operation (insert, remove, query) takes O(K) time. The `left` pointer moves at most N times in total, so the total time for removals is amortized. · **Space:** O(N * K), where N is the number of elements and K is the number of bits in the numbers (here, K=20). The Trie can store up to N numbers, each contributing to a path of length K.
**Pros:** Highly efficient, with a time complexity that meets the problem constraints.; Effectively combines sorting, sliding window, and Trie data structure to solve a complex-looking condition.
**Cons:** The implementation is more complex, requiring a custom Trie data structure with insert, remove, and query operations.; The space complexity is proportional to the number of elements and the number of bits, which can be significant for large inputs.
### Explanation
We begin by sorting `nums`. This allows us to handle the strong pair condition efficiently. We iterate through the sorted array using a pointer `right`, representing the element `x = nums[right]`. We maintain a sliding window of candidates `[left, right]` and a Trie containing all elements `nums[j]` where `left <= j <= right`.

For each `x`, we first add it to the Trie. Then, we check the strong pair condition against the leftmost element of our window, `y = nums[left]`. Since `y <= x`, the condition is `x <= 2y`. If this fails (i.e., `x > 2 * nums[left]`), `nums[left]` is too small. We remove it from the Trie and advance `left`. We repeat this until the window's left boundary `nums[left]` is large enough.

At this point, every number `y` remaining in the Trie (from `nums[left]` to `nums[right]`) forms a strong pair with the current `x`. We then perform a query on the Trie: for the given `x`, find a `y` in the Trie that maximizes `x ^ y`. This query greedily builds the best matching number bit by bit. The maximum XOR found for `x` is used to update the global `maxXOR`.

This combination of sorting, a sliding window, and a Trie reduces the complexity of finding the best partner for each element from linear time to logarithmic time (with respect to the maximum value), leading to an overall efficient solution.

```java
class TrieNode {
    TrieNode[] children = new TrieNode[2];
    int count = 0; // Tracks how many numbers pass through this node
}

class Trie {
    private TrieNode root;
    private static final int MAX_BITS = 20; // nums[i] < 2^20

    public Trie() {
        root = new TrieNode();
    }

    public void insert(int num) {
        TrieNode curr = root;
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
            curr.count++;
        }
    }

    public void remove(int num) {
        TrieNode curr = root;
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            curr = curr.children[bit];
            curr.count--;
        }
    }

    public int findMaxXOR(int num) {
        TrieNode curr = root;
        int maxXOR = 0;
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;

            if (curr.children[oppositeBit] != null && curr.children[oppositeBit].count > 0) {
                maxXOR |= (1 << i);
                curr = curr.children[oppositeBit];
            } else {
                curr = curr.children[bit];
            }
        }
        return maxXOR;
    }
}

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        Trie trie = new Trie();
        int maxXOR = 0;
        int left = 0;
        for (int x : nums) {
            trie.insert(x);
            while (x > 2 * nums[left]) {
                trie.remove(nums[left]);
                left++;
            }
            maxXOR = Math.max(maxXOR, trie.findMaxXOR(x));
        }
        return maxXOR;
    }
}
```
### Algorithm
1. First, simplify the strong pair condition. For any two numbers `x` and `y`, let's assume `x <= y`. The condition `|x - y| <= min(x, y)` becomes `y - x <= x`, which simplifies to `y <= 2x`.
2. Sort the input array `nums` in non-decreasing order. This is key to enabling an efficient sliding window.
3. Initialize a Trie data structure, a variable `maxXOR = 0`, and a `left` pointer to 0.
4. Iterate through the sorted array with a `right` pointer (or an enhanced for-loop). Let the current element be `x`.
5. **Insert**: Insert the current element `x` into the Trie. The Trie will store numbers in their binary representation.
6. **Shrink Window**: The `left` pointer marks the beginning of our window of valid candidates. For the current `x` (`nums[right]`), any candidate `y` (`nums[left]`) must satisfy `x <= 2y`. If `x > 2 * nums[left]`, `nums[left]` is too small to form a strong pair with `x` (and any subsequent elements, since the array is sorted). So, we remove `nums[left]` from the Trie and increment `left` until the condition is met.
7. **Query**: After adjusting the window, all numbers currently in the Trie form a strong pair with `x`. We query the Trie with `x` to find the number `y` in the Trie that maximizes `x ^ y`. This is done by greedily choosing bits in `y` that are opposite to the bits in `x`, starting from the most significant bit.
8. **Update**: Update `maxXOR` with the result from the query if it's larger.
9. After iterating through all numbers, return `maxXOR`.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 2 ]; private int cnt = 0 ; public Trie () { } public void insert ( int x ) { Trie node = this ; for ( int i = 20 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; ++ node . cnt ; } } public int search ( int x ) { Trie node = this ; int ans = 0 ; for ( int i = 20 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ^ 1 ] != null && node . children [ v ^ 1 ]. cnt > 0 ) { ans |= 1 << i ; node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } public void remove ( int x ) { Trie node = this ; for ( int i = 20 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; node = node . children [ v ]; -- node . cnt ; } } } class Solution { public int maximumStrongPairXor ( int [] nums ) { Arrays . sort ( nums ); Trie tree = new Trie (); int ans = 0 , i = 0 ; for ( int y : nums ) { tree . insert ( y ); while ( y > nums [ i ] * 2 ) { tree . remove ( nums [ i ++]); } ans = Math . max ( ans , tree . search ( y )); } return ans ; } }
```

### CPP

```cpp
class Trie { public: Trie * children [ 2 ]; int cnt ; Trie () : cnt ( 0 ) { children [ 0 ] = nullptr ; children [ 1 ] = nullptr ; } void insert ( int x ) { Trie * node = this ; for ( int i = 20 ; ~ i ; -- i ) { int v = ( x >> i ) & 1 ; if ( node -> children [ v ] == nullptr ) { node -> children [ v ] = new Trie (); } node = node -> children [ v ]; ++ node -> cnt ; } } int search ( int x ) { Trie * node = this ; int ans = 0 ; for ( int i = 20 ; ~ i ; -- i ) { int v = ( x >> i ) & 1 ; if ( node -> children [ v ^ 1 ] != nullptr && node -> children [ v ^ 1 ] -> cnt > 0 ) { ans |= 1 << i ; node = node -> children [ v ^ 1 ]; } else { node = node -> children [ v ]; } } return ans ; } void remove ( int x ) { Trie * node = this ; for ( int i = 20 ; ~ i ; -- i ) { int v = ( x >> i ) & 1 ; node = node -> children [ v ]; -- node -> cnt ; } } }; class Solution { public: int maximumStrongPairXor ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); Trie * tree = new Trie (); int ans = 0 , i = 0 ; for ( int y : nums ) { tree -> insert ( y ); while ( y > nums [ i ] * 2 ) { tree -> remove ( nums [ i ++ ]); } ans = max ( ans , tree -> search ( y )); } return ans ; } };
```

### Python

```python
class Trie : __slots__ = ( "children" , "cnt" ) def __init__ ( self ): self . children : List [ Trie | None ] = [ None , None ] self . cnt = 0 def insert ( self , x : int ): node = self for i in range ( 20 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ] is None : node . children [ v ] = Trie () node = node . children [ v ] node . cnt += 1 def search ( self , x : int ) -> int : node = self ans = 0 for i in range ( 20 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ^ 1 ] and node . children [ v ^ 1 ]. cnt : ans |= 1 << i node = node . children [ v ^ 1 ] else : node = node . children [ v ] return ans def remove ( self , x : int ): node = self for i in range ( 20 , - 1 , - 1 ): v = x >> i & 1 node = node . children [ v ] node . cnt -= 1 class Solution : def maximumStrongPairXor ( self , nums : List [ int ]) -> int : nums . sort () tree = Trie () ans = i = 0 for y in nums : tree . insert ( y ) while y > nums [ i ] * 2 : tree . remove ( nums [ i ]) i += 1 ans = max ( ans , tree . search ( y )) return ans
```