Unique Paths

Description

doc

Solutions

[Time Exceeded] First Idea

const DIRS = [
  [1, 0],
  [0, 1],
]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const [endX, endY] = [n - 1, m - 1]
  let queue = [[0, 0]]
  let pathCount = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    if (x === endX && y === endY) {
      pathCount++
      continue
    }

    DIRS.forEach(([_x, _y]) => {
      const newX = x + _x
      const newY = y + _y

      if (newX > endX || newY > endY) {
        return
      }

      queue.push([newX, newY])
    })
  }

  return pathCount
}

• Time Complexity: O(?)
• Space Complexty: O(1)

[Time Exceeded] Recursive Version

const DIRS = [
  [-1, 0],
  [0, -1],
]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  if (!(m - 1) && !(n - 1)) {
    return 1
  }

  return DIRS.reduce((acc, [_x, _y]) => {
    const newX = n + _x
    const newY = m + _y

    if (!newX || !newY) {
      return acc
    }

    return acc + uniquePaths(newY, newX)
  }, 0)
}

DP

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let matrics = Array(n)
    .fill(0)
    .map(() => Array(m).fill(0))

  for (let y = 0; y < m; y++) {
    for (let x = 0; x < n; x++) {
      if (!x && !y) {
        matrics[x][y] = 1
        continue
      }

      const left = matrics[x - 1]?.[y] ?? 0
      const top = matrics[x]?.[y - 1] ?? 0
      matrics[x][y] = left + top
    }
  }

  return matrics[n - 1][m - 1]
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)