Best Seat [Medium]
- Method 1

Best Seat [Medium]

You walk into a theatre you’re about to see a show in. The usher within the theatre walks you to your row and mentions you’re allowed to sit anywhere within the given row. Naturally you’d like to sit in the seat that gives you the most space. You also would prefer this space to be evenly distributed on either side of you (e.g. if there are three empty seats in a row, you would prefer to sit in the middle of those three seats).
Given the theatre row represented as an integer array, return the seat index of where you should sit. Ones represent occupied seats and zeroes represent empty seats.
You may assume that someone is always sitting in the first and last seat of the row. Whenever there are two equally good seats, you should sit in the seat with the lower index. If there is no seat to sit in, return -1. The given array will always have a length of at least one and contain only ones and zeroes.

Sample Input

seats=[1,0,1,0,0,0,1]

Sample Output

Hints

Hint 1

Try thinking about this problem in real life. How would you determine what seat has the most space?

Hint 2

The best seat will always be within the longest contiguous subarray of all zeros.

Hint 3

Once you find the longest contiguous subarray of empty seats, how can you choose where to sit within that subarray?

Hint 4

How can you find the midpoint between two people?

Method 1

【O(n)time∣O(1)space】

package Array;

/**
 * @author zhengstars
 * @date 2023/04/23
 */
public class BestSeat {
    public int bestSeat(int[] seats) {
        // the length of the longest vacant area
        int maxEmpty = 0;  
        // Index of the best location
        int index = -1;
        // The left index of the longest vacant area
        int left = -1;
        // The right index of the longest vacant area
        int right = -1;    
        int n = seats.length;

        // Find the longest vacant area
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                continue;
            }

            int j = i;
            while (j < n && seats[j] == 0) {
                j++;
            }

            int currEmpty = j - i;
            if (currEmpty > maxEmpty) {
                maxEmpty = currEmpty;
                left = i;
                right = j - 1;
            }

            i = j;
        }

        // Calculate the best location
        if (left == -1 || right == -1) {
            // There are no seats available.
            return -1;
        } else if (left == 0) {
            // The best position is in the first vacant position.
            index = 0;
        } else if (right == n - 1) {
            // The best position is in the last vacant seat.
            index = n - 1;
        } else {
            // The best position is in the middle of the longest vacancy area.
            index = (left + right) / 2;
        }

        return index;
    }
}

Best Seat [Medium]

Method 1

Enjoy Reading This Article?