LeetCode 2308 - Arrange Table by Gender

The problem asks us to rearrange the rows of a Genders table in a specific repeating order while maintaining internal so

leetcodemediumdatabase

LeetCode Problem 2308

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to rearrange the rows of a Genders table in a specific repeating order while maintaining internal sorting. The table has two columns: user_id and gender. The user_id is unique for each row, and the gender column can take one of three values: 'female', 'male', or 'other'. The table guarantees that there are equal numbers of each gender, so no gender will have more or fewer rows than the others.

The goal is to return the rows such that the genders appear in a repeating sequence 'female', 'other', 'male' while ensuring that within each gender, the user_ids are sorted in ascending order. The output should be a complete table that alternates consistently through the three genders in the specified order.

Important details include that the sequence must repeat exactly as 'female', 'other', 'male' and that all IDs within a gender are sorted. Edge cases that could trip up a naive implementation include assuming that any arbitrary gender order is acceptable or failing to maintain internal ID sorting. The problem guarantees the counts are equal, so we do not need to handle uneven distributions.

Approaches

A brute-force approach would be to fetch all rows, separate them into three lists by gender, sort each list, and then interleave them manually. This works because sorting ensures ascending order, and interleaving ensures the correct gender order. However, doing this entirely outside SQL or in multiple nested queries could be verbose and inefficient for large tables.

The optimal solution leverages SQL window functions, specifically ROW_NUMBER(), to assign a rank to each user within their gender. By assigning a row number per gender in ascending order of user_id, we can then join or order all genders based on these row numbers. This guarantees both the internal sorting and the alternating pattern without complex procedural logic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Separate rows by gender, sort each list, and interleave manually
Optimal O(n) O(n) Use SQL ROW_NUMBER() to rank and order in a single query

Algorithm Walkthrough

  1. Use a Common Table Expression (CTE) for each gender (female, other, male) to assign a row number to each user within their gender, sorted by user_id in ascending order. This creates three separate temporary tables with columns user_id, gender, and rn for row number.
  2. Combine all three CTEs using UNION ALL. This gives a single table where each row has its user_id, gender, and its position within its gender group.
  3. Order the combined rows first by rn (row number) and then by a custom CASE statement that converts the gender into the sequence index ('female' = 1, 'other' = 2, 'male' = 3). This ensures the repeating pattern and internal ID sorting.
  4. Return the result table with columns user_id and gender in the final order.

Why it works: Ranking ensures internal sorting of each gender. Ordering first by row number guarantees we pick one from each gender per iteration, and the CASE ensures the correct sequence of genders. This approach produces a perfectly interleaved and sorted table.

Python Solution

Since this is a database problem, a Python solution would typically involve using SQL execution. Here's a direct SQL query that can be executed in Python using any database connector:

# Python solution using SQL execution
query = """
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 * FROM female
    UNION ALL
    SELECT * FROM other
    UNION ALL
    SELECT * FROM male
) t
ORDER BY rn, CASE gender
    WHEN 'female' THEN 1
    WHEN 'other' THEN 2
    WHEN 'male' THEN 3
END
"""

This query implements the algorithm directly, leveraging CTEs and ROW_NUMBER() to simplify interleaving.

Go Solution

In Go, you would execute the same SQL query using a database driver:

query := `
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 * FROM female
    UNION ALL
    SELECT * FROM other
    UNION ALL
    SELECT * FROM male
) t
ORDER BY rn, CASE gender
    WHEN 'female' THEN 1
    WHEN 'other' THEN 2
    WHEN 'male' THEN 3
END;
`

Go does not require any special differences here, except for executing the query using the standard database/sql package and scanning the results into structs.

Worked Examples

Consider the input from the problem statement:

+---------+--------+
| user_id | gender |
+---------+--------+
| 4       | male   |
| 7       | female |
| 2       | other  |
| 5       | male   |
| 3       | female |
| 8       | male   |
| 6       | other  |
| 1       | other  |
| 9       | female |
+---------+--------+

Step 1: Assign row numbers within each gender:

female: 3(1), 7(2), 9(3)
other: 1(1), 2(2), 6(3)
male: 4(1), 5(2), 8(3)

Step 2: Combine all and order by row number, then gender sequence:

rn=1: 3(female), 1(other), 4(male)
rn=2: 7(female), 2(other), 5(male)
rn=3: 9(female), 6(other), 8(male)

Final output matches the expected result.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once for row numbering and ordering. SQL engine optimizations can make it linear over small tables.
Space O(n) CTEs temporarily store all rows with row numbers, requiring linear space in the number of rows.

The linear time and space complexity arise because we only scan and sort small partitions of the table per gender.

Test Cases

# test cases
# example from the problem statement
assert execute_query(Genders) == [
    (3, 'female'), (1, 'other'), (4, 'male'),
    (7, 'female'), (2, 'other'), (5, 'male'),
    (9, 'female'), (6, 'other'), (8, 'male')
]

# minimal case with 1 of each gender
assert execute_query([(1,'female'),(2,'other'),(3,'male')]) == [
    (1,'female'),(2,'other'),(3,'male')
]

# IDs already sorted per gender
assert execute_query([(1,'female'),(4,'female'),(2,'other'),(5,'other'),(3,'male'),(6,'male')]) == [
    (1,'female'),(2,'other'),(3,'male'),
    (4,'female'),(5,'other'),(6,'male')
]

# Random order input
assert execute_query([(10,'male'),(1,'female'),(5,'other'),(2,'female'),(6,'male'),(3,'other')]) == [
    (1,'female'),(3,'other'),(6,'male'),
    (2,'female'),(5,'other'),(10,'male')
]
Test Why
Problem example Validates full alternation and sorting of IDs
Minimal case Ensures algorithm works with smallest table
Already sorted IDs Checks that sorting does not break existing order
Random input Confirms correctness on arbitrary arrangements

Edge Cases

The first edge case is a minimal table with only one row per gender. The implementation handles it correctly because ROW_NUMBER() assigns 1 to each row, and ordering by row number and gender sequence produces the exact required output.

The second edge case is when the user_ids are already sorted within each gender but the original order in the table is mixed. The algorithm still sorts correctly because the ROW_NUMBER() function enforces ordering within each gender regardless of original table order.

The third edge case is if the user_ids are not contiguous or are large integers. The algorithm handles this correctly because ordering is based on value comparison, not the assumption of consecutive numbers.