Taro Logo

Maximum Strong Pair XOR II

#5 Most AskedHard
8 views
Topics:
ArraysTwo PointersBit ManipulationSliding WindowsTrees

You are given a 0-indexed integer array nums. A pair of integers x and y is called a strong pair if it satisfies the condition:

  • |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.

Example 1:

Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

Example 2:

Input: nums = [10,100]
Output: 0
Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

Example 3:

Input: nums = [500,520,2500,3000]
Output: 1020
Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 220 - 1

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Can a value be paired with itself, which contributes an exclusive-or of zero?
  2. Is a pair strong when the absolute difference is at most the smaller of the two values?
  3. Should the direct search return the largest exclusive-or among the strong pairs it finds?
  4. Are the values sorted before the bit search inserts them from small to large?
  5. Does the bit search rebuild a trie from scratch for every candidate bit?

Brute Force Solution

Approach

This double loop pairs every index with every index, including a value with itself. A pair is kept when the absolute difference is at most the smaller value. The answer is the largest exclusive-or among the pairs that pass.

Here's how the algorithm would work step-by-step:

  1. Start the best exclusive-or at zero.
  2. Choose a first index over the whole list.
  3. Choose a second index over the whole list, independently of the first.
  4. Read the two values and test whether their absolute difference is at most the smaller one.
  5. When the test passes, compute the exclusive-or of the two values.
  6. Replace the best value when this exclusive-or is larger.
  7. Return the best value after both loops finish.

Code Implementation

def maximumStrongPairXor(numbers):
    maximum_xor_so_far = 0
    collection_size = len(numbers)

    # We must check every number against every other number to find all possible pairs.
    for first_index in range(collection_size):
        for second_index in range(collection_size):
            first_number = numbers[first_index]
            second_number = numbers[second_index]

            # The strong pair condition requires the absolute difference to be no more than the minimum value.
            if abs(first_number - second_number) <= min(first_number, second_number):

                # For any valid strong pair, we calculate its XOR to see if it's a new maximum.
                current_pair_xor = first_number ^ second_number

                # We update our record if the current pair's XOR is the largest we've encountered.
                if current_pair_xor > maximum_xor_so_far:
                    maximum_xor_so_far = current_pair_xor
    
    return maximum_xor_so_far

Big(O) Analysis

Time Complexity
O(n^2) – The outer loop runs once per value and the inner loop runs once per value, so there are n squared pairs. Each pair computes an absolute difference, a minimum, and possibly an exclusive-or, all in constant time. No pair is skipped and no auxiliary index speeds the test up. The comparisons that update the maximum are also constant time. The total is O(n^2).
Space Complexity
O(1) – The loops store the two indexes, the two values, and the best exclusive-or. None of those quantities grows as more values are added. The input list is read in place. No pair list, set, or trie is allocated. Extra space is O(1).

Optimal Solution

Approach

The values are sorted, and the answer is assembled from the high bit downward. For each bit, a trie is rebuilt by inserting the sorted values one at a time, while each node remembers the smallest and largest value in its subtree. A query walks the trie for the exclusive-or prefix under test and returns success as soon as the opposite branch contains a value no larger than the current number.

Here's how the algorithm would work step-by-step:

  1. Sort the values and take twice the largest as the width of the bit field, returning zero when that width is zero.
  2. Start the answer at zero and walk bits from high to low.
  3. Form a candidate by turning on the current bit in the answer so far.
  4. Create an empty trie whose paths are that many bits long.
  5. Insert each sorted value, updating the minimum and maximum stored on every node that the value passes through.
  6. After each insertion, query whether the opposite branch at some bit has a minimum no larger than the inserted value.
  7. If any query succeeds, keep the candidate as the new answer and move to the next lower bit.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.min_value_in_subtree = float('inf')
        self.max_value_in_subtree = float('-inf')

class Trie:
    def __init__(self, bit_length):
        self.root = TrieNode()
        self.bit_length = bit_length

    def insert(self, number):
        current_node = self.root
        for bit_position in range(self.bit_length - 1, -1, -1):
            current_bit = (number >> bit_position) & 1
            if current_bit not in current_node.children:
                current_node.children[current_bit] = TrieNode()
            current_node = current_node.children[current_bit]
            current_node.min_value_in_subtree = min(current_node.min_value_in_subtree, number)
            current_node.max_value_in_subtree = max(current_node.max_value_in_subtree, number)

    def query(self, number_x, target_xor_prefix):
        current_node = self.root
        for bit_position in range(self.bit_length - 1, -1, -1):
            if not current_node:
                return False
            
            target_xor_bit = (target_xor_prefix >> bit_position) & 1
            bit_of_x = (number_x >> bit_position) & 1
            
            # We need a number 'y' such that (bit_of_x ^ bit_of_y) = target_xor_bit.
            required_bit_of_y = bit_of_x ^ target_xor_bit
            
            # Check if a valid pair exists in the other branch of the Trie.
            other_branch_node = current_node.children.get(1 - required_bit_of_y)
            if other_branch_node and other_branch_node.min_value_in_subtree <= number_x:
                return True
            
            current_node = current_node.children.get(required_bit_of_y)

        return False

class Solution:
    def maximumStrongPairXor(self, nums):
        sorted_numbers = sorted(nums)
        max_possible_value = 2 * sorted_numbers[-1]
        if max_possible_value == 0:
            return 0
        bit_length = max_possible_value.bit_length()
        
        max_xor_result = 0

        # Build the answer bit by bit, from most significant to least significant.
        for bit_position in range(bit_length - 1, -1, -1):
            potential_max_xor = max_xor_result | (1 << bit_position)
            is_possible = False
            
            # This structure will let us efficiently query for partners that satisfy the XOR prefix.
            trie_for_prefixes = Trie(bit_length)
            for number in sorted_numbers:
                trie_for_prefixes.insert(number)

                # For each number, we check if there's a previously inserted number that's a strong pair
                # and also satisfies the potential maximum XOR we're currently testing.
                if trie_for_prefixes.query(number, potential_max_xor):
                    is_possible = True
                    break
            
            if is_possible:
                max_xor_result = potential_max_xor
                
        return max_xor_result

Big(O) Analysis

Time Complexity
O(n log n + n log^2 M) – Sorting the values costs O(n log n). The bit width is logarithmic in the largest value M, because the field is sized from twice that largest value. For every bit, every value is inserted and queried, and each walk visits one node per bit. Doing that for every value and every bit costs O(n log^2 M). Adding the sort gives O(n log n + n log^2 M).
Space Complexity
O(n log M) – The sorted copy stores n values. One trie exists at a time, and each insertion adds at most one new node per bit. Across n values the trie therefore holds O(n log M) nodes, each with a constant amount of child and range data. The previous trie is discarded before the next bit builds another. Extra space is O(n log M).

Edge Cases

The list contains one value
How to Handle:
The direct search pairs that value with itself and records an exclusive-or of zero.
Two values are equal
How to Handle:
Their exclusive-or is zero, so the direct search does not raise its maximum unless another strong pair is larger.
The values are too far apart for any mixed pair to be strong
How to Handle:
The direct search returns zero, because only a value paired with itself qualifies.
A later strong pair has a larger exclusive-or than the pairs seen so far
How to Handle:
Replace the recorded maximum with that pair's exclusive-or.
Twice the largest value is zero
How to Handle:
Return zero from the bit search before any trie is built.
The trie query reports that the candidate prefix is possible
How to Handle:
Keep that bit in the running answer and continue with the lower bits.
0/25 completed