#2935

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Strong Pair XOR II

Find the maximum XOR among strong pairs in an array using array scanning and hash-based lookups efficiently.

array hash table bit manipulation trie sliding window

Problem Statement

You are given a 0-indexed integer array nums. A pair of integers (x, y) is considered strong if it satisfies a specific numeric condition defined in the problem. You must analyze the array to identify all possible strong pairs.

Your task is to find two integers from nums that form a strong pair and return the maximum XOR value achievable among all strong pairs. Optimize the approach for arrays with up to 5 * 10^4 elements and integer values up to 2^20 - 1.

Examples

Example 1

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

Output: 7

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

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

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

Solution Approach

Sort and Hash-Based Tracking

Sort the array to allow ordered comparisons, then iterate while maintaining a hash structure to record potential strong pairs. For each number, check candidates in the hash to compute XORs efficiently, ensuring the largest XOR is captured without brute-force checking all pairs.

Trie for Bitwise Maximization

Construct a Trie to store binary representations of nums. For each number, traverse the Trie to find the number that maximizes XOR while meeting the strong pair condition. This leverages bit manipulation for O(n * log(max_num)) performance, avoiding redundant checks.

Sliding Window or Two-Pointer Optimization

Apply a sliding window or two-pointer technique over the sorted array to quickly identify valid strong pairs. Calculate XORs on-the-fly within the window, updating the maximum XOR. This reduces unnecessary comparisons and aligns with the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n log n) for sorting plus O(n log(max_num)) for Trie traversal. Space complexity depends on the hash table or Trie size, proportional to n or max number of bits.

What Interviewers Usually Probe

Ask why a naive double loop is too slow for n up to 5 * 10^4.
Probe understanding of bitwise XOR maximization using Trie structures.
Check if candidate strong pairs are correctly filtered before computing XORs.

Common Pitfalls or Variants

Common pitfalls

Assuming all pairs are strong without applying the numeric condition.
Using brute-force nested loops, leading to timeouts on large arrays.
Failing to maintain proper hash or Trie updates when scanning the array.

Follow-up variants

Compute the minimum XOR of all strong pairs instead of maximum.
Find the maximum XOR among strong pairs with additional constraints on indices.
Adapt the problem to allow dynamic insertion of new numbers into nums and maintain maximum XOR efficiently.

FAQ

What is a strong pair in Maximum Strong Pair XOR II?

A strong pair consists of two numbers from nums satisfying a numeric condition, used to compute the maximum XOR.

How can I efficiently find the maximum XOR among strong pairs?

Use array sorting with hash lookup or a Trie to track candidates and compute XORs without checking every pair.

Does the array order affect the maximum XOR calculation?

Sorting helps streamline comparisons and ensures the scanning plus hash lookup pattern captures the largest XOR efficiently.

Can I use a brute-force approach for Maximum Strong Pair XOR II?

Brute-force is possible but inefficient for arrays up to 5 * 10^4 elements, likely causing timeouts.

Which LeetCode topics are most relevant to this problem?

Array scanning, hash table, bit manipulation, Trie, and sliding window are directly applicable to compute maximum XOR for strong pairs.

terminal

Solution

Solution 1: Sorting + Binary Trie

Observing the inequality $|x - y| \leq \min(x, y)$, which involves absolute value and minimum value, we can assume $x \leq y$, then we have $y - x \leq x$, that is, $y \leq 2x$. We can enumerate $y$ from small to large, then $x$ must satisfy the inequality $y \leq 2x$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

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

Continue Practicing

#2932 maximum strong pair xor i #1938 maximum genetic difference query #2958 length of longest subarray with at most k frequency