# 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:

| Original Seat | New Seat |
|---|---|
| `1` | gets student from `2` |
| `2` | gets student from `1` |
| `3` | gets student from `4` |
| `4` | gets student from `3` |

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

```sql
Seat
```

| Column | Type |
|---|---|
| id | int |
| student | varchar |

`id` is the primary key.

The `id` sequence is continuous, starting from `1`.

## Example

Input:

| id | student |
|---|---|
| 1 | Abbot |
| 2 | Doris |
| 3 | Emerson |
| 4 | Green |
| 5 | Jeames |

Output:

| id | student |
|---|---|
| 1 | Doris |
| 2 | Abbot |
| 3 | Green |
| 4 | Emerson |
| 5 | Jeames |

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:

| id | Student should come from |
|---|---|
| odd id | next seat |
| even id | previous seat |
| last odd id | itself |

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:

| Current `id` | Source `id` |
|---|---|
| odd | `id + 1` |
| even | `id - 1` |

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

```sql
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:

```sql
WHEN id % 2 = 1 THEN id + 1
```

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

```sql
ELSE id - 1
```

The final odd row needs special handling:

```sql
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:

```sql
ORDER BY id
```

returns the rows in the required order.

## Correctness

Each pair of adjacent seats has the form:

```text
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | The table is scanned, then sorted by `id` |
| Space | `O(n)` | The database may materialize the ordered result |

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.

```sql
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:

| id | student |
|---|---|
| 1 | Abbot |
| 2 | Doris |
| 3 | Emerson |
| 4 | Green |
| 5 | Jeames |

The ordering key becomes:

| id | student | ordering key |
|---|---|---|
| 1 | Abbot | 2 |
| 2 | Doris | 1 |
| 3 | Emerson | 4 |
| 4 | Green | 3 |
| 5 | Jeames | 6 |

After sorting by this key, the students appear as:

```text
Doris, Abbot, Green, Emerson, Jeames
```

Then `ROW_NUMBER()` assigns IDs `1` through `5`.

## Testing

Use this setup:

```sql
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:

| id | student |
|---|---|
| 1 | Doris |
| 2 | Abbot |
| 3 | Green |
| 4 | Emerson |
| 5 | Jeames |

Even number of students:

```sql
TRUNCATE TABLE Seat;

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

Expected result:

| id | student |
|---|---|
| 1 | B |
| 2 | A |
| 3 | D |
| 4 | C |

Single student:

```sql
TRUNCATE TABLE Seat;

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

Expected result:

| id | student |
|---|---|
| 1 | A |