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
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.