Number of ways from the top-left to the bottom-right in a 2D array ✅¶

Write a program that counts how many ways you can go from the top-left to the bottom-right in a 2D array. All moves must either go right or down.

:::tip Hint: If i > 0 and j > 0, you can get to (i; j) from (i − 1; j) or (j − 1; i).

If i = 0 or j = 0, there is only one way to get to (i; j) from the origin.

Time complexity: \(O(NM)\) Space complexity: \(O(NM)\) :::

alt

C# Solution¶

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class NumberOfWaysToButtomRight2DArray
  {
    public static int NumberOfWays(int row, int col)
    {
      return NumberOfWaysToBottom(row - 1, col - 1, new int[row, col]);
    }

    private static int NumberOfWaysToBottom(int row, int col, int[,] numOfWays)
    {
      if (row == 0 || col == 0) return 1;

      if (numOfWays[row, col] == 0)
      {
        var waysToTop = row == 0 ? 0 : NumberOfWaysToBottom(row - 1, col, numOfWays);
        var waysToLeft = col == 0 ? 0 : NumberOfWaysToBottom(row, col - 1, numOfWays);
        numOfWays[row, col] = waysToLeft + waysToTop;
      }

      return numOfWays[row, col];
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class NumberOfWaysToButtomRight2DArrayTests
  {
    [Fact]
    public void TestName()
    {
      Assert.Equal(70, NumberOfWaysToButtomRight2DArray.NumberOfWays(5, 5));
    }
  }
}