Number of Ways to Stay in the Same Place After Some Steps

Ah, the classic dilemma of wanting to move forward in life but somehow ending up right where you started. This problem is like trying to walk in a straight line while simultaneously being pulled back by an invisible force—like your mom calling you back home when you’re just about to leave for a party.

In this delightful little exercise, you’re tasked with figuring out how many ways you can stay in the same place after taking a certain number of steps. Imagine you’re at a party, and every time you take a step to the left, your friend pulls you back to the right. How many different ways can you end up right back where you started after a set number of steps? Spoiler alert: it’s not as straightforward as it sounds!

Links to Other Solutions

Java Solution

Python Solution

Code Solution


class Solution {
 public:
  int numWays(int steps, int arrLen) {
    constexpr int kMod = 1'000'000'007;
    const int n = min(arrLen, steps / 2 + 1);
    vector dp(n);
    dp[0] = 1;

    while (steps-- > 0) {
      vector newDp(n);
      for (int i = 0; i < n; ++i) {
        newDp[i] = dp[i];
        if (i - 1 >= 0)
          newDp[i] += dp[i - 1];
        if (i + 1 < n)
          newDp[i] += dp[i + 1];
        newDp[i] %= kMod;
      }
      dp = std::move(newDp);
    }

    return dp[0];
  }
};

Approach Explanation

The code uses dynamic programming to keep track of the number of ways to stay at each index after a certain number of steps. It initializes a vector dp where each index represents a position, and the value at that index represents the number of ways to reach that position. For each step, it calculates the new number of ways to stay at each index based on the previous step's values. It cleverly uses modular arithmetic to avoid overflow.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(steps * arrLen)
Space Complexity	O(arrLen)

Real-World Example

Imagine you’re at a dance party, and every time you try to move left to show off your moves, your friends pull you back to the center. After a few attempts, you realize you’ve danced in a circle and ended up right back where you started. This problem is just like that—counting all the ways you can cha-cha your way back to the center after a series of steps!