Maximum Strong Pair XOR II

Hard
1331.

Maximum Strong Pair XOR II

Maximum Strong Pair XOR II is a hard coding problem on arrays, bit manipulation and sliding window, asked in Amazon and Google interviews.

A pair of integers x and y is strong when |x - y| <= min(x, y).

Given an array nums of positive integers, choose two of its integers (you may pick the same element twice) that form a strong pair, so that their bitwise XOR is as large as possible.

Return that maximum XOR value.

Example 1

Input
nums = [6,9,12]
Output
15
Explanation
(6, 9) is strong since 3 <= 6, and `6 XOR 9 = 15`. (6, 12) and (9, 12) are strong too but give 10 and 5.

Example 2

Input
nums = [3,50]
Output
0
Explanation
(3, 50) is not strong, so only (3, 3) and (50, 50) remain, both with XOR 0.

Example 3

Input
nums = [7,4,5]
Output
3

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 2^20 - 1
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
 * @return {number}
 */
var maximumStrongPairXor = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Strong Pair XOR II — Solution in Python, Java & C++

Maximum Strong Pair XOR II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Strong Pair XOR II is a hard coding problem on arrays, bit manipulation and sliding window, asked in Amazon and Google interviews.

Problem statement

A pair of integers x and y is strong when |x - y| <= min(x, y).

Given an array nums of positive integers, choose two of its integers (you may pick the same element twice) that form a strong pair, so that their bitwise XOR is as large as possible.

Return that maximum XOR value.

Example 1

Input: nums = [6,9,12]
Output: 15
Explanation: (6, 9) is strong since 3 <= 6, and `6 XOR 9 = 15`. (6, 12) and (9, 12) are strong too but give 10 and 5.

Example 2

Input: nums = [3,50]
Output: 0
Explanation: (3, 50) is not strong, so only (3, 3) and (50, 50) remain, both with XOR 0.

Example 3

Input: nums = [7,4,5]
Output: 3

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 2^20 - 1

Hints for Maximum Strong Pair XOR II

  1. Hint 1

    With x <= y, the strong condition simplifies to y <= 2x.

  2. Hint 2

    Sort the numbers. For each y taken as the larger element, the valid partners x form a contiguous window ending at y whose left edge only moves right.

  3. Hint 3

    Keep the window in a binary trie that supports deletion (a count per node) and query the maximum XOR with y greedily from the top bit.

How to solve Maximum Strong Pair XOR II

After sorting, the partners of each y are exactly the values in [y/2, y], a sliding window. A binary trie with per-node counts can add and remove numbers and answer "maximum XOR with y" in O(20).

Approach

  1. Sort nums ascending and set a left pointer to 0.
  2. For each y in order: insert y into the trie (incrementing counts along its path).
  3. While 2 * nums[left] < y, remove nums[left] from the trie (decrementing counts) and advance left.
  4. Walk the trie from bit 19 down, preferring the child with the opposite bit of y whenever its count is positive; the bits gained form the best XOR for this y.
  5. Return the largest XOR seen.

Why it works

For x <= y, |x - y| <= min(x, y) reads y - x <= x, i.e. 2x >= y. Since the array is sorted and y only grows, the smallest allowed x only grows too, so the window moves monotonically and contains exactly the allowed partners when the query runs. The greedy walk maximises XOR because a higher bit outweighs all lower bits together; the count check ensures the walk follows only numbers still inside the window.

Complexity

  • Time — O(n log n + n · 20)
  • Space — O(n · 20)

Pitfalls

  • Deleting must decrement counts, not unlink nodes, because other numbers can share the path.
  • The pair (y, y) is always strong, so the answer is at least 0 and the trie is never empty during a query.
  • Compare 2 * x < y (strict) to evict — y = 2x is still strong.

Reference solution

Python

from typing import List

def maximumStrongPairXor(nums: List[int]) -> int:
    srt = sorted(nums)
    n = len(srt)
    ch = [0] * ((n * 20 + 2) * 2)
    cnt = [0] * (n * 20 + 2)
    nodes = 1

    def update(v, d):
        nonlocal nodes
        node = 0
        for b in range(19, -1, -1):
            bit = (v >> b) & 1
            if not ch[node * 2 + bit]:
                ch[node * 2 + bit] = nodes
                nodes += 1
            node = ch[node * 2 + bit]
            cnt[node] += d

    best = 0
    left = 0
    for y in srt:
        update(y, 1)
        while srt[left] * 2 < y:
            update(srt[left], -1)
            left += 1
        node = 0
        cur = 0
        for b in range(19, -1, -1):
            want = ((y >> b) & 1) ^ 1
            c = ch[node * 2 + want]
            if c and cnt[c] > 0:
                cur |= 1 << b
                node = c
            else:
                node = ch[node * 2 + (want ^ 1)]
        if cur > best:
            best = cur
    return best

Java

public static int maximumStrongPairXor(int[] nums) {
    int[] srt = nums.clone();
    Arrays.sort(srt);
    int n = srt.length;
    int[] ch = new int[(n * 20 + 2) * 2];
    int[] cnt = new int[n * 20 + 2];
    int[] nodes = {1};
    int best = 0, left = 0;
    for (int i = 0; i < n; i++) {
        int y = srt[i];
        mspxUpdate(ch, cnt, nodes, y, 1);
        while (srt[left] * 2 < y) { mspxUpdate(ch, cnt, nodes, srt[left], -1); left++; }
        int node = 0, cur = 0;
        for (int b = 19; b >= 0; b--) {
            int want = ((y >> b) & 1) ^ 1;
            int c = ch[node * 2 + want];
            if (c != 0 && cnt[c] > 0) { cur |= 1 << b; node = c; }
            else node = ch[node * 2 + (want ^ 1)];
        }
        best = Math.max(best, cur);
    }
    return best;
}

static void mspxUpdate(int[] ch, int[] cnt, int[] nodes, int v, int d) {
    int node = 0;
    for (int b = 19; b >= 0; b--) {
        int bit = (v >> b) & 1;
        if (ch[node * 2 + bit] == 0) ch[node * 2 + bit] = nodes[0]++;
        node = ch[node * 2 + bit];
        cnt[node] += d;
    }
}

C++

int maximumStrongPairXor(vector<int>& nums) {
    vector<int> srt(nums);
    sort(srt.begin(), srt.end());
    int n = srt.size();
    vector<int> ch((n * 20 + 2) * 2, 0), cnt(n * 20 + 2, 0);
    int nodes = 1;
    auto update = [&](int v, int d) {
        int node = 0;
        for (int b = 19; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
            node = ch[node * 2 + bit];
            cnt[node] += d;
        }
    };
    int best = 0, left = 0;
    for (int i = 0; i < n; i++) {
        int y = srt[i];
        update(y, 1);
        while (srt[left] * 2 < y) { update(srt[left], -1); left++; }
        int node = 0, cur = 0;
        for (int b = 19; b >= 0; b--) {
            int want = ((y >> b) & 1) ^ 1;
            int c = ch[node * 2 + want];
            if (c && cnt[c] > 0) { cur |= 1 << b; node = c; }
            else node = ch[node * 2 + (want ^ 1)];
        }
        best = max(best, cur);
    }
    return best;
}

JavaScript

var maximumStrongPairXor = function(nums) {
    var srt = nums.slice().sort(function(a, b) { return a - b; });
    var n = srt.length;
    var ch = new Int32Array((n * 20 + 2) * 2), cnt = new Int32Array(n * 20 + 2);
    var nodes = 1;
    function update(v, d) {
        var node = 0;
        for (var b = 19; b >= 0; b--) {
            var bit = (v >> b) & 1;
            if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
            node = ch[node * 2 + bit];
            cnt[node] += d;
        }
    }
    var best = 0, left = 0;
    for (var i = 0; i < n; i++) {
        var y = srt[i];
        update(y, 1);
        while (srt[left] * 2 < y) { update(srt[left], -1); left++; }
        var node = 0, cur = 0;
        for (var b = 19; b >= 0; b--) {
            var want = ((y >> b) & 1) ^ 1;
            var c = ch[node * 2 + want];
            if (c && cnt[c] > 0) { cur |= 1 << b; node = c; }
            else node = ch[node * 2 + (want ^ 1)];
        }
        if (cur > best) best = cur;
    }
    return best;
};

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 · Bit Manipulation