Course4all

Maximum XOR with an Element from Array

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Maximum XOR with an Element from Array

Given an integer array nums, return the maximum value of nums[j] XOR xi where nums[j] <= mi. If all numbers in nums are larger than mi, the answer is -1.

Visual Representation

Nums: [0, 1, 2, 3, 4] Query: [3, 1] (x=3, m=1) Valid nums <= 1: [0, 1] XOR results: 3^0=3, 3^1=2 Max: 3 Optimal approach: 1. Sort nums. 2. Sort queries by m. 3. Insert nums into Trie as long as nums[j] <= m. 4. Query Trie for max XOR.
Hard

Examples

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

Level I: Brute Force

Intuition

For each query [xi, mi], iterate through every number in the nums array. If nums[j] <= mi, calculate nums[j] XOR xi and update the maximum. Simple O(N*Q) solution.
⏱ O(N * Q)💾 O(1)
java
class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int max = -1;
            for (int n : nums) if (n <= queries[i][1]) max = Math.max(max, n ^ queries[i][0]);
            ans[i] = max;
        }
        return ans;
    }
}
Approach 2

Level III: Offline Queries + Binary Trie

Intuition

Since we need to check nums[j]≤mnums[j] \le m, we can sort both numsnums and queriesqueries (by mm). By processing queries offline in non-decreasing order of mm, we only insert numbers into the Trie when they become 'valid' for the current mm. This transforms the conditional maximum problem into a standard Maximum XOR problem on a growing Trie.
⏱ O(N log N + Q log Q + (N+Q) * 31).💾 O(N * 31).
java
import java.util.*;
class Solution {
    class Node { Node[] children = new Node[2]; }
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int[][] qWithIdx = new int[queries.length][3];
        for(int i=0; i<queries.length; i++) { qWithIdx[i][0]=queries[i][0]; qWithIdx[i][1]=queries[i][1]; qWithIdx[i][2]=i; }
        Arrays.sort(qWithIdx, (a,b) -> a[1] - b[1]);
        
        int[] ans = new int[queries.length];
        Node root = new Node();
        int numsIdx = 0;
        for(int i=0; i<qWithIdx.length; i++) {
            int x = qWithIdx[i][0], m = qWithIdx[i][1], originalIdx = qWithIdx[i][2];
            while(numsIdx < nums.length && nums[numsIdx] <= m) {
                insert(root, nums[numsIdx++]);
            }
            if(numsIdx == 0) ans[originalIdx] = -1;
            else ans[originalIdx] = getMaxXor(root, x);
        }
        return ans;
    }
    private void insert(Node root, int n) {
        Node curr = root;
        for(int i=30; i>=0; i--) {
            int bit = (n >> i) & 1;
            if(curr.children[bit] == null) curr.children[bit] = new Node();
            curr = curr.children[bit];
        }
    }
    private int getMaxXor(Node root, int x) {
        Node curr = root; int res = 0;
        for(int i=30; i>=0; i--) {
            int bit = (x >> i) & 1;
            if(curr.children[1-bit] != null) { res |= (1 << i); curr = curr.children[1-bit]; }
            else curr = curr.children[bit];
        }
        return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionShortest Unique Prefix
Next Question →Word Break II