Maximum XOR of Two Numbers in an Array

Medium Tries Bitwise Trie Original on LeetCode

Reported atGoldman Sachs

Maximum XOR of Two Numbers in an Array is a medium tries problem solved with the bitwise trie pattern. The best approach, optimal (binary trie, greedy from the top bit), runs in O(n · 31) time and O(n · 31) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an array nums of non-negative integers. Return the largest value of nums[i] XOR nums[j] over all index pairs with 0 <= i <= j < nums.length.

Note that i and j may be the same index, so the answer is never negative and is 0 when the array has only one number.

Examples

Example 1

Input
nums = [6, 9, 12, 3]
Output
15
Why
6 XOR 9 = 0110 XOR 1001 = 1111 = 15, and 12 XOR 3 is also 15. No pair can beat 4 set bits here.

Example 2

Input
nums = [8, 1, 2, 20]
Output
28
Why
20 XOR 8 = 10100 XOR 01000 = 11100 = 28. The next best pair, 20 XOR 2, only reaches 22.

Example 3

Input
nums = [7]
Output
0
Why
With a single number the only pair is the number with itself, and x XOR x = 0.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n²)O(1)
Optimal (binary trie, greedy from the top bit)O(n · 31)O(n · 31)

1Brute force

TimeO(n²)Every one of the n(n - 1) / 2 pairs is XORed once.
SpaceO(1)Only the running maximum.

Try every pair of indices and keep the largest XOR.

  1. best = 0.
  2. For every i and every j > i, best = max(best, nums[i] ^ nums[j]).
  3. Return best.
class Solution {
    public int findMaximumXOR(int[] nums) {
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                best = Math.max(best, nums[i] ^ nums[j]);
            }
        }
        return best;
    }
}

2Optimal (binary trie, greedy from the top bit)

TimeO(n · 31)Each number does one insert and one query, each 31 steps long.
SpaceO(n · 31)Each insert can create up to 31 new trie nodes.

Insert each number into a trie keyed by its bits from bit 30 down to bit 0. For a query x, walk from the root and at every level take the child whose bit is the opposite of x's bit if it exists (that bit of the XOR becomes 1), otherwise take the same bit. Because a higher bit outweighs all lower bits combined, this greedy walk finds the best partner for x. Insert x before querying it so the trie is never empty.

  1. Build trie nodes as arrays of two children, stored in flat int arrays for speed.
  2. For each x: insert its 31 bits, then walk the trie choosing the opposite bit when possible, adding (1 << b) to the XOR each time it succeeds.
  3. Keep the maximum XOR over all x.
class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxNodes = nums.length * 31 + 1;
        int[][] child = new int[2][maxNodes];
        int count = 1; // node 0 is the root
        int best = 0;
        for (int x : nums) {
            int node = 0;
            for (int b = 30; b >= 0; b--) {
                int bit = (x >> b) & 1;
                if (child[bit][node] == 0) child[bit][node] = count++;
                node = child[bit][node];
            }
            node = 0;
            int cur = 0;
            for (int b = 30; b >= 0; b--) {
                int bit = (x >> b) & 1;
                int want = bit ^ 1;
                if (child[want][node] != 0) {
                    cur |= 1 << b;
                    node = child[want][node];
                } else {
                    node = child[bit][node];
                }
            }
            best = Math.max(best, cur);
        }
        return best;
    }
}

Edge cases to test

  • A single element (answer 0, since i may equal j)
  • All elements equal (answer 0)
  • Zero in the array (its XOR with x is x itself)
  • Numbers using bit 30, the highest bit allowed

Hints

Hint 1

The highest bit of the result matters more than all lower bits together. Try to make the top bit 1 first, then the next, and so on.

Hint 2

For a fixed number x, the best partner has the opposite bit to x wherever possible, starting from the top bit.

Hint 3

Store every number in a binary trie of its 31 bits. Walking down from the root, prefer the child with the opposite bit.

FAQ

What is the best time complexity for Maximum XOR of Two Numbers in an Array?

Optimal (binary trie, greedy from the top bit) runs in O(n · 31) time and O(n · 31) extra space. Each number does one insert and one query, each 31 steps long.

Which pattern does Maximum XOR of Two Numbers in an Array use?

It is a tries problem that uses the bitwise trie pattern.

Is there a brute force solution for Maximum XOR of Two Numbers in an Array?

Yes. Brute force takes O(n²) time and O(1) space. Try every pair of indices and keep the largest XOR.

Which edge cases should I test for Maximum XOR of Two Numbers in an Array?

A single element (answer 0, since i may equal j); All elements equal (answer 0); Zero in the array (its XOR with x is x itself); Numbers using bit 30, the highest bit allowed.