Seating Arrangement

Time: O(n)

Space: O(1)

Intuition

A new person can sit only on an empty seat whose immediate neighbors are also empty or outside the row. The greedy left-to-right strategy works because placing a person at the earliest valid seat cannot reduce a better future option: once a position is valid, choosing it only blocks its immediate next neighbor, which would also be blocked by any nearby valid placement. So we can scan the row once, seat people whenever possible, and stop as soon as k people are seated.

Algorithm

1First scan the seats and return false if the input already has two adjacent occupied seats, because that arrangement violates the rule before adding anyone.
2Traverse seats from left to right while k is not zero.
3For each empty seat, check its left neighbor if it exists and its right neighbor if it exists.
4If both checked neighbors are not occupied, mark the current seat occupied, decrement k, and skip the next index because it can no longer be used.
5Return true when k reaches 0; otherwise return false after the scan.
6Time Complexity: O(n), where n is seats.length, because the row is scanned a constant number of times.
7Space Complexity: O(1), because the seating is updated in place.

Example Walkthrough

Input: k = 2, seats = [0, 0, 0, 0, 0]

1.There are no adjacent occupied seats initially.
2.Seat 0 is valid because it has no left neighbor and seat 1 is empty, so place one person there. Remaining k = 1.
3.Skip seat 1 because it is adjacent to the newly occupied seat 0.
4.Seat 2 is valid because seats 1 and 3 are both empty, so place the second person. Remaining k = 0.
5.Since everyone has been seated, the scan can stop successfully.

Output: true

Common Pitfalls

•Boundary seats have only one neighbor, so avoid reading outside the array.
•After placing someone, skip the next seat because adjacent seating is forbidden.
•If the original arrangement already contains adjacent occupied seats, no additions can make it valid.

Seating Arrangement.java

Java

// Approach: First reject any already-invalid arrangement with adjacent occupied seats.
// Then greedily scan left to right and place a person at every empty seat whose existing
// neighbors are empty or outside the row, skipping the next seat after each placement.
// Time: O(n) Space: O(1)

class Solution {

    public boolean canSeatAllPeople(int k, int[] seats) {
        int n = seats.length;
        for (int i = 0; i < n - 1; ++i) {
            if (seats[i] == 1 && seats[i + 1] == 1) {
                return false;
            }
        }

        for (int i = 0; i < n && k != 0; ++i) {
            boolean leftEmpty = (i == 0) || seats[i - 1] == 0;
            boolean rightEmpty = (i == n - 1) || seats[i + 1] == 0;
            if (seats[i] == 0 && leftEmpty && rightEmpty) {
                seats[i] = 1;
                k--;
                i++;
            }

        }
        return k == 0;
    }
}

Was this solution helpful?