Maximum XOR of Two Numbers in an Array

Tested Python solution for LeetCode 421 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 421, Medium. Topics: Array, Hash Table, Bit Manipulation, Trie. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 421   # by problem number
lcpy gen -s maximum_xor_of_two_numbers_in_an_array   # by problem name

​

Problem

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

​

Examples

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

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

​

Constraints

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 2^31 - 1

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n * 31)
    # Space: O(n * 31)
    def find_maximum_xor(self, nums: list[int]) -> int:
        root: dict[int, dict] = {}

        def insert(word: int) -> None:
            node = root
            for bit in range(30, -1, -1):
                node = node.setdefault((word >> bit) & 1, {})

        result = 0
        insert(nums[0])
        for num in nums[1:]:
            node = root
            best = 0
            for bit in range(30, -1, -1):
                key = (num >> bit) & 1
                if (1 - key) in node:
                    best |= 1 << bit
                    node = node[1 - key]
                else:
                    node = node[key]
            result = max(result, best)
            insert(num)
        return result

​

Complexity

Time	Space
O(n * 31)	O(n * 31)

​

Tags