Challenge: Collect Coins in Minimum Steps

In this lesson, you will find the minimum number of steps it takes to collect the coins given an array of the heights of vertically stacks of coins.

Coin collection in minimum steps

Suppose you are given many adjacent piles of vertically stacked coins.

You are required to calculate the minimum number of steps needed to collect these coins (minimum number of straight lines that pass through all the coins). In one step you can collect either one horizontal or one vertical line of coins, and collected coins should be continuous.

For instance, in the given illustration, the minimum number of lines is 5.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.