Exchange Seats Problem

Problem

Table: Seat

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

id is the primary key (unique value) column for this table. Each row of this table indicates the name and the ID of a student. id is a continuous increment.

Write a solution to swap the seat id of every two consecutive students. If the number of students is odd, the id of the last student is not swapped.

Return the result table ordered by id in ascending order.

The result format is in the following example.

Examples

Example 1:

Input: Seat table:

+----+---------+
| 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  |
+----+---------+

Explanation: Note that if the number of students is odd, there is no need to change the last one’s seat.

Solution

Method 1 - Select with case

Code

Sql

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

Complexity

⏰ Time complexity: O(n)
- The main complexity arises from the subquery (SELECT MAX(id) FROM Seat) which is O(1) as it aggregates a single value.
- Thus, the overall complexity for the query is O(n), where n is the number of rows in the Seat table given that it scans all rows once.
🧺 Space complexity: O(1)
- The space complexity is O(1) for the additional storage needed during query execution since we’re not using any extra space that’s dependent on input size aside from the result set.

Problem#

Examples#

Solution#

Method 1 - Select with case#

Code#

Sql#

Complexity#