Exchange Seats - Solution & Explanation
Problem Statement
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. The ID sequence always starts from 1 and increments continuously.
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.
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.
Approach Overview
Problem Overview: The table stores students with sequential seat IDs. The task is to swap every pair of adjacent seats: seat 1 with seat 2, seat 3 with seat 4, and so on. If the number of rows is odd, the final seat remains unchanged.
Approach 1: Direct Swap with Traversal (Time: O(n), Space: O(1))
This approach iterates through the rows in seat order and swaps adjacent pairs as it goes. When the current seat index is odd, exchange it with the next seat. When the index is even, it has already been handled by the previous step. In SQL-style logic, this is often implemented with a CASE expression that increments or decrements the seat ID depending on whether the row index is odd or even, while checking if a next row exists. The algorithm performs a single pass over the dataset, making it efficient and easy to reason about. This technique is essentially a simulation of pairwise swapping and works well when rows are already ordered by ID.
Approach 2: Use of Temporary Data Structures (Time: O(n), Space: O(n))
This method first copies the seat data into a temporary structure such as an array or intermediate table. Iterate through the collection in steps of two and swap elements at positions i and i + 1. If the total number of elements is odd, the final element remains untouched. After processing, rebuild the result set using the updated order. The approach is straightforward and useful when you want clearer manipulation logic or when transformations are easier to express outside a direct query. The tradeoff is extra memory usage because all rows must be stored before swapping.
In database environments, the same idea is commonly expressed with SQL constructs like CASE, COUNT(), or window functions to determine whether a seat should move forward or backward. The key insight is that swapping happens strictly in adjacent pairs, so each row only needs to look at its immediate neighbor.
Recommended for interviews: The direct traversal or SQL CASE approach is what interviewers typically expect. It demonstrates that you recognize the pairwise pattern and can implement the swap in a single pass with constant extra space. Showing the temporary structure approach first can help explain the idea clearly, but the in-place or query-based swap highlights stronger optimization instincts.
Approach 1: Approach 1: Direct Swap with Traversal
This approach involves iterating through the list and swapping every two consecutive students. The loop runs with a step of 2 to handle even-indexed pairs, ensuring that swaps are done pair-wise. If the total number of students is odd, the last student remains in their original position as there is no pair to swap with.
The C code uses an array of strings to represent students. It swaps the seats by iterating through the array with a step of 2. For each iteration, it swaps the student names using a temporary variable. The last student remains unaltered if the number of students is odd since the iteration breaks before reaching them.
Complexity
Time Complexity: O(n), since each element may be swapped once.
Space Complexity: O(1), as no extra space is used except the temporary variable for swapping.
Approach 2: Approach 2: Use of Temporary Data Structures
This method employs a temporary array or list to store swapped results before copying them back to the original list or directly returning them as new results. This makes the logic conceptually simpler at the cost of some additional space usage.
The C variant uses an extra 2D array to initially store swapped pairs, maintaining the original array intact. It later prints the new results by referencing the temporary storage after all swaps are completed.
Complexity
Time Complexity: O(n) due to linear traversal.
Space Complexity: O(n), using a full-sized temporary array.
Approach 3: Default Approach
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Swap with Traversal | Time Complexity: O(n), since each element may be swapped once. |
| Approach 2: Use of Temporary Data Structures | Time Complexity: O(n) due to linear traversal. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Swap with Traversal | O(n) | O(1) | Best choice when rows are already ordered by seat ID and swaps can be computed directly with conditional logic |
| Temporary Data Structure | O(n) | O(n) | Useful when implementing the logic in general-purpose languages or when transformations are easier with arrays |
Video Solution
Exchange Seats | Leetcode 626 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 12,244 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Exchange Seats easy or hard?
Exchange Seats Python/Java solution
How to solve Exchange Seats in O(n)?
What is the best approach for Exchange Seats?
Is Exchange Seats asked at Google/Amazon/Meta?
What data structure is used in Exchange Seats?
What is the time complexity of Exchange Seats?
Ready to solve this problem?
Practice Exchange Seats with our built-in code editor and test cases.
Practice on FleetCode