What is the time complexity of unique paths with obstacles?

Worst case O(rows × cols). Space complexity is O(rows × cols), or O(cols) with one row. Without obstacles the answer is the binomial coefficient C(R+C−2, R−1).

Unique paths with obstacles

easy

Right and down only, so the ways to reach a cell are the ways to reach the cell above plus the one to its left. An obstacle is just a zero - no branching logic needed.

Worst O(rows × cols)Space O(rows × cols), or O(cols) with one row

Loading the unique paths with obstacles engine…

Where to go next

House robber

easy

Two choices per house, and the table collapses to two variables.

Coin change (DP)

medium

One subproblem per amount, and no first choice can trap it.

Longest common subsequence

medium

Match means diagonal; mismatch means the better of two.