Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Collect Coins in Minimum Steps

Explore how to solve the collect coins in minimum steps problem using a divide-and-conquer approach. Understand the recursive method that splits the problem into subproblems, and learn how to evaluate and implement minimum steps calculation with clear code explanation and time complexity analysis.

We'll cover the following...

Solution

We can solve this problem using a divide-and-conquer technique as follows:

C# 9.0
using System;
public class Program
{
    /// <summary>
    /// Helper recursive method to calculate the minimum steps required to collect coins from a array.
    /// </summary>
    /// <param name="arr">Array of coin stacks.</param>
    /// <param name="left">Left index of the array.</param>
    /// <param name="right">Right index of the array.</param>
    /// <param name="h">Height of the stack.</param>
    /// <returns>The minimum number of steps to collect coins from the array. Returns 0 if no steps are required.</returns>
    public static int MinimumStepsRecursive(int[] arr, int left, int right, int h)
    {
        // Base Case: When left is greater or equal to right
        if (left >= right)
        {
            return 0;
        }
        // Find the index with the minimum height in the current segment
        int minimumHeight = left;
        for (int i = left; i < right; i++)
        {
            if (arr[i] < arr[minimumHeight])
            {
                minimumHeight = i;
            }
        }
        // Collecting all vertical line coins and horizontal line coins on both sides
        return Math.Min(right - left,
            MinimumStepsRecursive(arr, left, minimumHeight, arr[minimumHeight]) +
            MinimumStepsRecursive(arr, minimumHeight + 1, right, arr[minimumHeight]) +
            arr[minimumHeight] - h);
    }
    /// <summary>
    /// Method which calculates the minimum steps to collect coins from the array
    /// </summary>
    /// <param name="arr">Array of coin stacks.</param>
    /// <returns>The minimum number of steps to collect coins from the array. Returns 0 if no steps are required.</returns>
    public static int MinimumSteps(int[] arr)
    {
        return MinimumStepsRecursive(arr, 0, arr.Length, 0);
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        int[] arr = { 2, 1, 2, 5, 1 };
        Console.WriteLine("Minimum number of steps: " + MinimumSteps(arr));
    }
}

Explanation

If there are no more coins to collect, we are done in zero steps. Otherwise, we have two options:

  • Either we collect each column individually.

  • Or, since the bottom few rows are guaranteed to be filled contiguously, we pick as many contiguous rows from the bottom as possible, then solve the remaining coins problem recursively. The remaining coins will be in two separate sets from left to minimumHeight and minimumHeight + 1 to right. So, two recursive calls will need to be made. So, we take the minimum of the above options.

Here is the ...