Problem

Table: Data

+-------------+------+
| Column Name | Type |
+-------------+------+
| first_col   | int  |
| second_col  | int  |
+-------------+------+
This table may contain duplicate rows.

Write a solution to independently:

  • order first_col in ascending order.
  • order second_col in descending order.

The result format is 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

Input: 
Data table:
+-----------+------------+
| first_col | second_col |
+-----------+------------+
| 4         | 2          |
| 2         | 3          |
| 3         | 1          |
| 1         | 4          |
+-----------+------------+
Output: 
+-----------+------------+
| first_col | second_col |
+-----------+------------+
| 1         | 4          |
| 2         | 3          |
| 3         | 2          |
| 4         | 1          |
+-----------+------------+

Solution

Method 1 – Independent Sorting and Row Construction

Intuition

We need to sort the first column in ascending order and the second column in descending order, then pair the sorted values row-wise. This is a classic independent column sort and zip problem.

Approach

  1. Select all values from first_col and sort them in ascending order.
  2. Select all values from second_col and sort them in descending order.
  3. Pair the sorted values row-wise to form the result.

Code

1
2
3
4
5
6
7

SELECT
  t1.first_col,
  t2.second_col
FROM
  (SELECT first_col, ROW_NUMBER() OVER (ORDER BY first_col ASC) AS rn FROM Data) t1
  JOIN (SELECT second_col, ROW_NUMBER() OVER (ORDER BY second_col DESC) AS rn FROM Data) t2
  ON t1.rn = t2.rn;
1
2
3
4
5
6
7

SELECT
  t1.first_col,
  t2.second_col
FROM
  (SELECT first_col, ROW_NUMBER() OVER (ORDER BY first_col ASC) AS rn FROM Data) t1
  JOIN (SELECT second_col, ROW_NUMBER() OVER (ORDER BY second_col DESC) AS rn FROM Data) t2
  ON t1.rn = t2.rn;
1
2
3
4
5

class Solution:
    def order_columns(self, data: 'pd.DataFrame') -> 'pd.DataFrame':
        a = sorted(data['first_col'])
        b = sorted(data['second_col'], reverse=True)
        return pd.DataFrame({'first_col': a, 'second_col': b})

Complexity

  • ⏰ Time complexity: O(N log N), where N is the number of rows. Sorting each column independently is O(N log N).
  • 🧺 Space complexity: O(N), for storing the sorted columns and the result.