What is the brute force approach and complexity for Maximum XOR With an Element From Array?

For each query, try every number ≤ m and keep the best XOR; O(n · q) with time complexity O(n · q) and space complexity O(1).

What is the optimal approach and complexity for Maximum XOR With an Element From Array?

Sort nums and the queries by m; add each number when it becomes allowed; walk the trie per query with optimal time complexity O((n + q) log(n + q)) and space complexity O(30 · n).

How do you identify the pattern for Maximum XOR With an Element From Array?

Look for key signals in the prompt: "nums[j] ≤ m, for each query" indicates Every query limits which numbers it may use → sort by the limit and process the queries in that order.; "maximum XOR with x" indicates The best partner is found bit by bit → the greedy bitwise trie walk.; "−1 when no number is allowed" indicates An empty trie means no answer → check for it before the walk..

Maximum XOR With an Element From Array

Hard·LeetCode #1707 Pro OnlyInterview-Level

LeetCode

Problem Statement

You get a list of non-negative integers nums, and a list of queries. Each query is a pair [x, m].

For each query, look only at the numbers in nums that are not larger than m (that is, number ≤ m). Among those, find the largest value of number XOR x. If no number in nums is ≤ m, the answer for that query is -1.

Return one answer per query, in the same order as the queries.

Input

nums: a list of non-negative integers. queries: a list of pairs [x, m].

Output

A list with one answer per query, in the original query order.

Example 1

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

Output: [3, 3, 7]

For [3, 1]: only 0 and 1 are ≤ 1, and 0 XOR 3 = 3 beats 1 XOR 3 = 2. For [1, 3]: 2 XOR 1 = 3 is the best of 0, 1, 2, 3. For [5, 6]: 2 XOR 5 = 7 is the best of all five numbers.

Example 2

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

Output: [15, -1, 5]

For [12, 4]: the allowed numbers are 2, 4 and 3, and 3 XOR 12 = 15 is the best. For [8, 1]: no number is ≤ 1, so the answer is -1. For [6, 3]: the allowed numbers are 2 and 3, and 6 XOR 3 = 5.

Constraints

• 1 ≤ nums.length, queries.length ≤ 10^5
• Each query has exactly two numbers: queries[i] = [x, m].
• 0 ≤ nums[j], x, m ≤ 10^9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“nums[j] ≤ m, for each query”

→ Every query limits which numbers it may use → sort by the limit and process the queries in that order.

“maximum XOR with x”

→ The best partner is found bit by bit → the greedy bitwise trie walk.

“−1 when no number is allowed”

→ An empty trie means no answer → check for it before the walk.

Approach Complexity Ladder

Brute Force — scan every allowed number for each queryO(n · q)O(1)

For each query, try every number ≤ m and keep the best XOR; O(n · q)

Optimal — sort, then sweep the queries by m with a growing trieO((n + q) log(n + q))O(30 · n)

Sort nums and the queries by m; add each number when it becomes allowed; walk the trie per query

Brute Force Intuition

For a query [x, m], look at every number in nums. Skip the numbers above m. Keep the largest number XOR x among the rest. If nothing is allowed, the best value stays -1.

Recognition rule for this sub-pattern:

Store numbers bit by bit (high to low). To maximise XOR, greedily walk the opposite bit.

Remember this · Trie

Trigger

Many words + prefix search, autocomplete, word dictionary with wildcards, maximum XOR.

Think

Do many queries share prefixes that I keep re-checking?

Key question

What does each node store (children, end-of-word, count)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Trie translate into production architectures and low-level memory mechanics.

LLD Practice

Autocomplete & Search Engine

Prefix query caching, ranking, and memory-efficient trie compaction.

Explore Track

C++ Internals

Memory Alignment & Struct Padding

Minimizing pointer overhead and cache misses across 26-ary trie nodes.

Explore Track

Maximum XOR of Two Numbers in an Array