# Hard | LeetCode 2147. Number of Ways to Divide a Long Corridor

## Intuition

- Dynamic programming (bottom-up approach).
- Based on hint 1 (divide the corridor into segments):
- There will be no solution if the number of seats is odd.
- Divide
`corridor`

into multiple groups; each group contains**exactly**two seats and several plants.

- Based on hint 3 (if there are k plants between two adjacent segments, there are k + 1 positions (ways) you could install the divider):
- There will be
`nbOfPlants + 1`

ways to install a divider between two successive groups. `nbOfPlants`

is the number of plants between two successive groups (i.e., ignore the plants inside a single group).

- There will be
- The answer is the number of ways to place a divider between each successive group times with each other.
- Define the answer as
`long`

to prevent potential overflows.

## Approach

- Initialise
`nbOfSeats`

and`nbOfPlants`

to 0, and initialise`ans`

to 1 (assume that there are at least two seats in the corridor). - Range over
`corridor`

(say`corridor[i]`

as`c`

):- Increase
`nbOfSeats`

if`c`

is a seat. - If
`c`

is a plant:- Increase
`nbOfPlants`

if we have already found a group (`nbOfSeats == 2`

). - Otherwise, the plant is inside a single group, and we should ignore it.

- Increase
- After reaching the start of the next group (
`nbOfSeats == 3`

):- Update
`ans`

. - Set
`nbOfSeats`

to 1 (i.e., move to the next group of seats), and clear`nbOfPlants`

.

- Update

- Increase
- Return 0 if
`nbOfSeats != 2`

(i.e., there’s an odd number of seats). - Otherwise, return
`ans`

.

Pseudocode of `numberOfWays()`

:

1 | numberOfWays(corridor): |

## Complexity

Time complexity: $O(n)$.

- $n$ iterations to calculate the answer.

Space complexity: $O(1)$.

## Code

1 | class Solution { |