Seating Arrangement Problem

Problem Statement

You are given:

An integer k representing the number of new people to be seated.
An array seats[] where:
- 0 represents an empty seat.
- 1 represents an occupied seat.

The goal is to determine whether all k people can be seated such that no two occupied seats are adjacent.

Example

Input

k = 2
seats = [0, 0, 1, 0, 0, 0, 1]

Output

true

Explanation

We can place people at index 0 and index 4.

Final arrangement:

[1, 0, 1, 0, 1, 0, 1]

No two occupied seats are adjacent.

Understanding the Key Observation

A person can sit at position i only if:

The current seat is empty (seats[i] == 0).
The left seat is empty or does not exist.
The right seat is empty or does not exist.

Mathematically:

seats[i] == 0
&& (i == 0 || seats[i - 1] == 0)
&& (i == n - 1 || seats[i + 1] == 0)

Why Greedy Works

Whenever we find a valid seat, we immediately place a person there.

Why Is This Correct?

Placing a person in the earliest available valid seat can never reduce the maximum number of people that can be seated later.

Since every placement is locally optimal and does not harm future choices, the problem is a perfect candidate for a Greedy Algorithm.

Dry Run

Consider:

k = 2
seats = [0, 0, 1, 0, 0, 0, 1]

Step 1: Check Index 0

Current seat:

Left:

Boundary

Right:

This is a valid position.

Place a person:

[1, 0, 1, 0, 0, 0, 1]

Remaining people:

k = 1

Step 2: Check Index 1

This seat is adjacent to an occupied seat.

Skip.

Step 3: Check Index 3

Left neighbor:

Cannot place a person.

Skip.

Step 4: Check Index 4

Current seat:

Left:

Right:

This is a valid position.

Place a person:

[1, 0, 1, 0, 1, 0, 1]

Remaining people:

k = 0

All people are seated successfully.

Return:

true

Algorithm

Traverse the array from left to right.
For every empty seat:
- Check the left neighbor.
- Check the right neighbor.
If both neighbors are empty (or out of bounds):
- Seat a person.
- Mark the seat as occupied.
- Decrease k.
If k becomes 0, return true.
After traversal, return whether k == 0.

C++ Solution

class Solution {
public:
    bool canSeatAllPeople(int k, vector<int> &seats) {
        int n = seats.size();

        for (int i = 0; i < n && k > 0; i++) {

            if (seats[i] == 0) {

                bool leftEmpty =
                    (i == 0 || seats[i - 1] == 0);

                bool rightEmpty =
                    (i == n - 1 || seats[i + 1] == 0);

                if (leftEmpty && rightEmpty) {
                    seats[i] = 1;
                    k--;
                }
            }
        }

        return k == 0;
    }
};

Why This Approach Is Efficient

The algorithm scans the array only once.

Whenever a valid seat is found:

A person is placed immediately.
The seat is marked as occupied.
Future checks automatically respect the adjacency rule.

There is no need for backtracking, recursion, or additional data structures.

Correctness Intuition

The greedy strategy always chooses the earliest valid seat.

Since seating someone at a valid position cannot invalidate a better future arrangement, every placement is safe.

By the end of the traversal:

If k reaches 0, all people have been seated successfully.
Otherwise, there are not enough valid seats available.

Complexity Analysis

Time Complexity

Each seat is visited exactly once.

O(n)

where n is the size of the array.

Space Complexity

No extra data structures are used.

O(1)

Pattern Recognition

This problem is a classic example of a:

Greedy Algorithm

Common indicators include:

Make the best local choice.
Place items as early as possible.
No need to revisit previous decisions.
Future choices are not harmed by current optimal choices.

Key Takeaway

The key insight is that a person can be seated only when the current seat and its adjacent seats are empty. Since placing a person in the earliest valid position never reduces future seating opportunities, a greedy left-to-right scan guarantees the maximum possible placements in linear time.

Summary

To determine whether all k people can be seated without creating adjacent occupied seats, traverse the seat array and greedily place people whenever the current seat and its neighbors are empty. Each seat is processed once, resulting in an efficient O(n) time and O(1) space solution. The problem is a classic application of the Greedy Algorithm pattern.