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

• 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)
``````

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

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

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

• This post is deleted!

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