1

Question

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Constraints:
1 <= nums.length <= 2 * 105
0 <= nums[i] <= 231 - 1

Approach: I have solved using Triewhere I add each elements and after adding I search for the number which can result in maximum xor.

Solution:

class TreeNode:
    def __init__(self, value = '-1'):
        self.val = value
        self.left = None
        self.right = None
class Solution(object):
    def findMaximumXOR(self, a):
        root = TreeNode()
        msf = float('-inf')
        for i in a:
            bits = format(i, 'b').zfill(31)
            node = root
            for bit in bits:
                if bit == '0' and node.left:
                    node = node.left
                elif bit == '0':
                    new_node = TreeNode('0')
                    node.left = new_node
                    node = new_node
                
                if bit == '1' and node.right:
                    node = node.right
                elif bit == '1':
                    new_node = TreeNode('1')
                    node.right = new_node
                    node = new_node
            
            ssf=''
            node = root
            for bit in bits:
                if bit == '0' and node.right:
                    ssf += '1'
                    node = node.right
                elif bit == '1' and node.left:
                    ssf += '1'
                    node = node.left
                elif node.left:
                    ssf += '0'
                    node = node.left
                else:
                    ssf += '0'
                    node = node.right

            val = int(ssf, 2)
            msf = max(msf, val)
        return msf

Question: What is the time complexity of the above solution? In my opinion it is O(N) where N is the number of element in nums.

trincot
  • 317,000
  • 35
  • 244
  • 286
Akanksha
  • 49
  • 1
  • 8
  • Yes, this is linear. The inner loops are bound above and below by the size of the integers (31 bits) and so are constant, the only other loop is linear. This solution takes up a large constant amount of space as well, specifically O(2^32-1) worst case (which is O(1), but large) space. – Welbog Aug 22 '22 at 19:36
  • Still I am getting Time Limit Exceeded for this approach. The expected time complexity is `O(N)` – Akanksha Aug 22 '22 at 19:47
  • 2
    It's O(N) with a huge constant factor. A single iteration of the inner loop has a large constant factor because you are creating and inserting a node into the trie. To make matters worse, the inner loop always runs 31 times. So the large constant factor for each iteration is multiplied by 31, making it a huge constant factor. To understand the magnitude of that constant factor, consider that an O(nlogn) solution to the problem would actually have better performance for the given constraints, since the worst case would be `log(n) = log(2e5) ≈ 18` which is less than 31. – user3386109 Aug 22 '22 at 20:23
  • Strings are slow, you should use bitwise operations to get the bits in such problems. – IVlad Aug 22 '22 at 23:10
  • @Welbog that worst case is way overestimated because it will be nowhere near that under the given constraints for the size of the array. – IVlad Aug 22 '22 at 23:29

2 Answers2

1

your time complexity is O(N*Log2(max(nums))).

Mohammad Resli
  • 27
  • 3
0

It is actually O(n*(log2(max_num)**2)), because for each bit you do string concatenation, which is not O(1) in Python:

        for bit in bits: # this entire for loop is O(bits**2)
            if bit == '0' and node.right:
                ssf += '1' # this is not O(1), it is O(len(bits))
        ...

Avoid strings, use bitwise operators to get true O(n*log(max_num)).

IVlad
  • 43,099
  • 13
  • 111
  • 179