Hill Climbing Swiggy Python Interview Question

You're attempting to climb a hill—not in a mathematical optimization sense (check out hill climbing for that), but literally outside, touching grass, and trying to climb a hill.

Imagine there are steps carved into the hill. You can go up using either 1 or 2 steps at a time.

Your task is to return the number of distinct ways to reach the top of the hill.

Example 1:

Input:
Output:
Explanation: There are three distinct ways to climb to the top of a hill with 3 steps:

1. Take 1 step, then 1 step, then 1 step.
2. Take 1 step, then 2 steps.
3. Take 2 steps, then 1 step.

Example 2:

Input:
Output:
Explanation: There are five distinct ways to climb to the top of a hill with 4 steps:

1. Take 1 step, then 1 step, then 1 step, then 1 step.
2. Take 1 step, then 1 step, then 2 steps.
3. Take 1 step, then 2 steps, then 1 step.
4. Take 2 steps, then 1 step, then 1 step.
5. Take 2 steps, then 2 steps.

Recursive Approach (Brute Force)

Let's start with a basic recursive solution. At each step , we need to know the number of ways to reach the previous two steps ( and ), since we can reach step from either of those.

The recursive function has two key parts:

• Base Case: When is 0 or 1, there’s only 1 way to reach that step, so we return 1.
• Recursive Case: For any other step , we calculate . This gives the total ways to reach step by combining the ways to get to the previous two steps.

Here's the code:

This approach is simple but inefficient for larger due to repeated calculations.

Memoization

To make our solution more efficient, we can store previously calculated results in a dictionary. This prevents redundant calculations and speeds up the process by allowing us to reuse computed results.

With memoization, the code looks like this:

With this approach, each step’s result is calculated only once, making it more efficient for larger inputs.

Iterative Approach

An iterative approach allows us to build up the solution step by step, using an array to store the number of ways to reach each step. Starting from the base cases, we calculate the number of ways to reach each subsequent step up to .

Here's the code:

This approach has a time complexity of $O(n)$ and uses $O(n)$ space.

Space Optimization

In the iterative approach, we can further optimize space usage by only storing the results of the last two steps. Since each step calculation only depends on the previous two results, we can avoid using an entire array and instead use two variables to track the last two results.

Here's the code:

This approach is also $O(n)$ in time complexity but reduces space complexity to $O(1)$, making it the most efficient in terms of memory usage.