Problem Statement:

You are given the seat layout of a cinema hall consisting of several rows, each row is denoted by an uppercase letter ‘A’, ‘B’, ‘C’, ‘D’, … Each row can have seats from 1 to 10.

Your task is to find the count of maximum consecutive available seats in the cinema hall. A seat is said to be available if it is not occupied by any one. A max-consecutive-seats is defined by having no reserved seats in between the found the empty seats.

Example 1: Input:

[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '.', '.'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]

Output: 2

Explanation: The '.' in the last two positions on row H is available for a booking. Any of the two empty seats can be booked for a group of 2 consecutive seat seekers.

Example 2: Input:

[['#', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
 ['#', '#', '#', '#', '#', '#', '#', '#', '.', '.'],
 ['#', '.', '.', '#', '#', '.', '#', '#', '.', '#'],
 ['#', '#', '#', '.', '#', '#', '.', '.', '#', '#'],
 ['#', '.', '.', '#', '#', '.', '#', '#', '#', '#'],
 ['.', '#', '.', '#', '#', '#', '.', '.', '#', '#'],
 ['#', '.', '.', '.', '#', '.', '#', '#', '#', '#'],
 ['#', '#', '.', '.', '.', '.', '#', '.', '.', '#'],
 ['#', '#', '#', '#', '#', '.', '.', '#', '#', '#'],
 ['.', '#', '#', '#', '.', '#', '#', '.', '#', '.']]

Output: 3

Explanation: In row A, three consecutive seats are available from indices 2 to 4 (which are denoted as '.' in the input array).

Solution Approach:

Iterate through all rows and for each row count the number of consecutive available seats(groups) you find without any reserved seats in between.

Keep track of the max consecutive available seats found so far.

Print out the maximum number of consecutive available seats found after iterating through all rows.

To count the consecutive seats we can iterate the row and keep on checking 2 continuous available seats. When we find a available seat, we check if next seat is available and if it is, we increment count, and we continue iteration.

If we encounter a reserved seat, then we reset count to zero and move to next seat. When we find a consecutive k number of available seats, we update the max_consecutive_available_seats variable with value k if it is >= previous value.

Let's implement this in code in Python -

def max_consecutive_available_seats(seat_layout): max_consecutive_available_seats_so_far = 0 for row in seat_layout: consecutive_available_seats = 0 for seat in row: if seat == '.': consecutive_available_seats += 1 if consecutive_available_seats >= 2: max_consecutive_available_seats_so_far = max( max_consecutive_available_seats_so_far, consecutive_available_seats) else: consecutive_available_seats = 0 return max_consecutive_available_seats_so_far

#Testing cinema_seats = [['#', '#', '#', '#', '#', '#', '#', '#', '.', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '.', '.'], ['#', '.', '.', '#', '#', '.', '#', '#', '.', '#'], ['#', '#', '#', '.', '#', '#', '.', '.', '#', '#'], ['#', '.', '.', '#', '#', '.', '#', '#', '#', '#'], ['.', '#', '.', '#', '#', '#', '.', '.', '#', '#'], ['#', '.', '.', '.', '#', '.', '#', '#', '#', '#'], ['#', '#', '.', '.', '.', '.', '#', '.', '.', '#'], ['#', '#', '#', '#', '#', '.', '.', '#', '#', '#'], ['.', '#', '#', '#', '.', '#', '#', '.', '#', '.']] print(max_consecutive_available_seats(cinema_seats)) # Expected Output: 3

cinema_seats = [['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '.', '.'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']] print(max_consecutive_available_seats(cinema_seats)) # Expected Output: 2

Time Complexity: O(MN), where M is the number of rows and N is the number of seats in each row.

Space Complexity: O(1), as we are not using any extra space.

1