The lesson says the optimal space complexity is O(n). Can we reduce this to constant space?
def climb_stairs(nums):
old = new = 1
for i in range(2, nums + 1):
new, old = old + new, new
return new
Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Climbing Stairs - Grokking Coding Interview Patterns in Python
Hello @Isaac_Haseley,
The solution can be achieved with constant space complexity. However, in this specific lesson, the suggestion of achieving O(n) space complexity typically refers to solving it using dynamic programming solutions, since the lesson is categorized under that topic. The suggested optimal dynamic programming code is also presented in the "Figure it out” section for further clarity.
Hey @Dian_Us_Suqlain!
Yes! I started with the following notes:
dp array of length n + 1
first two items are 1 and 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
we only look at the previous two entries. can we optimize to constant space?
The dynamic programming lessons encourage us to optimize space where possible, so it seemed consistent with the dynamic programming approach to remove the unnecessary array.