Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Number of path - Feb. 17, 2018 - 4:00 pm mock interview
using System;
class Solution
{
public static int NumOfPathsToDest(int n)
{
if( n <= 0 )
return 0;
if(n == 1)
return 1;
// O(n * n ) matrix -> O(n) space -> O(1) -> two variables
var SIZE = n - 1;
var currentRow = new int[SIZE];
var previousRow = new int[SIZE];
for(int row = 0; row < SIZE ; row++)
{
for(int col = 0; col < SIZE ; col++)
{
if(row == 0)
{
currentRow[col] = 1;
}
else if(row <= col)
{
currentRow[col] = currentRow[col - 1] + previousRow[col]; // left one + underneath
}
}
// copy array from current to previous
for(int col = row; col < SIZE; col++)
{
previousRow[col] = currentRow[col];
}
}
return currentRow[SIZE - 1];
}
static void Main(string[] args)
{
}
}
/*
keywords:
cannot cross the diagonal border
only up or right
start from (0,0 )
ask: number of possible paths to given n - right top corner
x x x x x
x x x x 14
x x x 5 14 Dest(4, 4) = 5
x x 2 5 9
x 1 2 3 4 -> from left to right, start from row <= col, previous row, left side -> iteration
1 1 1 1 1 -> row by row - line 47
Time complexity: O(n * n)
space complexity: O(n * n )
previous row O(n) -> previous/ current row -> O(n) ->
two variable -> left one
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment