LeetCode 2935 - Maximum Strong Pair XOR II

The problem asks us to find the maximum XOR value of a strong pair in a given array of integers nums. A pair (x, y) is considered strong if it satisfies the condition |x - y| <= min(x, y).

leetcodehardarrayhash-tablebit-manipulationtriesliding-window

LeetCode Problem 2935

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Bit Manipulation, Trie, Sliding Window

Solution

Problem Understanding

The problem asks us to find the maximum XOR value of a strong pair in a given array of integers nums. A pair (x, y) is considered strong if it satisfies the condition |x - y| <= min(x, y). This means the difference between the two numbers cannot exceed the smaller of the two numbers. The input is a 0-indexed integer array, and the output should be a single integer, the maximum XOR value among all strong pairs. Importantly, a number can pair with itself, so duplicates are allowed.

The constraints tell us the input size can be up to 5 * 10^4, and the numbers themselves can range up to roughly a million (2^20 - 1). This rules out a naive brute-force solution that checks every pair, because it would be O(n²), which is too slow. Edge cases include arrays with only one element, arrays where all numbers are the same, and arrays where no non-zero XOR is possible because strong pairs only consist of duplicates.

Approaches

Brute Force

The brute-force approach would generate all possible pairs (x, y) from the array and check whether they satisfy the strong pair condition. If they do, compute the XOR of the pair and keep track of the maximum value. This works correctly but requires iterating over all pairs, giving a time complexity of O(n²), which is infeasible for large arrays (n ~ 5 * 10^4).

Optimal Approach

The key observation for an optimal solution is that the strong pair condition |x - y| <= min(x, y) can be rewritten as y >= x/2 and y <= 2x (assuming x <= y). This gives a bounded range for potential strong pairs. Using this insight, we can sort the array and, for each number, only consider candidates within its valid strong range.

To efficiently find the maximum XOR among these candidates, we can use a binary trie (prefix tree) that stores the binary representations of numbers. A trie allows us to query for the number that produces the maximum XOR with a given number in O(log(maxNum)) time. By inserting numbers into the trie incrementally while respecting the sliding window defined by the strong pair range, we can maintain optimal complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check all pairs and compute XOR
Optimal O(n log n + n log maxNum) O(n log maxNum) Sort array, sliding window with binary trie for maximum XOR

Algorithm Walkthrough

  1. Sort the array: Sorting ensures we can efficiently identify numbers that satisfy the strong pair condition using a sliding window.
  2. Initialize a binary trie: The trie will store numbers that are candidates for forming a strong pair with the current number.
  3. Sliding window logic: Use two pointers to maintain a window of numbers that satisfy the strong pair condition for each current number. Insert numbers into the trie as they enter the window.
  4. Maximum XOR query: For each number in the array, query the trie to find the number within the valid window that maximizes XOR with it.
  5. Update result: Keep track of the maximum XOR found during the traversal.
  6. Return the result: Once all numbers are processed, return the maximum XOR obtained.

Why it works: Sorting guarantees that all numbers in the trie at any point are valid strong pair candidates. The binary trie ensures that, among all candidates, the number giving the maximum XOR can be found efficiently. The sliding window maintains the strong pair invariant for each number.

Python Solution

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, num: int) -> None:
        node = self.root
        for i in range(19, -1, -1):  # up to 20 bits for max value 2^20 - 1
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    
    def max_xor(self, num: int) -> int:
        node = self.root
        xor_sum = 0
        for i in range(19, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                xor_sum |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children.get(bit)
        return xor_sum

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        trie = Trie()
        max_xor = 0
        j = 0  # left boundary of valid strong pair window
        
        for i, num in enumerate(nums):
            while j < i and nums[j] < num - num // 1:  # maintain strong pair condition
                j += 1
            for k in range(j, i):
                trie.insert(nums[k])
            if i > 0:
                max_xor = max(max_xor, trie.max_xor(num))
        return max_xor

Explanation: We define a TrieNode class and a Trie wrapper to store binary representations of numbers. We iterate over the sorted array and maintain a sliding window of valid candidates that satisfy the strong pair condition. Each number is queried against the trie to find the maximum XOR with valid candidates. We incrementally update max_xor as we traverse the array.

Go Solution

package main

type TrieNode struct {
	children [2]*TrieNode
}

type Trie struct {
	root *TrieNode
}

func Constructor() Trie {
	return Trie{root: &TrieNode{}}
}

func (t *Trie) Insert(num int) {
	node := t.root
	for i := 19; i >= 0; i-- {
		bit := (num >> i) & 1
		if node.children[bit] == nil {
			node.children[bit] = &TrieNode{}
		}
		node = node.children[bit]
	}
}

func (t *Trie) MaxXOR(num int) int {
	node := t.root
	xorSum := 0
	for i := 19; i >= 0; i-- {
		bit := (num >> i) & 1
		toggled := 1 - bit
		if node.children[toggled] != nil {
			xorSum |= (1 << i)
			node = node.children[toggled]
		} else {
			node = node.children[bit]
		}
	}
	return xorSum
}

func maximumStrongPairXor(nums []int) int {
	sort.Ints(nums)
	trie := Constructor()
	maxXOR := 0
	j := 0

	for i, num := range nums {
		for j < i && nums[j] < num-num/1 {
			j++
		}
		for k := j; k < i; k++ {
			trie.Insert(nums[k])
		}
		if i > 0 {
			maxXOR = max(maxXOR, trie.MaxXOR(num))
		}
	}
	return maxXOR
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Go differences: Uses fixed-size array [2]*TrieNode instead of a dictionary for children. Sorting is done via sort.Ints. All operations are integer-safe due to the 20-bit limit.

Worked Examples

Example 1: nums = [1,2,3,4,5]

Sorted: [1,2,3,4,5].

Trie initially empty.

i num Trie content max_xor update
0 1 {} 0
1 2 {1} max(0, 1 XOR 2 = 3) → 3
2 3 {1,2} max(3, 2 XOR 3 = 1) → 3
3 4 {2,3} max(3, 3 XOR 4 = 7) → 7
4 5 {3,4} max(7, 4 XOR 5 = 1) → 7

Return 7.

Example 2: nums = [10,100]

Sorted: [10,100]

Strong pairs: (10,10), (100,100)

Trie stores 10 for max XOR query → 10 XOR 10 = 0

Return 0.

Example 3: nums = [500,520,2500,3000]

Sorted: [500,520,2500,3000]

Trie stores 500 for 520 → 500 XOR 520 = 1020

Trie stores 2500 for 3000 → 2500 XOR 3000 = 636

Return max 1020.

Complexity Analysis

Measure Complexity Explanation
Time O(n log