2147. Number of Ways to Divide a Long Corridor - Explanation

Problem Link



1. Dynamic Programming (Top-Down)

Intuition

We need to divide the corridor so each section has exactly two seats. The key insight is that after placing two seats in a section, we have a choice: place the divider immediately after the second seat, or delay it through any number of plants. Each plant between the second seat of one section and the first seat of the next section represents a possible divider position.

Algorithm

  1. Define a recursive function dfs(i, seats) where i is the current index and seats counts how many seats are in the current section (0, 1, or 2).
  2. Base case: If we reach the end of the corridor, return 1 if we have exactly 2 seats (valid section), otherwise 0.
  3. If we already have 2 seats in the current section:
    • If the current position is a seat, we must start a new section (reset seats to 1).
    • If it's a plant, we can either place the divider here (reset to 0) or continue without dividing (keep at 2).
  4. If we have fewer than 2 seats, count the seat if present and continue.
  5. Use memoization to cache results.
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        cache = [[-1] * 3 for i in range(len(corridor))]  # (i, seats) -> count

        def dfs(i, seats):
            if i == len(corridor):
                return 1 if seats == 2 else 0
            if cache[i][seats] != -1:
                return cache[i][seats]

            res = 0
            if seats == 2:
                if corridor[i] == "S":
                    res = dfs(i + 1, 1)
                else:
                    res = (dfs(i + 1, 0) + dfs(i + 1, 2)) % mod
            else:
                if corridor[i] == "S":
                    res = dfs(i + 1, seats + 1)
                else:
                    res = dfs(i + 1, seats)

            cache[i][seats] = res
            return res

        return dfs(0, 0)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up by iterating from the end of the corridor to the beginning. For each position, we compute the number of ways based on whether we have 0, 1, or 2 seats in the current section.

Algorithm

  1. Create a DP table where dp[i][seats] represents the number of ways to divide from index i onward with seats seats in the current section.
  2. Initialize dp[n][2] = 1 (reaching the end with exactly 2 seats is one valid way).
  3. Iterate backward through the corridor:
    • For each position and seat count, apply the same transitions as the top-down approach.
  4. Return dp[0][0] (starting from index 0 with 0 seats).
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        n = len(corridor)
        dp = [[0] * 3 for _ in range(n + 1)]
        dp[n][2] = 1

        for i in range(n - 1, -1, -1):
            for seats in range(3):
                if seats == 2:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][1]
                    else:
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
                else:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][seats + 1]
                    else:
                        dp[i][seats] = dp[i + 1][seats]

        return dp[0][0]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Dynamic Programming (Space Optimized)

Intuition

Since each row of the DP table only depends on the next row, we can reduce space by maintaining just a single array of size 3 (for the three possible seat counts).

Algorithm

  1. Initialize a DP array of size 3 with dp[2] = 1.
  2. Iterate backward through the corridor:
    • Create a new DP array and compute transitions based on whether the current position is a seat or plant.
    • Replace the old DP array with the new one.
  3. Return dp[0].
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        dp = [0, 0, 1]

        for i in reversed(corridor):
            new_dp = [0] * 3
            for seats in range(3):
                if seats == 2:
                    new_dp[seats] = dp[1] if i == 'S' else (dp[0] + dp[2]) % MOD
                else:
                    new_dp[seats] = dp[seats + 1] if i == 'S' else dp[seats]
            dp = new_dp

        return dp[0]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

4. Combinatorics

Intuition

Instead of DP, we can think combinatorially. First, collect all seat positions. If the count isn't even or is less than 2, there's no valid way. Otherwise, between every pair of seats (the 2nd and 3rd, 4th and 5th, etc.), we can place the divider at any position including those occupied by plants. The number of choices at each gap is the distance between consecutive pairs of seats.

Algorithm

  1. Collect the indices of all seats in a list.
  2. If the seat count is less than 2 or odd, return 0.
  3. For every pair of adjacent seat groups (positions 1 and 2, positions 3 and 4, etc.), multiply res by the gap size seats[i+1] - seats[i].
  4. Return res modulo 10^9 + 7.
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        seats = [i for i, c in enumerate(corridor) if c == "S"]

        length = len(seats)
        if length < 2 or length % 2 == 1:
            return 0

        res = 1
        for i in range(1, length - 1, 2):
            res = (res * (seats[i + 1] - seats[i])) % mod

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

5. Combinatorics (Optimal)

Intuition

We can optimize the combinatorics approach by not storing all seat positions. Instead, we track the count of seats and the position of the previous seat. Whenever we complete a pair (seat count becomes even and greater than 2), we multiply by the gap between the current seat and the previous one.

Algorithm

  1. Initialize count = 0, res = 1, and prev = -1 to track the position of the last seat.
  2. Iterate through the corridor:
    • When a seat is found, increment count.
    • If count > 2 and count % 2 == 1 (meaning we just started a new section), multiply res by the distance from prev.
    • Update prev to the current position.
  3. If count >= 2 and count % 2 == 0, return res; otherwise return 0.
class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 1_000_000_007
        count = 0
        res = 1
        prev = -1

        for i, c in enumerate(corridor):
            if c == 'S':
                count += 1
                if count > 2 and count % 2 == 1:
                    res = (res * (i - prev)) % mod
                prev = i

        return res if count >= 2 and count % 2 == 0 else 0

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)