Maximum XOR with an Element from Array

Master this topic with zero to advance depth.

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] \le m$ , we can sort both $nums$ and $queries$ (by $m$ ). By processing queries offline in non-decreasing order of $m$ , we only insert numbers into the Trie when they become 'valid' for the current $m$ . 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;
    }
}

← Previous QuestionShortest Unique Prefix

Next Question →Word Break II

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.