Maximum Strong Pair XOR I

Difficulty: Easy | Acceptance: 76.00% | Paid: No Topics: Array, Hash Table, Bit Manipulation, Trie, Sliding Window

You are given a 0-indexed integer array nums. A pair of indices (i, j) is called strong if 0 <= i <= j < nums.length and nums[i] <= nums[j].

The XOR value of a pair (i, j) is equal to nums[i] XOR nums[j].

Return the maximum XOR value of a strong pair in the array nums.

• Examples
• Constraints
• Brute Force
• Hash Set + Value Iteration
• Trie with Min-Value Constraint

Examples

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 = [5,6,25,30]

Output:

7

Explanation: There are 6 strong pairs in the array nums: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30). The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 100

Brute Force

Intuition Since the constraint nums.length <= 50 is very small, we can simply check every possible pair (i, j) to see if it is a strong pair and calculate the XOR.

Steps

• Initialize max_xor to 0.
• Iterate i from 0 to n - 1.
• Iterate j from i to n - 1.
• Check if nums[i] <= nums[j].
• If true, update max_xor with max(max_xor, nums[i] ^ nums[j]).
• Return max_xor.

class Solution:
    def maximumStrongPairXor(self, nums: list[int]) -> int:
        max_xor = 0
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                if nums[i] <= nums[j]:
                    max_xor = max(max_xor, nums[i] ^ nums[j])
        return max_xor

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Efficient enough for the given constraints.

Hash Set + Value Iteration

Intuition The constraint nums[i] <= 100 allows us to iterate through possible values instead of indices. For each number nums[j], we only care about previous numbers x such that x <= nums[j]. We can iterate x from 0 to nums[j] and check if x exists in our set of seen numbers.

Steps

• Initialize a set seen and max_xor to 0.
• Iterate through each number num in nums.
• Iterate x from 0 to num.
• If x is in seen, update max_xor with max(max_xor, x ^ num).
• Add num to seen.
• Return max_xor.

class Solution:
    def maximumStrongPairXor(self, nums: list[int]) -> int:
        seen = set()
        max_xor = 0
        for num in nums:
            for x in range(num + 1):
                if x in seen:
                    max_xor = max(max_xor, x ^ num)
            seen.add(num)
        return max_xor

Complexity

• Time: O(n * C), where C is the maximum value in nums (100).
• Space: O(n)
• Notes: Efficient due to the small value constraint.

Trie with Min-Value Constraint

Intuition To find the maximum XOR efficiently, we use a Trie. However, we must respect the nums[i] <= nums[j] constraint. We augment the Trie to store the minimum value in each subtree. When querying for nums[j], we only traverse to a child if that child’s subtree contains a value <= nums[j].

Steps

• Define a TrieNode with children and a min_val field.
• Initialize a Trie.
• Iterate through nums.
• For each num, query the Trie to find the maximum XOR with any previously seen number x where x <= num.
  • Traverse bits from MSB to LSB.
  • Prefer the bit that flips the current bit of num to maximize XOR.
  • Check if the preferred child exists and if its min_val <= num.
  • If not, take the other child (if valid).
• Update the global maximum.
• Insert num into the Trie, updating min_val along the path.

class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.min_val = float('inf')

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        node.min_val = min(node.min_val, num)
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.min_val = min(node.min_val, num)

    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            toggled = 1 - bit
            if node.children[toggled] and node.children[toggled].min_val <= num:
                max_xor |= (1 << i)
                node = node.children[toggled]
            elif node.children[bit] and node.children[bit].min_val <= num:
                node = node.children[bit]
            else:
                return 0
        return max_xor

class Solution:
    def maximumStrongPairXor(self, nums: list[int]) -> int:
        trie = Trie()
        max_xor = 0
        for num in nums:
            if trie.root.min_val != float('inf'):
                max_xor = max(max_xor, trie.find_max_xor(num))
            trie.insert(num)
        return max_xor

Complexity

• Time: O(n * 31)
• Space: O(n * 31)
• Notes: Optimal for larger inputs, handles the constraint via subtree min-values.