Out of Boundary Paths - Leetcode 576 - Python

[@AMakYu]

That 3D DP solution is wild. I was able to get the memoization solution on my own today, but I still have trouble translating that into bottom up approaches. But honestly, I've come a long ways already for being able to solve a problem like this by myself with memo. Thanks Neet!

[@zaki_1337]

is it necessary to learn the iterative solutions? do interviewers ask that?

[@aswinnath8580]

they will mostly expect that one if you give only the memo one there is no guarantee you will pass the round unless if its a very hard dp problem or not a trivial one. @@zaki_1337

[@AMakYu]

@@zaki_1337 I think it depends on your interviewer. I think most would probably accept memo, but I had a friend who had a TikTok interview where he tried memo for a problem but it was hitting a stack limit, indicating that they wanted the bottom up approach.

[@zaki_1337]

@@AMakYu oh :/

[@vm1662]

3D DP it is! I was thinking in terms of 2D and didn't know how to memoize it. Thanks NeetCode!

[@felixx2012]

Thanks for doing these daily problems. Very helpful

[@gmh14]

You mentioned a BFS solution wouldn't work but in one of my approaches I considered it and it somehow worked. Gave TLE at 22/94 but it could possibly be optimized?
# BFS solution
MOD = 10**9 + 7
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
queue = [(startRow, startColumn, maxMove)]
res = 0
while queue:
node_i, node_j, curMoves = queue.pop(0)
if curMoves > 0:
curMoves -= 1
for delrow, delcol in directions:
new_i, new_j = node_i + delrow, node_j + delcol
if not (0

[@pastori2672]

i actually got MLE on a bfs solution and a TLE on the dfs one xd

[@firehouse1395]

Your solutions are so real, nothing fancy, they are simple and easy to understand

[@legendary5320]

One thing I was confused about the recursive brute force solution is that why are we allowed to go back to the node we just came from? Would that not consitute a path?

[@EduarteBDO]

The second solution is less efficient in LC because we are calculating the possibilities for all positions in the grid. Different from the dfs solution were we calculate for the startRow/startCol, but in a case where we wanted to calculate all of them the DP is much more faster and memory efficient.

[@MP-ny3ep]

Great explanation as always. Thank you .

[@rostislav_engineer]

thanks, man

[@krateskim4169]

Thank you so much

[@priyanshuganatra]

Memoization solution is pretty straightforward, I dunno bout da tabu sol tho

[@sankalpchordia5245]

Well explained

[@shashankjoshi8250]

For a Brute Force Memoization I am getting TLE.

[@unknown-ut5qn]

always on top

[@Kaviarasu_NS]

Thanks ❤

[@EduarteBDO]

for the if statments I mada a helper function:
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
ROWS,COLS = m,n
MODULO = pow(10,9)+7
curGrid = [[0] * COLS for _ in range(ROWS)]
prevGrid = [[0] * COLS for _ in range(ROWS)]
def helper(r,c):
if r < 0 or c < 0 or r == ROWS or c == COLS:
return 1
return prevGrid[r][c]
for _ in range(maxMove):
for r in range(ROWS):
for c in range(COLS):
val = helper(r+1,c)
val += helper(r-1,c)
val += helper(r,c+1)
val += helper(r,c-1)
val %=MODULO
curGrid[r][c] = val
prevGrid, curGrid = curGrid,prevGrid
return prevGrid[startRow][startColumn]

[@sankalppatil2994]

💪💪

[@walkastray007]

Not to brag NeetCode, but I got the 15 view on this video.

[@SC2Edu]

did you solve it at least? :D

[@XEQUTE]

day 26
Leetcode

[@shaco6630]

Great explanation as usual!
A suggestion, is it not a bit more readible to remove the if/else checks with something similar to this? (I added this vcrsion to neetcode github if that's ok, instead of having all the if statements)
class Solution {
fun findPaths(m: Int, n: Int, maxMove: Int, startRow: Int, startColumn: Int): Int {
val mod = 1_000_000_007
val dirs = intArrayOf(0, 1, 0, -1, 0)
val dp = Array (m) { Array (n) { LongArray (maxMove + 1) } }
for (k in 1..maxMove) {
for (i in 0 until m) {
for (j in 0 until n) {
for (dir in 0..3) {
val i2 = i + dirs[dir]
val j2 = j + dirs[dir + 1]
if (i2 < 0 || i2 == m || j2 < 0 || j2 == n)
dp[i][j][k]++
else
dp[i][j][k] = (dp[i][j][k] + dp[i2][j2][k - 1]) % mod
}
}
}
}
return dp[startRow][startColumn][maxMove].toInt()
}
}