I recently solved the Leetcode 868. Binary Gap problem in Go, and encountered something interesting.
My supposedly worst solution — with an O(n log n) time complexity — ended up beating 100% of submissions in runtime.
Meanwhile, the "optimal" space version used more memory.
That made me realise something important:
Big-O complexity might not always dominate — especially when input size is tightly bounded.
In this case, the maximum binary length was only 32 bits. Sorting a handful of integers becomes effectively constant time. The theory said one thing. The measurements told another story.
I wrote a short breakdown explaining:
- Why does this happen
- How online judges measure performance
- When asymptotic complexity truly matters
- And how to implement a truly optimal bitwise version
If you're into performance reasoning and algorithm trade-offs, you might enjoy this one.
https://dev.to/rezzcode/leetcode-sunday-4-1025