code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

062 Unique Paths

/**
 * 
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

/* 
 * A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
 * 
 * The robot can only move either down or right at any point in time. The robot is trying to reach 
 * the bottom-right corner of the grid (marked 'Finish' in the diagram below).
 * 
 * Example 1:
 * 
 * Input: m = 3, n = 2
 * Output: 3
 * Explanation:
 * From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
 * 1. Right -> Right -> Down
 * 2. Right -> Down -> Right
 * 3. Down -> Right -> Right
 * Example 2:
 * 
 * Input: m = 7, n = 3
 * Output: 28
 *  
 * 
 * Constraints:
 * 
 * 1 <= m, n <= 100
 * It's guarantee
*/

function uniquePaths(m, n) {
  let rows = new Array(m).fill(0);
  let matrix = rows.map(v => new Array(n).fill(1))
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      matrix[i][j] = matrix[i][j-1] + matrix[i-1][j]
    }    
  }
  return matrix[m-1][n-1]
}

test('unique Paths', () => {
  expect(uniquePaths(3, 2)).toEqual(3)
  expect(uniquePaths(7, 3)).toEqual(28)
});

Created 2020-03-20T20:39:49+00:00, updated 2020-03-25T13:38:42+00:00 · History · Edit