LeetCode 1707 - Maximum XOR With an Element From Array

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Trie

Solution

Problem Understanding

The problem gives us two inputs:

An integer array nums
A list of queries, where each query is [xi, mi]

For every query, we must find the maximum possible value of:

nums[j] XOR xi

subject to the condition:

nums[j] <= mi

If no number in nums satisfies the condition nums[j] <= mi, then the answer for that query is -1.

The XOR operation is a bitwise operation. Its most important property for this problem is that two bits contribute maximally when they are different:

1 XOR 0 = 1
0 XOR 1 = 1

So, to maximize XOR, we usually want opposite bits whenever possible.

The constraints are extremely important:

nums.length and queries.length can each be up to 100000
Values can be as large as 10^9

A naive approach that checks every number in nums for every query would require:

100000 * 100000 = 10^10

operations in the worst case, which is far too slow.

The problem therefore requires a more advanced approach that avoids repeatedly scanning the entire array.

Several edge cases are important:

A query may have no valid numbers because every value in nums is larger than mi
nums may contain duplicate values
Queries are independent and may appear in arbitrary order
Values can be zero
Large values require handling up to 31 bits because 10^9 < 2^30

The core challenge is efficiently answering many constrained maximum XOR queries.

Approaches

Brute Force Approach

The most straightforward solution is to process each query independently.

For a query [xi, mi]:

Iterate through every number in nums
Ignore numbers greater than mi
Compute nums[j] XOR xi for valid numbers
Track the maximum result

This works because it directly checks every possible candidate.

However, it is too slow.

If there are n numbers and q queries:

Each query scans all n numbers
Total complexity becomes O(n * q)

With both values potentially equal to 100000, this approach is not feasible.

Key Insight

The important observation is that the constraint nums[j] <= mi changes per query, but queries can be processed in sorted order.

If we sort:

nums
queries by mi

then we can incrementally add valid numbers into a data structure as mi increases.

The second insight is that a Binary Trie allows us to efficiently compute the maximum XOR value.

A Binary Trie stores numbers bit by bit:

Each node has:
child 0
child 1

When trying to maximize XOR:

If the current bit of xi is 0, we prefer 1
If the current bit of xi is 1, we prefer 0

This greedy choice works because higher bits contribute more to the final numeric value.

Combining:

offline query processing
sorting
binary trie

gives an efficient solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Checks every number for every query
Optimal	O((n + q) log n + 31(n + q))	O(31 × n)	Uses sorting and a binary trie

Algorithm Walkthrough

Optimal Algorithm

Sort the nums array in ascending order.

Sorting allows us to progressively add only the numbers that satisfy the current query limit mi. 2. Transform the queries into a sortable structure.

For each query, store:

(mi, xi, original_index)

We keep the original index because sorting changes query order, but answers must be returned in the original order. 3. Sort the transformed queries by mi.

This ensures that as we process queries, the allowed maximum value only increases. 4. Create an empty Binary Trie.

The trie stores binary representations of numbers.

Since values are at most 10^9, we process bits from position 30 down to 0. 5. Maintain a pointer into the sorted nums array.

For each query with limit mi:

Insert all numbers <= mi into the trie
Advance the pointer accordingly

Each number is inserted exactly once. 6. Answer the query using greedy XOR traversal.

For every bit from 30 down to 0:

Extract the current bit of xi
Prefer the opposite bit in the trie
If opposite exists:
move there
set the corresponding bit in the result
Otherwise:
follow the same bit

This greedily maximizes the XOR value from the most significant bit downward. 7. Handle empty trie cases.

If no numbers have been inserted yet, then no valid number satisfies nums[j] <= mi.

Return -1. 8. Store the result at the query's original index.

This restores the required output order.

Why it works

The algorithm works because queries are processed in increasing order of mi. At any moment, the trie contains exactly the numbers allowed for the current query.

The trie traversal is optimal because XOR value is determined lexicographically by bits from most significant to least significant. Choosing the opposite bit whenever possible maximizes the current bit contribution without sacrificing already optimized higher bits.

Since every number is inserted once and every query performs a fixed 31-bit traversal, the algorithm is efficient enough for the constraints.

Python Solution

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}

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

    def insert(self, num: int) -> None:
        node = self.root

        for bit in range(30, -1, -1):
            current_bit = (num >> bit) & 1

            if current_bit not in node.children:
                node.children[current_bit] = TrieNode()

            node = node.children[current_bit]

    def max_xor(self, num: int) -> int:
        node = self.root
        result = 0

        for bit in range(30, -1, -1):
            current_bit = (num >> bit) & 1
            opposite_bit = 1 - current_bit

            if opposite_bit in node.children:
                result |= (1 << bit)
                node = node.children[opposite_bit]
            else:
                node = node.children[current_bit]

        return result

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        nums.sort()

        indexed_queries = []

        for index, (x, m) in enumerate(queries):
            indexed_queries.append((m, x, index))

        indexed_queries.sort()

        trie = BinaryTrie()

        answers = [-1] * len(queries)

        nums_index = 0
        n = len(nums)

        for limit, x, original_index in indexed_queries:

            while nums_index < n and nums[nums_index] <= limit:
                trie.insert(nums[nums_index])
                nums_index += 1

            if nums_index == 0:
                answers[original_index] = -1
            else:
                answers[original_index] = trie.max_xor(x)

        return answers

The implementation begins by sorting nums, which enables incremental insertion into the trie.

The queries are converted into tuples containing:

the limit mi
the XOR value xi
the original query index

Sorting queries by mi guarantees that once a number becomes valid, it remains valid for all future queries.

The BinaryTrie class handles insertion and XOR maximization. Each number is stored bit by bit from the most significant bit down to the least significant bit.

The max_xor method greedily attempts to move toward the opposite bit because opposite bits produce XOR value 1.

The main loop inserts all newly valid numbers before answering each query. Since every number is inserted only once, the total insertion cost remains linear in the number of elements.

Finally, answers are written back using original query indices so the returned array matches the input order.

Go Solution

package main

import "sort"

type TrieNode struct {
	children [2]*TrieNode
}

type BinaryTrie struct {
	root *TrieNode
}

func NewBinaryTrie() *BinaryTrie {
	return &BinaryTrie{
		root: &TrieNode{},
	}
}

func (t *BinaryTrie) Insert(num int) {
	node := t.root

	for bit := 30; bit >= 0; bit-- {
		currentBit := (num >> bit) & 1

		if node.children[currentBit] == nil {
			node.children[currentBit] = &TrieNode{}
		}

		node = node.children[currentBit]
	}
}

func (t *BinaryTrie) MaxXor(num int) int {
	node := t.root
	result := 0

	for bit := 30; bit >= 0; bit-- {
		currentBit := (num >> bit) & 1
		oppositeBit := 1 - currentBit

		if node.children[oppositeBit] != nil {
			result |= (1 << bit)
			node = node.children[oppositeBit]
		} else {
			node = node.children[currentBit]
		}
	}

	return result
}

func maximizeXor(nums []int, queries [][]int) []int {
	sort.Ints(nums)

	type Query struct {
		limit int
		x     int
		index int
	}

	indexedQueries := make([]Query, len(queries))

	for i, q := range queries {
		indexedQueries[i] = Query{
			limit: q[1],
			x:     q[0],
			index: i,
		}
	}

	sort.Slice(indexedQueries, func(i, j int) bool {
		return indexedQueries[i].limit < indexedQueries[j].limit
	})

	trie := NewBinaryTrie()

	answers := make([]int, len(queries))

	for i := range answers {
		answers[i] = -1
	}

	numsIndex := 0
	n := len(nums)

	for _, query := range indexedQueries {

		for numsIndex < n && nums[numsIndex] <= query.limit {
			trie.Insert(nums[numsIndex])
			numsIndex++
		}

		if numsIndex == 0 {
			answers[query.index] = -1
		} else {
			answers[query.index] = trie.MaxXor(query.x)
		}
	}

	return answers
}

The Go implementation follows the same algorithmic structure as the Python version.

A fixed-size array:

children [2]*TrieNode

is used instead of a hash map for efficiency because each node only has two possible children.

Go integers safely handle the required range because values are at most 10^9.

Slices are used for dynamic query storage, and sort.Slice is used for sorting custom structures.

Nil pointers naturally represent missing trie branches.

Worked Examples

Example 1

Input:

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]

Step 1: Sort nums

nums = [0,1,2,3,4]

Step 2: Transform and sort queries

Original Query	Stored Form
[3,1]	(1,3,0)
[1,3]	(3,1,1)
[5,6]	(6,5,2)

Already sorted by mi.

Query 1: `(1,3,0)`

Insert all numbers <= 1.

Inserted:

0, 1

Trie now contains:

0 -> 000
1 -> 001

Compute maximum XOR with 3.

3 XOR 0 = 3
3 XOR 1 = 2

Maximum:

Store:

answers[0] = 3

Query 2: `(3,1,1)`

Insert all numbers <= 3.

New insertions:

2, 3

Trie now contains:

0,1,2,3

Compute maximum XOR with 1.

1 XOR 0 = 1
1 XOR 1 = 0
1 XOR 2 = 3
1 XOR 3 = 2

Maximum:

Store:

answers[1] = 3

Query 3: `(6,5,2)`

Insert all numbers <= 6.

New insertion:

Trie now contains all numbers.

Compute maximum XOR with 5.

5 XOR 0 = 5
5 XOR 1 = 4
5 XOR 2 = 7
5 XOR 3 = 6
5 XOR 4 = 1

Maximum:

Final result:

[3,3,7]

Example 2

Input:

nums = [5,2,4,6,6,3]
queries = [[12,4],[8,1],[6,3]]

Step 1: Sort nums

[2,3,4,5,6,6]

Step 2: Sort queries

Query	Stored Form
[8,1]	(1,8,1)
[6,3]	(3,6,2)
[12,4]	(4,12,0)

Query `(1,8,1)`

No numbers <= 1.

Answer:

-1

Query `(3,6,2)`

Insert:

2,3

Compute:

6 XOR 2 = 4
6 XOR 3 = 5

Maximum:

Query `(4,12,0)`

Insert:

Compute:

12 XOR 2 = 14
12 XOR 3 = 15
12 XOR 4 = 8

Maximum:

Final result:

[15,-1,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n + 31(n + q))	Sorting plus trie operations
Space	O(31 × n)	Trie stores up to 31 nodes per inserted number

Sorting dominates the logarithmic portion of the runtime.

Each number is inserted into the trie exactly once, and each insertion processes 31 bits.

Each query also traverses exactly 31 bits.

Therefore the trie operations are effectively linear with respect to the number of elements and queries.

The trie may contain up to 31 new nodes per inserted number in the worst case, producing O(31 × n) space usage.

Test Cases

from typing import List

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}

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

            def insert(self, num: int) -> None:
                node = self.root

                for bit in range(30, -1, -1):
                    current_bit = (num >> bit) & 1

                    if current_bit not in node.children:
                        node.children[current_bit] = TrieNode()

                    node = node.children[current_bit]

            def max_xor(self, num: int) -> int:
                node = self.root
                result = 0

                for bit in range(30, -1, -1):
                    current_bit = (num >> bit) & 1
                    opposite_bit = 1 - current_bit

                    if opposite_bit in node.children:
                        result |= (1 << bit)
                        node = node.children[opposite_bit]
                    else:
                        node = node.children[current_bit]

                return result

        nums.sort()

        indexed_queries = []

        for index, (x, m) in enumerate(queries):
            indexed_queries.append((m, x, index))

        indexed_queries.sort()

        trie = BinaryTrie()

        answers = [-1] * len(queries)

        nums_index = 0

        for limit, x, original_index in indexed_queries:

            while nums_index < len(nums) and nums[nums_index] <= limit:
                trie.insert(nums[nums_index])
                nums_index += 1

            if nums_index == 0:
                answers[original_index] = -1
            else:
                answers[original_index] = trie.max_xor(x)

        return answers

solution = Solution()

assert solution.maximizeXor(
    [0,1,2,3,4],
    [[3,1],[1,3],[5,6]]
) == [3,3,7]  # provided example 1

assert solution.maximizeXor(
    [5,2,4,6,6,3],
    [[12,4],[8,1],[6,3]]
) == [15,-1,5]  # provided example 2

assert solution.maximizeXor(
    [1],
    [[0,0]]
) == [-1]  # no valid number

assert solution.maximizeXor(
    [0],
    [[0,0]]
) == [0]  # XOR with zero

assert solution.maximizeXor(
    [8,10,2],
    [[5,2]]
) == [7]  # best XOR uses 2

assert solution.maximizeXor(
    [1,2,3],
    [[7,3]]
) == [6]  # maximum among all valid numbers

assert solution.maximizeXor(
    [4,4,4],
    [[1,4]]
) == [5]  # duplicate values

assert solution.maximizeXor(
    [1000000000],
    [[1000000000,1000000000]]
) == [0]  # large values

assert solution.maximizeXor(
    [0,1,2],
    [[3,0]]
) == [3]  # only zero allowed

assert solution.maximizeXor(
    [2,4,6,8],
    [[1,1],[3,5],[7,10]]
) == [-1,7,15]  # mixed query limits

Test	Why
`[0,1,2,3,4]` with standard queries	Validates normal functionality
`[5,2,4,6,6,3]` example	Validates offline query ordering
Single element with impossible limit	Ensures `-1` handling
Single zero value	Tests XOR with zero
Small constrained search	Verifies limit filtering
Query using all numbers	Tests unrestricted maximum
Duplicate numbers	Ensures duplicates do not break trie
Very large values	Tests high-bit handling
Only zero allowed	Tests minimal valid trie
Mixed limits	Verifies incremental insertion logic

Edge Cases

No Valid Numbers

A query may have a limit mi smaller than every number in nums.

Example:

nums = [5,6,7]
query = [2,1]

No number satisfies nums[j] <= 1.

This is a common source of bugs because trie traversal assumes at least one inserted value exists.

The implementation handles this by checking:

if nums_index == 0:

before attempting trie traversal.

Duplicate Numbers

The input may contain repeated values.

Example:

nums = [4,4,4]

A buggy implementation might incorrectly attempt deduplication or mishandle repeated insertions.

The trie safely supports duplicates because inserting the same path multiple times does not affect correctness.

Large Bit Values

Values may be as large as 10^9.

This requires processing up to bit position 30.

If the implementation uses too few bits, higher-order contributions to XOR would be lost, producing incorrect answers.

The solution explicitly iterates:

for bit in range(30, -1, -1):

which safely covers all possible input values.

LeetCode 1707 - Maximum XOR With an Element From Array

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Sort nums

Step 2: Transform and sort queries

Query 1: (1,3,0)

Query 2: (3,1,1)

Query 3: (6,5,2)

Example 2

Step 1: Sort nums

Step 2: Sort queries

Query (1,8,1)

Query (3,6,2)

Query (4,12,0)

Complexity Analysis

Test Cases

Edge Cases

No Valid Numbers

Duplicate Numbers

Large Bit Values

Query 1: `(1,3,0)`

Query 2: `(3,1,1)`

Query 3: `(6,5,2)`

Query `(1,8,1)`

Query `(3,6,2)`

Query `(4,12,0)`