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