Out of Boundary Paths - Leetcode 576 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/out-of-...
0:00 - Read the problem
0:30 - Drawing Recursive solution
5:23 - Coding Recursive
8:59 - Drawing DP solution
12:35 - Coding DP solution
leetcode 576
#neetcode #leetcode #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!

[@pastori2672]

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

[@felixx2012]

Thanks for doing these daily problems. Very helpful

[@firehouse1395]

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

[@MP-ny3ep]

Great explanation as always. Thank you .

[@sankalpchordia5245]

Well explained

[@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?

[@Kaviarasu_NS]

Thanks ❤

[@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.

[@unknown-ut5qn]

always on top

[@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

[@krateskim4169]

Thank you so much

[@rostislav_vat]

thanks, man

[@priyanshuganatra]

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

[@sankalppatil2994]

💪💪

[@shashankjoshi8250]

For a Brute Force Memoization I am getting TLE.

[@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

[@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]

[@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()
}
}