Problem Statement
You are given:
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:
0
Left:
Boundary
Right:
0
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:
1
Cannot place a person.
Skip.
Step 4: Check Index 4
Current seat:
0
Left:
0
Right:
0
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:
If both neighbors are empty (or out of bounds):
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.
Similar problems include:
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.
Join the conversation! Your thoughts help the community grow.