Divide and Conquer, No radix/bucket sort, just run each bit, O(n) time


  • 1

    The idea is to run through each bit i, divide the group of numbers into 2 groups: the group of ith bit = 1 and the group of ith bit = 0. Then we can call recursively for each group to find max gap in each group. We also need to compare with min(group 1) - max(group 0).

    Since at each level, we only do linear amount of work, the total running time for 32 levels is still O(n).

    class Solution(object):
        def helper(self, nums, i):
            if len(nums) < 2 or i < 0: return 0
            arr0, arr1 = [], []
            for num in nums:
                if (num>>i)&1 == 0:
                    arr0.append(num)
                else:
                    arr1.append(num)
            gap = max(self.helper(arr0, i-1), self.helper(arr1, i-1))
            if len(arr0) > 0 and len(arr1) > 0:
                gap = max(gap, min(arr1) - max(arr0))
            return gap
        
        def maximumGap(self, nums):
            return self.helper(nums, 31)
    

  • 0
    Z

    @simkieu Did you invented that? Because that's awesome, you can use this method to solve lot of thing in (big O) linear time.


  • 0

    @ZephyrSails Thanks, I came up with the solution myself without looking up anything. I hope it does lol.


  • 0
    R

    Let's say the run time for you helper is f(n), where n is the size of nums. It first enumerates nums, this will take n time units, and then helper is called twice. Assume the ith bit separates nums in two small arrays with size n/2, we then get f(n) = 2f(n/2) + n. Therefore, f(n) = nlogn.

    As analyzed above, your algorithm is actually O(nlogn). But as stated in the problem, 0 <= n <= 2^31, you can bound log n by 31, so in the restricted condition, you might say your algorithm run roughly in O(n) time.


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.