Code Implementation

class Solution:
    def consecutiveSeats(self, seats):
        """
        :type seats: List[List[int]]
        :rtype: List[List[int]]
        """
        # Sort seats by row_id and seat_id
        seats.sort()
        res = []
        prev_row, prev_seat = None, None
        for row_id, seat_id in seats:
            if prev_row == row_id and seat_id == prev_seat + 1:
                res.append([row_id, prev_seat, seat_id])
            prev_row, prev_seat = row_id, seat_id
        return res
      

class Solution {
public:
    vector<vector<int>> consecutiveSeats(vector<vector<int>>& seats) {
        sort(seats.begin(), seats.end());
        vector<vector<int>> res;
        int prev_row = -1, prev_seat = -1;
        for (auto& seat : seats) {
            int row_id = seat[0], seat_id = seat[1];
            if (row_id == prev_row && seat_id == prev_seat + 1) {
                res.push_back({row_id, prev_seat, seat_id});
            }
            prev_row = row_id;
            prev_seat = seat_id;
        }
        return res;
    }
};
      

class Solution {
    public List<List<Integer>> consecutiveSeats(int[][] seats) {
        Arrays.sort(seats, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        List<List<Integer>> res = new ArrayList<>();
        int prevRow = -1, prevSeat = -1;
        for (int[] seat : seats) {
            int rowId = seat[0], seatId = seat[1];
            if (rowId == prevRow && seatId == prevSeat + 1) {
                res.add(Arrays.asList(rowId, prevSeat, seatId));
            }
            prevRow = rowId;
            prevSeat = seatId;
        }
        return res;
    }
}
      

var consecutiveSeats = function(seats) {
    seats.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    let res = [];
    let prevRow = null, prevSeat = null;
    for (let [rowId, seatId] of seats) {
        if (prevRow === rowId && seatId === prevSeat + 1) {
            res.push([rowId, prevSeat, seatId]);
        }
        prevRow = rowId;
        prevSeat = seatId;
    }
    return res;
};
      

Problem Description

The "Consecutive Available Seats" problem asks you to find all pairs of consecutive available seats in a cinema. You are given a list of available seats, where each seat is represented as a pair [row_id, seat_id]. Your task is to return a list of all pairs of seats that are consecutive in the same row (i.e., same row_id and seat_id values differ by 1).

• Each seat is represented as [row_id, seat_id].
• Seats are considered consecutive if they are in the same row and their seat_id values differ by exactly 1.
• Return each pair as [row_id, seat_id1, seat_id2] where seat_id1 and seat_id2 are consecutive.
• Do not reuse seat pairs; each valid consecutive pair should appear only once.
• There may be multiple rows and the input is not guaranteed to be sorted.

Thought Process

To solve this problem, we first need to identify all pairs of seats that are consecutive in the same row. A brute-force approach would be to compare every seat with every other seat to check if they are in the same row and consecutive. However, this would be inefficient for large inputs.

Instead, we can optimize by sorting the seats first. Once sorted by row_id and then by seat_id, consecutive pairs within the same row will be adjacent in the list. This allows us to simply compare each seat with its previous seat and check if they are consecutive.

This shift from brute-force to sorting and linear scan dramatically reduces the number of comparisons we need to make, making the solution efficient and straightforward.

Solution Approach

• Step 1: Sort the input list of seats first by row_id, then by seat_id. This groups seats by row and arranges them in order.
• Step 2: Iterate through the sorted list, keeping track of the previous seat's row_id and seat_id.
• Step 3: For each seat, check if it is consecutive with the previous seat (same row_id and seat_id is previous seat + 1).
• Step 4: If they are consecutive, add the pair [row_id, prev_seat_id, seat_id] to the result list.
• Step 5: Continue scanning until all seats have been processed.
• Step 6: Return the result list containing all consecutive seat pairs.

Sorting is used because it brings all potentially consecutive seats together, enabling a single linear scan to find all pairs. This avoids the need for nested loops and reduces complexity.

Example Walkthrough

Input: [[1,2], [1,3], [1,5], [2,1], [2,2], [2,4]]

Step 1: Sort the seats:
After sorting, the list becomes: [[1,2], [1,3], [1,5], [2,1], [2,2], [2,4]] (already sorted in this example).

Step 2: Scan for consecutive seats:

• Compare [1,2] and [1,3]: Same row, seat IDs differ by 1 → [1,2,3] is a valid pair.
• Compare [1,3] and [1,5]: Seat IDs differ by 2 → not consecutive.
• Compare [1,5] and [2,1]: Different rows → not consecutive.
• Compare [2,1] and [2,2]: Same row, seat IDs differ by 1 → [2,1,2] is a valid pair.
• Compare [2,2] and [2,4]: Seat IDs differ by 2 → not consecutive.

Final Output: [[1,2,3], [2,1,2]]

Time and Space Complexity

• Brute-force approach: For each seat, compare with every other seat to check if they are consecutive. This leads to O(n^2) time complexity, where n is the number of seats.
• Optimized approach (sorting and linear scan):
  • Sorting takes O(n log n) time.
  • Scanning the sorted list is O(n).
  • Overall time complexity is O(n log n).
  • Space complexity is O(1) extra (ignoring output), as sorting can be done in place and only a few variables are used.

Summary

The "Consecutive Available Seats" problem is best solved by first sorting the seats by row and seat number, then scanning for adjacent pairs that are consecutive in the same row. This approach is efficient, simple, and avoids unnecessary comparisons. The key insight is that sorting brings all potential pairs together, making it easy to find consecutive seats in a single pass.