Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

LeetCode 2147 - Number of Ways to Divide a Long Corridor

Problem Understanding

The corridor is represented as a string where each character is either 'S' for a seat or 'P' for a plant. We already have fixed dividers at both ends of the corridor, and we may optionally place additional dividers between adjacent positions.

The goal is to divide the corridor into sections such that every section contains exactly two seats. Plants do not affect validity, since a section may contain any number of plants. The challenge is determining how many distinct ways we can place dividers while satisfying this condition.

A divider may only be placed between two indices. Two arrangements are considered different if at least one divider position differs.

The constraints are important:

The corridor length can be as large as 10^5
A brute-force exploration of all divider placements would be exponential
We need an efficient linear-time solution

There are several important edge cases:

If the total number of seats is odd, it is impossible to divide the corridor into groups of exactly two seats
If there are zero seats, no valid partition exists
If there are exactly two seats, there is exactly one valid arrangement, no extra divider is needed
Long stretches of plants between seat pairs create multiple valid divider positions

The key observation is that divider placement freedom only exists between consecutive groups of two seats.

Approaches

Brute Force Approach

A brute-force solution would consider every possible divider placement between positions. Since each gap can either contain a divider or not contain one, there are 2^(n-1) possible divider configurations.

For each configuration, we would scan all resulting sections and count seats. If every section contains exactly two seats, we count the arrangement as valid.

This approach is correct because it explicitly checks every possible divider arrangement. However, it is far too slow for n = 10^5.

Optimal Observation

The important insight is that sections are forced by seat grouping.

Suppose the seat positions are:

S S ... S S ... S S

Every valid section must contain exactly two seats. Therefore:

The first two seats must belong to the first section
The next two seats must belong to the second section
And so on

The only flexibility comes from plants located between seat groups.

If there are k positions between the second seat of one section and the first seat of the next section, then we have k possible divider placements.

The final answer becomes the product of all such gap counts.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(n)	Tries every divider configuration
Optimal	O(n)	O(1)	Counts valid divider gaps between seat pairs

Algorithm Walkthrough

Count the total number of seats in the corridor.
If the seat count is zero or odd, immediately return 0, because we cannot form sections containing exactly two seats.
Traverse the corridor from left to right while tracking encountered seats.
Every time we finish a pair of seats, we begin looking for the next seat group.
Count the number of plants between the current completed pair and the next seat.
Suppose there are gap possible divider positions between two consecutive seat groups. Multiply the running answer by gap.
Continue until the entire corridor has been processed.
Return the answer modulo 10^9 + 7.

Why it works

Each valid section must contain exactly two seats, so seat grouping is completely determined. The only choices occur between adjacent seat groups. Every plant gap between groups creates additional divider positions. Since choices between different groups are independent, the total number of valid arrangements is the product of all gap counts.

Python Solution

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7
        
        total_seats = corridor.count('S')
        
        if total_seats == 0 or total_seats % 2 == 1:
            return 0
        
        answer = 1
        seat_count = 0
        plant_count = 0
        
        for char in corridor:
            if char == 'S':
                seat_count += 1
                
                if seat_count > 2 and seat_count % 2 == 1:
                    answer = (answer * (plant_count + 1)) % MOD
                    plant_count = 0
            else:
                if seat_count % 2 == 0 and seat_count != 0:
                    plant_count += 1
        
        return answer

The implementation begins by counting seats. If the count is invalid, meaning zero or odd, the function immediately returns 0.

The variable seat_count tracks how many seats have been encountered so far. Every completed pair creates a potential boundary before the next pair begins.

The variable plant_count records how many plants appear between consecutive seat groups. If there are k plants, there are k + 1 divider positions.

Whenever we encounter the first seat of a new pair, we multiply the answer by (plant_count + 1) and reset the plant counter.

Modulo arithmetic is applied during multiplication to avoid overflow and satisfy the problem requirements.

Go Solution

func numberOfWays(corridor string) int {
    const MOD int = 1e9 + 7

    totalSeats := 0
    for _, ch := range corridor {
        if ch == 'S' {
            totalSeats++
        }
    }

    if totalSeats == 0 || totalSeats%2 == 1 {
        return 0
    }

    answer := 1
    seatCount := 0
    plantCount := 0

    for _, ch := range corridor {
        if ch == 'S' {
            seatCount++

            if seatCount > 2 && seatCount%2 == 1 {
                answer = (answer * (plantCount + 1)) % MOD
                plantCount = 0
            }
        } else {
            if seatCount%2 == 0 && seatCount != 0 {
                plantCount++
            }
        }
    }

    return answer
}

The Go implementation follows the same logic as the Python solution. Since Go does not have Python's arbitrary precision integers, modulo arithmetic is especially important during multiplication.

Strings are iterated using range, which yields runes. Since the input only contains ASCII characters, direct rune comparison is sufficient.

The result slice handling complexities that appear in some Go problems are not relevant here because the function returns a single integer.

Worked Examples

Example 1

corridor = "SSPPSPS"

Seat positions:

0 1 4 6

Processing walkthrough:

Index	Character	seat_count	plant_count	answer
0	S	1	0	1
1	S	2	0	1
2	P	2	1	1
3	P	2	2	1
4	S	3	0	3
5	P	3	0	3
6	S	4	0	3

There are 2 + 1 = 3 divider positions between the two seat groups.

Final answer:

Example 2

corridor = "PPSPSP"

Seat positions:

2 4

There is only one pair of seats, so no additional divider choices exist.

Index	Character	seat_count	plant_count	answer
0	P	0	0	1
1	P	0	0	1
2	S	1	0	1
3	P	1	0	1
4	S	2	0	1
5	P	2	1	1

Final answer:

Example 3

corridor = "S"

Total seats:

Since the seat count is odd, forming sections with exactly two seats is impossible.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the corridor
Space	O(1)	Only a few integer variables are used

The algorithm scans the corridor once to count seats and process gaps. No auxiliary data structures proportional to input size are needed.

Test Cases

sol = Solution()

assert sol.numberOfWays("SSPPSPS") == 3  # Example with multiple divider choices
assert sol.numberOfWays("PPSPSP") == 1  # Exactly one valid partition
assert sol.numberOfWays("S") == 0  # Odd number of seats
assert sol.numberOfWays("PPPP") == 0  # No seats at all
assert sol.numberOfWays("SS") == 1  # Exactly one seat pair
assert sol.numberOfWays("SSPPSS") == 3  # Plants between seat groups
assert sol.numberOfWays("SSPPSPPSPSPPSS") == 9  # Multiple independent gaps
assert sol.numberOfWays("SPPSPSPPSSPP") == 0  # Odd number of seats
assert sol.numberOfWays("SSPPPPSS") == 5  # Large plant gap
assert sol.numberOfWays("SSSS") == 1  # Consecutive seat groups without plants

Test Summary

Test	Why
`"SSPPSPS"`	Standard example with multiple choices
`"PPSPSP"`	Single valid arrangement
`"S"`	Odd seat count
`"PPPP"`	No seats
`"SS"`	Minimum valid corridor
`"SSPPSS"`	Divider choices from plants
`"SSPPSPPSPSPPSS"`	Multiple multiplicative gaps
`"SPPSPSPPSSPP"`	Invalid odd seat count
`"SSPPPPSS"`	Large divider flexibility
`"SSSS"`	No plants between seat groups

Edge Cases

One important edge case occurs when the corridor contains no seats at all. A naive implementation might incorrectly assume the corridor is already valid because no section violates the rule. However, every section must contain exactly two seats, and zero seats does not satisfy this requirement. The implementation explicitly checks for total_seats == 0 and returns 0.

Another important case is an odd number of seats. Since seats must be partitioned into groups of exactly two, an odd count can never be fully divided correctly. The implementation handles this immediately with total_seats % 2 == 1.

A third subtle edge case occurs when consecutive seat groups have no plants between them, such as "SSSS". In this situation, there is exactly one divider position between the seat groups. The implementation correctly computes this because plant_count becomes 0, and multiplication uses (plant_count + 1), producing exactly one valid choice.

LeetCode 2150 - Find All Lonely Numbers in the Array

Problem Understanding

We are given an integer array nums. A number is considered lonely if two conditions are simultaneously true:

The number appears exactly once in the array.
Neither its immediate neighbors, meaning x - 1 nor x + 1, appear anywhere in the array.

The task is to return all numbers satisfying both conditions. The output order does not matter.

The constraints allow up to 10^5 elements, so the solution must be efficient. A quadratic solution that repeatedly scans the array for neighbors would be too slow.

Several edge cases are important:

Duplicate values can never be lonely
Consecutive values invalidate each other
A single-element array always produces a lonely number
Values may be as large as 10^6, so direct indexing arrays are possible but hash maps are cleaner and more flexible

The central challenge is efficiently checking both frequency and neighbor existence.

Approaches

Brute Force Approach

A brute-force solution would examine every number individually.

For each element:

Count how many times it appears in the array
Scan the array again to check whether x - 1 or x + 1 exists

This guarantees correctness because every loneliness condition is explicitly verified.

However, each element may require a full array scan, leading to O(n^2) time complexity.

Optimal Observation

The key insight is that we only need fast access to:

The frequency of each number
Whether neighboring numbers exist

A hash map naturally supports both operations in constant average time.

We first build a frequency map. Then, for each distinct number:

Its frequency must equal 1
x - 1 must not exist
x + 1 must not exist

This transforms repeated scans into constant-time lookups.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Repeatedly scans array
Optimal	O(n)	O(n)	Uses frequency hash map

Algorithm Walkthrough

Create a hash map called frequency.
Traverse the array once and count occurrences of every number.
Initialize an empty result list.
Iterate through the numbers in the array again.
For each number x, check three conditions:
frequency[x] == 1
x - 1 is not in the map
x + 1 is not in the map
If all conditions are true, append x to the result.
Return the result list.

Why it works

The frequency map stores complete information about element occurrences and neighbor existence. A number is lonely precisely when its count is one and adjacent values are absent. Since the algorithm checks exactly these conditions for every number, all lonely numbers are included and all non-lonely numbers are excluded.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        frequency = Counter(nums)
        
        lonely_numbers = []
        
        for num in nums:
            if (
                frequency[num] == 1
                and (num - 1) not in frequency
                and (num + 1) not in frequency
            ):
                lonely_numbers.append(num)
        
        return lonely_numbers

The implementation begins by constructing a frequency table using Counter. This gives constant-time access to occurrence counts.

The second loop evaluates each number against the loneliness conditions. Because dictionary membership checks are average O(1), the overall algorithm remains linear.

The result list stores all valid lonely numbers and is returned at the end.

Go Solution

func findLonely(nums []int) []int {
    frequency := make(map[int]int)

    for _, num := range nums {
        frequency[num]++
    }

    result := []int{}

    for _, num := range nums {
        if frequency[num] == 1 {
            _, hasPrev := frequency[num-1]
            _, hasNext := frequency[num+1]

            if !hasPrev && !hasNext {
                result = append(result, num)
            }
        }
    }

    return result
}

The Go solution uses a map from integers to counts. Membership checking is performed using the comma-ok idiom.

Slices are dynamically expanded using append. Unlike Python's dictionaries, Go requires explicit existence checks when determining whether neighbor values are present.

Worked Examples

Example 1

nums = [10,6,5,8]

Frequency map:

Number	Count
10	1
6	1
5	1
8	1

Evaluation:

Number	Count == 1	Neighbor Exists	Lonely
10	Yes	No	Yes
6	Yes	5 exists	No
5	Yes	6 exists	No
8	Yes	No	Yes

Result:

[10, 8]

Example 2

nums = [1,3,5,3]

Frequency map:

Number	Count
1	1
3	2
5	1

Evaluation:

Number	Count == 1	Neighbor Exists	Lonely
1	Yes	No	Yes
3	No	N/A	No
5	Yes	No	Yes

Result:

[1, 5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear passes through the array
Space	O(n)	Frequency hash map stores counts

The hash map may contain up to n distinct values. Each lookup and insertion is constant average time, making the overall runtime linear.

Test Cases

sol = Solution()

assert sorted(sol.findLonely([10,6,5,8])) == [8,10]  # Example case
assert sorted(sol.findLonely([1,3,5,3])) == [1,5]  # Duplicate removes loneliness
assert sol.findLonely([7]) == [7]  # Single element
assert sol.findLonely([1,2,3]) == []  # Consecutive numbers invalidate all
assert sol.findLonely([1,1,1]) == []  # Duplicates only
assert sorted(sol.findLonely([0,2,4,6])) == [0,2,4,6]  # All isolated
assert sol.findLonely([5,6,8,8,10]) == [10]  # Duplicate and adjacency interactions
assert sorted(sol.findLonely([1000000,0])) == [0,1000000]  # Large values
assert sol.findLonely([2,3,4,5,6]) == []  # Entire consecutive range
assert sorted(sol.findLonely([1,4,7,10])) == [1,4,7,10]  # No neighbors

Test Summary

Test	Why
`[10,6,5,8]`	Standard example
`[1,3,5,3]`	Duplicate invalidation
`[7]`	Single-element array
`[1,2,3]`	Consecutive chain
`[1,1,1]`	All duplicates
`[0,2,4,6]`	Every number lonely
`[5,6,8,8,10]`	Mixed conditions
`[1000000,0]`	Boundary values
`[2,3,4,5,6]`	Dense consecutive values
`[1,4,7,10]`	Fully isolated numbers

Edge Cases

One important edge case occurs when all elements are duplicates, such as [1,1,1]. A buggy implementation might incorrectly include one occurrence if it only checks neighbors. The solution correctly rejects all duplicates by requiring frequency exactly equal to one.

Another subtle case occurs with consecutive values like [4,5]. Both numbers appear once, but neither is lonely because each has an adjacent neighbor. The implementation explicitly checks both x - 1 and x + 1.

A third important case is a single-element array. Since the number appears once and no adjacent values exist, it must be lonely. The frequency map correctly handles missing neighbors, so the implementation naturally returns the single value.