Maximum strong pair xor ii

Array Hash Table Bit Manipulation Trie Sliding Window

32.2% acceptance

Feb 25, 2026

210

You are given a 0-indexed integer array nums. A pair of integers x and y is called a strong pair if: |x - y| <= min(x, y) You need to select two integers from nums such that they form a strong pair and their bitwise XOR is the maximum among all strong pairs in the array. Return the maximum XOR value out of all possible strong pairs in the array nums. Note that you can pick the same integer twice to form a pair.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_strong_pair_xor(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    nums.sort_unstable();
    let n = nums.len();
    const BITS: usize = 20;
    let max_nodes = (n + 1) * (BITS + 1) * 2 + 10;

    let mut ch = vec![0i32; max_nodes * 2];
    let mut cnt = vec![0i32; max_nodes];
    let mut node_cnt = 1usize; // node 0 is root

    let mut ans = 0i32;
    let mut lo = 0usize;

    for r in 0..n {
      // Remove elements no longer in strong pair window
      while nums[lo] * 2 < nums[r] {
        let mut cur = 0usize;
        for i in (0..BITS).rev() {
          let bit = ((nums[lo] >> i) & 1) as usize;
          let child = ch[cur * 2 + bit] as usize;
          cnt[child] -= 1;
          cur = child;
        }
        lo += 1;
      }

      // Add nums[r] to trie
      {
        let mut cur = 0usize;
        for i in (0..BITS).rev() {
          let bit = ((nums[r] >> i) & 1) as usize;
          if ch[cur * 2 + bit] == 0 {
            ch[cur * 2 + bit] = node_cnt as i32;
            node_cnt += 1;
          }
          let child = ch[cur * 2 + bit] as usize;
          cnt[child] += 1;
          cur = child;
        }
      }

      // Query max XOR with nums[r]
      {
        let mut cur = 0usize;
        let mut xor_val = 0i32;
        for i in (0..BITS).rev() {
          let bit = ((nums[r] >> i) & 1) as usize;
          let want = 1 - bit;
          let child_want = ch[cur * 2 + want] as usize;
          if child_want != 0 && cnt[child_want] > 0 {
            xor_val |= 1 << i;
            cur = child_want;
          } else {
            cur = ch[cur * 2 + bit] as usize;
          }
        }
        ans = ans.max(xor_val);
      }
    }
    ans
  }
}