Skip to content

1285. Find the Start and End Number of Continuous Ranges πŸ”’

Description

Table: Logs

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| log_id        | int     |
+---------------+---------+
log_id is the column of unique values for this table.
Each row of this table contains the ID in a log Table.

 

Write a solution to find the start and end number of continuous ranges in the table Logs.

Return the result table ordered by start_id.

The result format is in the following example.

 

Example 1:

Input: 
Logs table:
+------------+
| log_id     |
+------------+
| 1          |
| 2          |
| 3          |
| 7          |
| 8          |
| 10         |
+------------+
Output: 
+------------+--------------+
| start_id   | end_id       |
+------------+--------------+
| 1          | 3            |
| 7          | 8            |
| 10         | 10           |
+------------+--------------+
Explanation: 
The result table should contain all ranges in table Logs.
From 1 to 3 is contained in the table.
From 4 to 6 is missing in the table
From 7 to 8 is contained in the table.
Number 9 is missing from the table.
Number 10 is contained in the table.

Solutions

Solution 1: Group By + Window Function

Thinking

Consecutive logs differ by \(1\). A \(0/1\) from β€œdifference from the previous row is \(1\)”, then a prefix sum, puts a run in one group. \(MIN\)/\(MAX\) \(log\_id\) per that id are the range ends.

We need to find a way to group a continuous sequence of logs into the same group, and then aggregate each group to obtain the start and end logs of each group.

There are two ways to implement grouping:

  1. By calculating the difference between each log and the previous log, if the difference is \(1\), then the two logs are continuous, and we set \(delta\) to \(0\), otherwise we set it to \(1\). Then we take the prefix sum of \(delta\) to obtain the grouping identifier for each row.
  2. By calculating the difference between the current log and its row number, we obtain the grouping identifier for each row.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            log_id,
            SUM(delta) OVER (ORDER BY log_id) AS pid
        FROM
            (
                SELECT
                    log_id,
                    IF((log_id - LAG(log_id) OVER (ORDER BY log_id)) = 1, 0, 1) AS delta
                FROM Logs
            ) AS t
    )
SELECT MIN(log_id) AS start_id, MAX(log_id) AS end_id
FROM T
GROUP BY pid;

Solution 2

Thinking

Solution 1 discretizes gaps then prefix-sums. \(log\_id\) minus row number is constant on a consecutive run, so that difference is the island key and we drop \(LAG\) and the conditional \(delta\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            log_id,
            log_id - ROW_NUMBER() OVER (ORDER BY log_id) AS pid
        FROM Logs
    )
SELECT MIN(log_id) AS start_id, MAX(log_id) AS end_id
FROM T
GROUP BY pid;

Comments