# 15.10.2023 [1269. Number of Ways to Stay in the Same Place After Some Steps]
Number of ways to return to `0` after moving `left, right` or `stay` `steps` time
15.10.2023
1269. Number of Ways to Stay in the Same Place After Some Steps hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/371
Problem TLDR
Number of ways to return to 0
after moving left, right
or stay
steps
time
Intuition
We can do a brute force Depth First Search, each time moving position to the left
, right
or stay, adjusting steps
left. After all the steps used, we count the way if it is at 0
position.
The result will only depend on the inputs, so can be cached.
Approach
one optimization can be to use only half of the array, as it is symmetrical
use
when
instead ofif - else
, because you can forgetelse
:
if (some) 0L
if (other) 1L // must be `else if`
Complexity
Time complexity:
O(s^2), max index can be no more than number of steps, as we move by 1 at a timeSpace complexity:
O(s^2)
Code
fun numWays(steps: Int, arrLen: Int): Int {
val m = 1_000_000_007L
val dp = mutableMapOf<Pair<Int, Int>, Long>()
fun dfs(i: Int, s: Int): Long = dp.getOrPut(i to s) { when {
s == steps && i == 0 -> 1L
i < 0 || i >= arrLen || s >= steps -> 0L
else -> {
val leftRight = (dfs(i - 1, s + 1) + dfs(i + 1, s + 1)) % m
val stay = dfs(i, s + 1)
(leftRight + stay) % m
}
} }
return dfs(0, 0).toInt()
}