Greedy Algorithms8 sections · 316 units
Open in Course

Remove K Digits - Why Greedy

Local removal helps globally

Why does removing the first digit larger than the next one minimize the result? Numbers are compared left to right. The leftmost digits have the most impact. A large digit early hurts more than a large digit late.

When you see a peak (digit followed by smaller digit), removing the peak always reduces the number. Counter-example: in '5432154321', removing any non-leftmost digit leaves a larger number than removing '55'.

This greedy choice is safe because you fix the leftmost problem first, which has the biggest effect on the final number.