Skip to content

421. Maximum Xor Of Two Numbers In An Array

Array Hash Table Bit Manipulation Trie

Problem - Maximum Xor Of Two Numbers In An Array

Medium

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

 

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

 

Constraints:

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

Solutions

 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
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = Trie()
        for val in nums:
            trie.insert(val)

        return max(trie.search(val) for val in nums)

class Trie:
    def __init__(self):
        self.children: List[Trie | None] = [None, None]

    def insert(self, ins: int):
        node = self
        for i in range(30, -1, -1):
            val = ins >> i & 1
            if node.children[val] is None:
                node.children[val] = Trie()
            node = node.children[val]

    def search(self, sear: int):
        node = self
        result = 0
        for i in range(30, -1, -1):
            val = sear >> i & 1
            if node.children[val ^ 1]:
                result |= 1 << i
                node = node.children[val ^ 1]
            else:
                node = node.children[val]
        return result

Submission Stats:

  • Runtime: 6165 ms (26.52%)
  • Memory: 499.2 MB (33.23%)