Maximum XOR With an Element From Array

Hard
1327.

Maximum XOR With an Element From Array

Maximum XOR With an Element From Array is a hard coding problem on arrays, sorting and bit manipulation, asked in Amazon and Google interviews.

You are given an array nums of non-negative integers and an array queries where queries[i] = [xi, mi].

The answer to query i is the largest value of xi XOR nums[j] over all indices j with nums[j] <= mi. If every element of nums is larger than mi, the answer is -1.

Return an array answer with answer[i] 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
Query 0 may use 0 and 1: `3 XOR 0 = 3`. Query 1 may use 0..3: `1 XOR 2 = 3`. Query 2 may use everything: `5 XOR 2 = 7`.

Example 2

Input
nums = [6,9,12], queries = [[8,5],[4,10],[0,20]]
Output
[-1,13,12]
Explanation
No element is at most 5. With limit 10, `4 XOR 9 = 13` beats `4 XOR 6 = 2`.

Constraints

  • 1 <= nums.length, queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximizeXor = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum XOR With an Element From Array — Problem & Solution

Maximum XOR With an Element From Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum XOR With an Element From Array is a hard coding problem on arrays, sorting and bit manipulation, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of non-negative integers and an array queries where queries[i] = [xi, mi].

The answer to query i is the largest value of xi XOR nums[j] over all indices j with nums[j] <= mi. If every element of nums is larger than mi, the answer is -1.

Return an array answer with answer[i] 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: Query 0 may use 0 and 1: `3 XOR 0 = 3`. Query 1 may use 0..3: `1 XOR 2 = 3`. Query 2 may use everything: `5 XOR 2 = 7`.

Example 2

Input: nums = [6,9,12], queries = [[8,5],[4,10],[0,20]]
Output: [-1,13,12]
Explanation: No element is at most 5. With limit 10, `4 XOR 9 = 13` beats `4 XOR 6 = 2`.

Constraints

  • 1 <= nums.length, queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 10^9

Hints for Maximum XOR With an Element From Array

  1. Hint 1

    Without the limit this is the classic maximum-XOR query: a binary trie of the numbers, walked greedily from the top bit.

  2. Hint 2

    The limit only removes numbers. Can you answer the queries in an order where the allowed set only grows?

  3. Hint 3

    Sort nums and sort the queries by mi; before each query insert every number <= mi into the trie, then walk it preferring the opposite bit of xi.

How to solve Maximum XOR With an Element From Array

Answer the queries offline in increasing order of mi, so the set of allowed numbers only grows and a single binary trie can hold exactly them.

Approach

  1. Sort nums, and sort the query indices by mi.
  2. Keep a pointer into the sorted nums. For each query in that order, insert every number <= mi into a 30-level binary trie (10^9 < 2^30).
  3. If nothing has been inserted, the answer is -1.
  4. Otherwise walk from bit 29 down: at each level go to the child holding the opposite of xi's bit if it exists (that bit of the XOR becomes 1), else the other child. The bits collected form the answer.
  5. Store each answer at its original query index.

Why it works

After the insertions the trie contains precisely the numbers allowed by the current query. The greedy walk is optimal because a 1 in a higher XOR bit outweighs every lower bit combined, so whenever the opposite bit is available taking it can never be beaten.

Complexity

  • Time — O((n + q) · 30 + n log n + q log q)
  • Space — O(n · 30)

Pitfalls

  • Answers must be returned in the original query order, not the sorted one.
  • Use <= mi, not < mi, when inserting.
  • Return -1 only when no number is allowed — an allowed number can still give XOR 0.

Reference solution

Python

from typing import List

def maximizeXor(nums: List[int], queries: List[List[int]]) -> List[int]:
    srt = sorted(nums)
    order = sorted(range(len(queries)), key=lambda i: queries[i][1])
    ch = [0] * ((len(srt) * 30 + 2) * 2)
    nodes = 1
    p = 0
    ans = [0] * len(queries)
    for qi in order:
        x, m = queries[qi]
        while p < len(srt) and srt[p] <= m:
            node = 0
            v = srt[p]
            for b in range(29, -1, -1):
                bit = (v >> b) & 1
                if not ch[node * 2 + bit]:
                    ch[node * 2 + bit] = nodes
                    nodes += 1
                node = ch[node * 2 + bit]
            p += 1
        if p == 0:
            ans[qi] = -1
            continue
        cur = 0
        best = 0
        for b in range(29, -1, -1):
            want = ((x >> b) & 1) ^ 1
            if ch[cur * 2 + want]:
                best |= 1 << b
                cur = ch[cur * 2 + want]
            else:
                cur = ch[cur * 2 + (want ^ 1)]
        ans[qi] = best
    return ans

Java

public static int[] maximizeXor(int[] nums, int[][] queries) {
    int[] srt = nums.clone();
    Arrays.sort(srt);
    int q = queries.length;
    Integer[] order = new Integer[q];
    for (int i = 0; i < q; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(queries[a][1], queries[b][1]));
    int[] ch = new int[(srt.length * 30 + 2) * 2];
    int nodes = 1, p = 0;
    int[] ans = new int[q];
    for (int t = 0; t < q; t++) {
        int qi = order[t], x = queries[qi][0], m = queries[qi][1];
        while (p < srt.length && srt[p] <= m) {
            int node = 0;
            for (int b = 29; b >= 0; b--) {
                int bit = (srt[p] >> b) & 1;
                if (ch[node * 2 + bit] == 0) ch[node * 2 + bit] = nodes++;
                node = ch[node * 2 + bit];
            }
            p++;
        }
        if (p == 0) { ans[qi] = -1; continue; }
        int cur = 0, best = 0;
        for (int b = 29; b >= 0; b--) {
            int want = ((x >> b) & 1) ^ 1;
            if (ch[cur * 2 + want] != 0) { best |= 1 << b; cur = ch[cur * 2 + want]; }
            else cur = ch[cur * 2 + (want ^ 1)];
        }
        ans[qi] = best;
    }
    return ans;
}

C++

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> srt(nums);
    sort(srt.begin(), srt.end());
    int q = queries.size();
    vector<int> order(q);
    for (int i = 0; i < q; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return queries[a][1] < queries[b][1]; });
    vector<int> ch(((int)srt.size() * 30 + 2) * 2, 0);
    int nodes = 1, p = 0;
    vector<int> ans(q);
    for (int t = 0; t < q; t++) {
        int qi = order[t], x = queries[qi][0], m = queries[qi][1];
        while (p < (int)srt.size() && srt[p] <= m) {
            int node = 0;
            for (int b = 29; b >= 0; b--) {
                int bit = (srt[p] >> b) & 1;
                if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
                node = ch[node * 2 + bit];
            }
            p++;
        }
        if (p == 0) { ans[qi] = -1; continue; }
        int cur = 0, best = 0;
        for (int b = 29; b >= 0; b--) {
            int want = ((x >> b) & 1) ^ 1;
            if (ch[cur * 2 + want]) { best |= 1 << b; cur = ch[cur * 2 + want]; }
            else cur = ch[cur * 2 + (want ^ 1)];
        }
        ans[qi] = best;
    }
    return ans;
}

JavaScript

var maximizeXor = function(nums, queries) {
    var srt = nums.slice().sort(function(a, b) { return a - b; });
    var order = [];
    for (var i = 0; i < queries.length; i++) order.push(i);
    order.sort(function(a, b) { return queries[a][1] - queries[b][1]; });
    var ch = new Int32Array((srt.length * 30 + 2) * 2);
    var nodes = 1, p = 0;
    var ans = new Array(queries.length);
    for (var t = 0; t < order.length; t++) {
        var qi = order[t], x = queries[qi][0], m = queries[qi][1];
        while (p < srt.length && srt[p] <= m) {
            var node = 0;
            for (var b = 29; b >= 0; b--) {
                var bit = (srt[p] >> b) & 1;
                if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
                node = ch[node * 2 + bit];
            }
            p++;
        }
        if (p === 0) { ans[qi] = -1; continue; }
        var cur = 0, best = 0;
        for (var b2 = 29; b2 >= 0; b2--) {
            var want = ((x >> b2) & 1) ^ 1;
            if (ch[cur * 2 + want]) { best |= 1 << b2; cur = ch[cur * 2 + want]; }
            else cur = ch[cur * 2 + (want ^ 1)];
        }
        ans[qi] = best;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms