Problem

Table: CoffeeShop

1
2
3
4
5
6
7
8
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| drink       | varchar |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row in this table shows the order id and the name of the drink ordered. Some drink rows are nulls.

Write a solution to replace the null values of the drink with the name of the drink of the previous row that is not null. It is guaranteed that the drink on the first row of the table is not null.

Return the result table in the same order as the input.

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
Input: 
CoffeeShop table:
+----+-------------------+
| id | drink             |
+----+-------------------+
| 9  | Rum and Coke      |
| 6  | null              |
| 7  | null              |
| 3  | St Germain Spritz |
| 1  | Orange Margarita  |
| 2  | null              |
+----+-------------------+
Output: 
+----+-------------------+
| id | drink             |
+----+-------------------+
| 9  | Rum and Coke      |
| 6  | Rum and Coke      |
| 7  | Rum and Coke      |
| 3  | St Germain Spritz |
| 1  | Orange Margarita  |
| 2  | Orange Margarita  |
+----+-------------------+
Explanation: 
For ID 6, the previous value that is not null is from ID 9. We replace the null with "Rum and Coke".
For ID 7, the previous value that is not null is from ID 9. We replace the null with "Rum and Coke;.
For ID 2, the previous value that is not null is from ID 1. We replace the null with "Orange Margarita".
Note that the rows in the output are the same as in the input.

Solution

Method 1 – Window Function with Last Non-Null Value Propagation

Intuition: To fill null values in a column with the previous non-null value (in the original order), we can use a window function that propagates the last non-null value seen so far. In SQL, this is typically done using the LAST_VALUE or MAX window function with a frame that looks backwards.

Approach:

  1. Use the MAX(drink) window function over an ordered window that starts at the first row and ends at the current row.
  2. For each row, this gives the most recent non-null drink up to and including that row.
  3. Return the result in the same order as the input.

Code

1
2
3
4
5
SELECT
  id,
  MAX(drink) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS drink
FROM CoffeeShop
ORDER BY FIELD(id, (SELECT GROUP_CONCAT(id ORDER BY id) FROM CoffeeShop));
1
2
3
4
5
SELECT
  id,
  MAX(drink) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS drink
FROM CoffeeShop
ORDER BY id;

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)