Problem

Table: Genders

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| gender      | varchar |
+-------------+---------+
user_id is the primary key (column with unique values) for this table.
gender is ENUM (category) of type 'female', 'male', or 'other'.
Each row in this table contains the ID of a user and their gender.
The table has an equal number of 'female', 'male', and 'other'.

Write a solution to rearrange the Genders table such that the rows alternate between 'female', 'other', and 'male' in order. The table should be rearranged such that the IDs of each gender are sorted in ascending order.

Return the result table in the mentioned order.

The result format is shown in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Input: 
Genders table:
+---------+--------+
| user_id | gender |
+---------+--------+
| 4       | male   |
| 7       | female |
| 2       | other  |
| 5       | male   |
| 3       | female |
| 8       | male   |
| 6       | other  |
| 1       | other  |
| 9       | female |
+---------+--------+
Output: 
+---------+--------+
| user_id | gender |
+---------+--------+
| 3       | female |
| 1       | other  |
| 4       | male   |
| 7       | female |
| 2       | other  |
| 5       | male   |
| 9       | female |
| 6       | other  |
| 8       | male   |
+---------+--------+
Explanation: 
Female gender: IDs 3, 7, and 9.
Other gender: IDs 1, 2, and 6.
Male gender: IDs 4, 5, and 8.
We arrange the table alternating between 'female', 'other', and 'male'.
Note that the IDs of each gender are sorted in ascending order.

Solution

Method 1 – Window Functions and Row Number (MySQL)

Intuition

We need to alternate rows by gender in the order ‘female’, ‘other’, ‘male’, with IDs of each gender sorted. Assign a row number to each gender group, then join them by row number and output in the required order.

Approach

  1. Assign a row number to each gender group, ordered by user_id ascending.
  2. Join the three gender groups on their row number.
  3. Output the rows in the order: female, other, male, for each row number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

WITH
  female AS (
    SELECT user_id, gender, ROW_NUMBER() OVER (ORDER BY user_id) AS rn
    FROM Genders WHERE gender = 'female'
  ),
  other AS (
    SELECT user_id, gender, ROW_NUMBER() OVER (ORDER BY user_id) AS rn
    FROM Genders WHERE gender = 'other'
  ),
  male AS (
    SELECT user_id, gender, ROW_NUMBER() OVER (ORDER BY user_id) AS rn
    FROM Genders WHERE gender = 'male'
  )
SELECT user_id, gender FROM (
  SELECT f.rn, f.user_id, f.gender FROM female f
  UNION ALL
  SELECT o.rn, o.user_id, o.gender FROM other o
  UNION ALL
  SELECT m.rn, m.user_id, m.gender FROM male m
) t
ORDER BY rn, FIELD(gender, 'female', 'other', 'male');

Complexity

  • ⏰ Time complexity: O(n log n) (sorting by user_id for each gender)
  • 🧺 Space complexity: O(n)