1707. Maximum XOR With an Element From Array Solution

The problem

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Approach overview

Problem Overview: You are given an integer array nums and queries [xi, mi]. For each query, choose a number from nums that is <= mi and maximize xi XOR num. If no valid number exists, return -1. The challenge is handling many queries efficiently while respecting the upper bound constraint.

Approach 1: Sorting and Binary Search (O(n log n + q log n + kq) time, O(1) extra space)

Start by sorting nums. For each query, use binary search to find the largest index where nums[i] <= mi. This gives the subset of values eligible for that query. Iterate through that prefix and compute xi ^ nums[j] for each candidate while tracking the maximum. The binary search reduces the filtering step from O(n) to O(log n), but the XOR scan can still reach O(n) in the worst case.

This approach is straightforward and works when constraints are small or when you want a quick baseline implementation. However, repeated scans across queries make it inefficient when both nums and queries are large.

Approach 2: Trie Data Structure (O((n + q) * 32) time, O(n * 32) space)

The optimal approach uses a bitwise Trie. Each node represents a bit (0 or 1). Insert numbers from nums bit by bit from the most significant bit (31) down to the least significant bit (0). While querying, greedily move toward the opposite bit to maximize the XOR value.

The constraint num <= mi is handled using an offline processing trick. Sort nums and sort queries by mi. As you process queries in increasing order of mi, insert all numbers from nums that satisfy the limit into the Trie. Then compute the maximum XOR for xi using the current Trie state. Each insertion and query takes about 32 steps because integers are 32-bit.

This technique combines ideas from array preprocessing, bit manipulation, and Trie traversal. The offline sorting ensures each number is inserted exactly once, keeping the algorithm efficient.

Recommended for interviews: The Trie-based solution is the expected answer for hard interview settings. It demonstrates understanding of bitwise optimization and offline query processing. A simpler sorted-array scan can show initial reasoning, but the Trie approach proves you can design scalable solutions under tight constraints.

Approach 1: Approach 1: Sorting and Binary Search

Sort the array and for each query, use binary search to find the largest element <= m. Then compute the XOR for eligible numbers and find the maximum result.

Python

def maxXorQueries(nums, queries):
    nums.sort()
    answer = []
    for x, m in queries:
        max_xor = -1
        for num in nums:
            if num > m:
                break
            max_xor = max(max_xor, x ^ num)
        answer.append(max_xor)
    return answer

Java

import java.util.Arrays;

public class Solution {
    public int[] maxXorQueries(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0];
            int m = queries[i][1];
            int maxXor = -1;
            for (int num : nums) {
                if (num > m) break;
                maxXor = Math.max(maxXor, x ^ num);
            }
            answer[i] = maxXor;
        }
        return answer;
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> maxXorQueries(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    vector<int> answer(queries.size(), -1);
    for (int i = 0; i < queries.size(); ++i) {
        int x = queries[i][0];
        int m = queries[i][1];
        auto it = upper_bound(nums.begin(), nums.end(), m);
        int maxXor = -1;
        for (auto jt = nums.begin(); jt != it; ++jt) {
            maxXor = max(maxXor, x ^ *jt);
        }
        answer[i] = maxXor;
    }
    return answer;
}

JavaScript

function maxXorQueries(nums, queries) {
    nums.sort((a, b) => a - b);
    const answer = new Array(queries.length);
    queries.forEach(([x, m], idx) => {
        let maxXor = -1;
        for (const num of nums) {
            if (num > m) break;
            maxXor = Math.max(maxXor, x ^ num);
        }
        answer[idx] = maxXor;
    });
    return answer;
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int binary_search(int *nums, int numsSize, int limit) {
    int left = 0, right = numsSize - 1, result = -1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= limit) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int* maxXorQueries(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    
    int* answer = (int*) malloc(sizeof(int) * queriesSize);
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int x = queries[i][0];
        int m = queries[i][1];
        int index = binary_search(nums, numsSize, m);
        int maxXor = -1;
        for (int j = 0; j <= index; j++) {
            int currentXor = x ^ nums[j];
            if (currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
        answer[i] = maxXor;
    }
    return answer;
}

using System;

public class Solution {
    public int[] MaxXorQueries(int[] nums, int[][] queries) {
        Array.Sort(nums);
        int[] answer = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int x = queries[i][0];
            int m = queries[i][1];
            int maxXor = -1;
            foreach (int num in nums) {
                if (num > m) break;
                maxXor = Math.Max(maxXor, x ^ num);
            }
            answer[i] = maxXor;
        }
        return answer;
    }
}

Python's list sorting and iteration allow for checking valid elements by respecting the constraint m in each query. The XORs of eligible elements lead to the answer.

Complexity

Time Complexity: O(n log n + nq), relating to the sort step and each query.

Space Complexity: O(1) not counting the result list.

Try this approach in the editor

Approach 2: Approach 2: Trie Data Structure

Build a Trie data structure to efficiently find the number that gives the maximum XOR with a given number. This is useful for queries constrained by a maximum value since it supports parts of operations in logarithmic time.

#include <stdio.h>
#include <stdlib.h>
#define MAX_BIT 30

typedef struct TrieNode {
    struct TrieNode* children[2];
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->children[0] = node->children[1] = NULL;
    return node;
}

void insert(TrieNode* root, int num) {
    TrieNode* node = root;
    for (int i = MAX_BIT; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!node->children[bit]) {
            node->children[bit] = createNode();
        }
        node = node->children[bit];
    }
}

int query(TrieNode* root, int num, int limit) {
    TrieNode* node = root;
    int maxXor = 0;
    for (int i = MAX_BIT; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (node->children[1 - bit] && ((maxXor | (1 << i)) <= limit)) {
            maxXor |= (1 << i);
            node = node->children[1 - bit];
        } else if(node->children[bit]) {
            node = node->children[bit];
        } else {
            return -1;
        }
    }
    return maxXor;
}

int* maxXorQueries(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    TrieNode* root = createNode();
    for (int i = 0; i < numsSize; i++) {
        insert(root, nums[i]);
    }
    
    *returnSize = queriesSize;
    int* answer = (int*) malloc(sizeof(int) * queriesSize);
    for (int i = 0; i < queriesSize; i++) {
        answer[i] = query(root, queries[i][0], queries[i][1]);
    }
    return answer;
}

This code constructs a Trie to store the binary representation of numbers. For each query, it traverses the Trie to maximize the XOR. The query checks if adding a set bit (1) keeps the result below the xor threshold.

Complexity

Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers.

Space Complexity: O(n * MAX_BIT), needed for Trie structure.

Try this approach in the editor

Approach 3: Offline Query + Binary Trie

From the problem description, we know that each query is independent and the result of the query is irrelevant to the order of elements in nums. Therefore, we consider sorting all queries in ascending order of m_i, and also sorting nums in ascending order.

Next, we use a binary trie to maintain the elements in nums. We use a pointer j to record the current elements in the trie, initially j=0. For each query [x_i, m_i], we continuously insert elements from nums into the trie until nums[j] > m_i. At this point, we can query all elements not exceeding m_i in the trie, and we take the XOR value of the element with the maximum XOR value with x_i as the answer.

The time complexity is O(m times log m + n times (log n + log M)), and the space complexity is O(n times log M). Where m and n are the lengths of the arrays nums and queries respectively, and M is the maximum value in the array nums. In this problem, M \le 10^9.

TypeScript

class Trie {
    children: (Trie | null)[];

    constructor() {
        this.children = [null, null];
    }

    insert(x: number): void {
        let node: Trie | null = this;
        for (let i = 30; ~i; i--) {
            const v = (x >> i) & 1;
            if (node.children[v] === null) {
                node.children[v] = new Trie();
            }
            node = node.children[v] as Trie;
        }
    }

    search(x: number): number {
        let node: Trie | null = this;
        let ans = 0;
        for (let i = 30; ~i; i--) {
            const v = (x >> i) & 1;
            if (node.children[v ^ 1] !== null) {
                ans |= 1 << i;
                node = node.children[v ^ 1] as Trie;
            } else if (node.children[v] !== null) {
                node = node.children[v] as Trie;
            } else {
                return -1;
            }
        }
        return ans;
    }
}

function maximizeXor(nums: number[], queries: number[][]): number[] {
    nums.sort((a, b) => a - b);
    const n = queries.length;
    const idx = Array.from({ length: n }, (_, i) => i);
    idx.sort((i, j) => queries[i][1] - queries[j][1]);
    const ans: number[] = [];
    const trie = new Trie();
    let j = 0;
    for (const i of idx) {
        const x = queries[i][0];
        const m = queries[i][1];
        while (j < nums.length && nums[j] <= m) {
            trie.insert(nums[j++]);
        }
        ans[i] = trie.search(x);
    }
    return ans;
}

type Trie struct {
	children [2]*Trie
}

func NewTrie() *Trie {
	return &Trie{}
}

func (t *Trie) insert(x int) {
	node := t
	for i := 30; i >= 0; i-- {
		v := x >> i & 1
		if node.children[v] == nil {
			node.children[v] = NewTrie()
		}
		node = node.children[v]
	}
}

func (t *Trie) search(x int) int {
	node := t
	ans := 0
	for i := 30; i >= 0; i-- {
		v := x >> i & 1
		if node.children[v^1] != nil {
			ans |= 1 << i
			node = node.children[v^1]
		} else if node.children[v] != nil {
			node = node.children[v]
		} else {
			return -1
		}
	}
	return ans
}

func maximizeXor(nums []int, queries [][]int) []int {
	sort.Ints(nums)
	n := len(queries)
	idx := make([]int, n)
	for i := 0; i < n; i++ {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool {
		return queries[idx[i]][1] < queries[idx[j]][1]
	})
	ans := make([]int, n)
	trie := NewTrie()
	j := 0
	for _, i := range idx {
		x, m := queries[i][0], queries[i][1]
		for j < len(nums) && nums[j] <= m {
			trie.insert(nums[j])
			j++
		}
		ans[i] = trie.search(x)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sorting and Binary Search	Time Complexity: O(n log n + nq), relating to the sort step and each query. Space Complexity: O(1) not counting the result list.
Approach 2: Trie Data Structure	Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers. Space Complexity: O(n * MAX_BIT), needed for Trie structure.
Offline Query + Binary Trie	–

Approach

Complexity

Approach 1: Sorting and Binary Search

Time Complexity: O(n log n + nq), relating to the sort step and each query.

Space Complexity: O(1) not counting the result list.

Approach 2: Trie Data Structure

Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers.

Space Complexity: O(n * MAX_BIT), needed for Trie structure.

Offline Query + Binary Trie

–

Complexity analysis

Approach	Time	Space	When to Use
Sorting + Binary Search with Scan	O(n log n + q log n + nq)	O(1)	Simple baseline approach when constraints are small
Offline Queries + Bitwise Trie	O((n + q) * 32 + n log n + q log q)	O(n * 32)	Optimal solution for large inputs and interview scenarios

Frequently asked questions

Is Maximum XOR With an Element From Array easy or hard?

The problem is classified as Hard because it combines multiple concepts: offline query processing, bit manipulation, and Trie data structures. A naive scan is easy to write, but designing the optimal Trie solution requires deeper algorithmic insight.

Maximum XOR With an Element From Array Python/Java solution

Implementations in Python, Java, C++, and JavaScript follow the same pattern: sort nums, sort queries with indices, insert valid numbers into a Trie, and compute the maximum XOR for each query. Each query takes about 32 steps in the Trie.

How to solve Maximum XOR With an Element From Array in O(n)?

Strict O(n) is not achievable because queries must be processed and sorted by the limit value. The closest practical complexity is O((n + q) * 32) using a bitwise Trie with offline query sorting, which behaves close to linear for typical constraints.

What is the best approach for Maximum XOR With an Element From Array?

The best approach uses an offline query strategy combined with a bitwise Trie. Sort both the array and queries by the limit value m, insert eligible numbers into the Trie, and compute the maximum XOR greedily for each query. This keeps the complexity around O((n + q) * 32) after sorting.

Is Maximum XOR With an Element From Array asked at Google/Amazon/Meta?

Variants of maximum XOR and bitwise Trie problems frequently appear in interviews at companies like Google, Amazon, and Meta. Interviewers use them to test understanding of bit manipulation, prefix structures, and efficient query processing.

What data structure is used in Maximum XOR With an Element From Array?

The key data structure is a bitwise Trie (binary prefix tree). Each level represents a bit position, allowing greedy traversal toward the opposite bit to maximize XOR during queries.

What is the time complexity of Maximum XOR With an Element From Array?

The optimal Trie-based solution runs in O((n + q) * 32) time for Trie operations plus O(n log n + q log q) for sorting. Since integers have at most 32 bits, each insert and query takes constant time relative to input size.

Maximum XOR With an Element From Array solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Binary Search

Approach 2: Approach 2: Trie Data Structure

Approach 3: Offline Query + Binary Trie

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum XOR With an Element From Array solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Binary Search

Approach 2: Approach 2: Trie Data Structure

Approach 3: Offline Query + Binary Trie

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems