Number of path - Feb. 17, 2018 - 4:00 pm mock interview

NumberOfPath_Feb17_2018.cs

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 
  */