Watch 5 video solutions for Find the Start and End Number of Continuous Ranges, a medium level problem involving Database. This walkthrough by Everyday Data Science has 6,591 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Problem Overview: Given a table of numeric log_id values, the goal is to compress consecutive numbers into ranges. Each continuous sequence should return a single row containing the starting number and ending number of that range.
Approach 1: Group By + Window Function (O(n) time, O(n) space)
This approach relies on the observation that consecutive numbers share a constant difference between the value and its row index. Use the ROW_NUMBER() window function to assign a sequential index ordered by log_id. For each row, compute log_id - ROW_NUMBER(). Consecutive numbers produce the same difference, which naturally groups them into ranges. After generating this grouping key, aggregate using GROUP BY and compute MIN(log_id) and MAX(log_id) for each group. The database performs a single ordered scan, giving O(n) time after sorting and O(n) auxiliary space for the window calculation. This pattern appears frequently when solving sequence grouping problems with SQL and window functions.
Approach 2: Default Approach (Session Variables) (O(n) time, O(1) extra space)
MySQL session variables can track when a range starts and ends while scanning rows in sorted order. Sort the table by log_id and maintain variables storing the previous value and the current range start. When the current log_id is not equal to previous + 1, a new range begins. The previous value marks the end of the last range, and the current value becomes the new start. This approach avoids window functions and works well in older MySQL environments that lack advanced analytic features. The query still performs a linear pass through the ordered data, so time complexity is O(n) with constant extra memory.
Recommended for interviews: The window-function grouping approach is the cleanest and most expressive solution. Interviewers expect you to recognize the value - row_number trick for consecutive sequences and combine it with GROUP BY aggregation. The variable-based approach shows deeper knowledge of MySQL internals but is less portable across SQL engines.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group By + Window Function | O(n) | O(n) | Preferred modern SQL solution when window functions like ROW_NUMBER() are available |
| Session Variables (Default MySQL) | O(n) | O(1) | Useful in MySQL environments without window functions or when minimizing memory usage |
