9. Kadane, Dutch Flag & Moore's Voting
Three famous one-pass array algorithms and their variations.
🎬 Episodes 11–13: video coming soon
Your progress0 of 9
2easy
7medium
0hard
Understand the topic
Three classic one-pass algorithms. Kadane's algorithm finds the best subarray sum by deciding at each step: extend the current run, or start fresh? The Dutch National Flag sorts 0s, 1s and 2s in one pass with three pointers (low, mid, high). Moore's voting finds the majority element by letting different votes cancel each other out.
They all run in O(n) time with O(1) extra space, which is why interviewers love them.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Majority Element #169 | Moore's voting | Easy | LeetCode ↗ | |
| 2 | Sort Array By Parity #905 | Two-way partition | Easy | LeetCode ↗ | |
| 3 | Maximum Subarray #53 | Kadane | Medium | LeetCode ↗ | |
| 4 | Maximum Product Subarray #152 | Kadane with min & max | Medium | LeetCode ↗ | |
| 5 | Maximum Sum Circular Subarray #918 | Kadane max & min | Medium | LeetCode ↗ | |
| 6 | Maximum Absolute Sum of Any Subarray #1749 | Kadane max & min | Medium | LeetCode ↗ | |
| 7 | Sort Colors #75 | Dutch National Flag | Medium | LeetCode ↗ | |
| 8 | Majority Element II #229 | Extended Moore's voting | Medium | LeetCode ↗ | |
| 9 | Maximum Subarray Sum with One Deletion #1186 | Kadane with two states | Medium | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.