Leetcode 164: Maximum gap (Series 1 of 5)

July 3, 2018

Introduction

It is a hard level algorithm called Leetcode 164: Maximum gap. The optimal solution is to use linear time complexity, so the array cannot be sorted using comparison sort. However, if the bucket sort can be applied, and then the array can be sorted using linear time. How do we know the bucket size?

I spent over 20 minutes today to think about the solution. I did think about maximum and minimum value of the array, but what is minimum gap for the array? Can we use the minimum gap to define a bucket? I need those two hints to help me come out the solution.

My practice in 2015

Here are some facts I like to review related to the algorithm.

1. I wrote more than 2 blogs about the algorithm: Leetcode 164: Maximum gap in 2015. Here are the links.
2. I did not submit the code through Leetcode online judge.
I should have submitted the solution.
3. The C# code I wrote could not be found. The gist's link is broken.
4. I spent more than four hours to work on the algorithm in 2015.

My practice in 2018

I plan to write C# code again. It is so exciting to write a hard level algorithm, and understand how important it is to lower down time complexity.

Here is C# code passing online judge.