LeetCode 626: Exchange Seats

Problem Restatement

We are given a table named Seat.

Each row stores a student and their seat id.

The id values start from 1 and increase continuously.

We need to swap every two adjacent students:

If the number of students is odd, the last student stays in the same seat.

The result must be ordered by id in ascending order.

Table

Seat

id is the primary key.

The id sequence is continuous, starting from 1.

Example

Input:

Output:

Seats 1 and 2 are exchanged.

Seats 3 and 4 are exchanged.

Seat 5 has no partner, so it stays unchanged.

First Thought: Move the Student, Not the Row

The table already has the final seat IDs we need to output: 1, 2, 3, ....

So we can keep each output row’s id, and decide which student’s name should appear there.

For each output seat:

For example, seat 1 should receive the student from seat 2.

Seat 2 should receive the student from seat 1.

Seat 5 would normally receive from seat 6, but seat 6 does not exist, so seat 5 keeps its own student.

Key Insight

The only special case is the final row when the number of rows is odd.

For every other row:

We can compute this with a CASE expression.

To know whether the current row is the final odd row, we can compare it with the maximum id in the table.

Because the IDs are continuous from 1, MAX(id) is also the number of rows.

Algorithm

For each row in Seat:

1. If id is odd and also equals the maximum id, keep it unchanged.
2. Else if id is odd, change it to id + 1.
3. Else if id is even, change it to id - 1.
4. Sort the final result by id.

Instead of physically updating the table, we only produce the swapped result.

SQL Solution

SELECT
    CASE
        WHEN id % 2 = 1 AND id = (SELECT MAX(id) FROM Seat) THEN id
        WHEN id % 2 = 1 THEN id + 1
        ELSE id - 1
    END AS id,
    student
FROM Seat
ORDER BY id;

Explanation

The CASE expression computes the new seat ID for each student.

For an odd id, the student should move to the next seat:

WHEN id % 2 = 1 THEN id + 1

For an even id, the student should move to the previous seat:

ELSE id - 1

The final odd row needs special handling:

WHEN id % 2 = 1 AND id = (SELECT MAX(id) FROM Seat) THEN id

For example, when id = 5 and there are only five rows, there is no seat 6. So the student remains at id = 5.

Finally:

ORDER BY id

returns the rows in the required order.

Correctness

Each pair of adjacent seats has the form:

(1, 2), (3, 4), (5, 6), ...

For every odd id that has a partner, the query changes its output id to id + 1.

For every even id, the query changes its output id to id - 1.

Therefore, each complete adjacent pair is swapped exactly once.

If the number of students is odd, the final id is odd and equals MAX(id). The first WHEN branch keeps that row unchanged. Therefore, the last unpaired student remains in the same seat.

The query returns exactly the required swapped seating arrangement.

Complexity

The MAX(id) subquery is logically a table aggregate. Most SQL engines can compute it efficiently, especially when id is indexed as a primary key.

Alternative Solution: Use ROW_NUMBER

Another common solution is to sort rows by the seat they should exchange with, then reassign sequential IDs.

SELECT
    ROW_NUMBER() OVER (
        ORDER BY
            CASE
                WHEN id % 2 = 1 THEN id + 1
                ELSE id - 1
            END
    ) AS id,
    student
FROM Seat;

This works because the ordering key places each adjacent pair in swapped order.

For input:

The ordering key becomes:

After sorting by this key, the students appear as:

Doris, Abbot, Green, Emerson, Jeames

Then ROW_NUMBER() assigns IDs 1 through 5.

Testing

Use this setup:

CREATE TABLE Seat (
    id INT PRIMARY KEY,
    student VARCHAR(255)
);

INSERT INTO Seat (id, student) VALUES
(1, 'Abbot'),
(2, 'Doris'),
(3, 'Emerson'),
(4, 'Green'),
(5, 'Jeames');

Expected result:

Even number of students:

TRUNCATE TABLE Seat;

INSERT INTO Seat (id, student) VALUES
(1, 'A'),
(2, 'B'),
(3, 'C'),
(4, 'D');

Expected result:

Single student:

TRUNCATE TABLE Seat;

INSERT INTO Seat (id, student) VALUES
(1, 'A');

Expected result: