How hard is LeetCode 2935. Maximum Strong Pair XOR II?

LeetCode 2935. Maximum Strong Pair XOR II is rated Hard on LeetCode.

What is the time complexity of LeetCode 2935. Maximum Strong Pair XOR II?

The Python solution on this page runs in O(n \times \log M).

What is the space complexity of LeetCode 2935. Maximum Strong Pair XOR II?

The Python solution on this page uses O(n \times \log M) auxiliary space.

What topics does LeetCode 2935. Maximum Strong Pair XOR II cover?

LeetCode 2935. Maximum Strong Pair XOR II is tagged Bit Manipulation, Trie, Array, Hash Table and Sliding Window on LeetCode.

Maximum Strong Pair XOR II — LeetCode 2935 Python Solution

HardBit ManipulationTrieArrayHash TableSliding Window

Problem: #2935
Pattern: Trie
Reading time: 9 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Trie:
    __slots__ = ("children", "cnt")

    def __init__(self):
        self.children: List[Trie | None] = [None, None]
        self.cnt = 0

    def insert(self, x: int):
        node = self
        for i in range(20, -1, -1):
            v = x >> i & 1
            if node.children[v] is None:
                node.children[v] = Trie()
            node = node.children[v]
            node.cnt += 1

    def search(self, x: int) -> int:
        node = self
        ans = 0
        for i in range(20, -1, -1):
            v = x >> i & 1
            if node.children[v ^ 1] and node.children[v ^ 1].cnt:
                ans |= 1 << i
                node = node.children[v ^ 1]
            else:
                node = node.children[v]
        return ans

    def remove(self, x: int):
        node = self
        for i in range(20, -1, -1):
            v = x >> i & 1
            node = node.children[v]
            node.cnt -= 1


class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        tree = Trie()
        ans = i = 0
        for y in nums:
            tree.insert(y)
            while y > nums[i] * 2:
                tree.remove(nums[i])
                i += 1
            ans = max(ans, tree.search(y))
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log M)
Space	O(n \times \log M) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 2935. Maximum Strong Pair XOR II is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2935. Maximum Strong Pair XOR II?: LeetCode 2935. Maximum Strong Pair XOR II is rated Hard on LeetCode.
What is the time complexity of LeetCode 2935. Maximum Strong Pair XOR II?: The Python solution on this page runs in O(n \times \log M).
What is the space complexity of LeetCode 2935. Maximum Strong Pair XOR II?: The Python solution on this page uses O(n \times \log M) auxiliary space.
What topics does LeetCode 2935. Maximum Strong Pair XOR II cover?: LeetCode 2935. Maximum Strong Pair XOR II is tagged Bit Manipulation, Trie, Array, Hash Table and Sliding Window on LeetCode.