LeetCode 1285 - Find the Start and End Number of Continuous Ranges

LeetCode Problem 1285

Difficulty: 🟡 Medium
Topics: Database

Solution

Here’s a full technical solution guide for LeetCode 1285 following your requested structure and formatting:

Problem Understanding

The problem asks us to find contiguous ranges of integers in a database table called Logs. Each row in the table contains a unique integer log_id. A contiguous range is a sequence of consecutive integers without gaps. For example, if the table contains 1, 2, 3, 7, 8, 10, the ranges are [1,3], [7,8], and [10,10]. The output should list the start and end of each range, ordered by start_id.

The input is a table of integers that are unique and unsorted. There may be gaps between numbers, meaning a range ends when the next consecutive integer is missing. The expected output is a table of ranges, with columns start_id and end_id.

Important edge cases include a table with a single row, consecutive numbers with no gaps, all numbers isolated (no consecutive pairs), and very large numbers where integer overflow could theoretically be an issue. The problem guarantees uniqueness, so we do not need to handle duplicates.

Approaches

The brute-force approach is to iterate through each possible integer between the minimum and maximum log_id in the table and check if it exists in the table. For each integer, we check whether it starts a range, continue until the next number is missing, and then record the range. While this approach works correctly, it is inefficient, because it requires scanning potentially large gaps between the minimum and maximum values. If the range between the smallest and largest log_id is large, this method is unnecessarily slow.

The key insight for an optimal solution is to sort the log_id values and then iterate through them once, keeping track of the start of the current range. When a gap is detected (the next log_id is more than 1 greater than the current), we record the range. This is efficient because sorting is O(n log n), and a single pass through the sorted list is O(n), making it much faster than scanning every integer in the potential range.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(max_id - min_id)	O(n)	Iterates through the entire range of possible numbers
Optimal	O(n log n)	O(n)	Sort log_id and scan once, detecting gaps

Algorithm Walkthrough

1. Retrieve all log_id values from the Logs table and store them in a list.
2. Sort the list of log_id values in ascending order.
3. Initialize an empty result list and a variable start to track the beginning of a current range.
4. Iterate through the sorted log_id values. For each value, check if it continues the current range (i.e., it is exactly 1 greater than the previous value).
5. If the current value does not continue the range, record the previous range from start to the previous value and update start to the current value.
6. After the loop completes, record the last range from start to the last log_id in the list.
7. Return the result ordered by start_id.

Why it works: The invariant is that start always points to the beginning of the current contiguous sequence. When a gap is found, we know the previous range is complete. By sorting first, all consecutive numbers are adjacent, ensuring no ranges are missed.

Python Solution

from typing import List
import sqlite3

class Solution:
    def findContinuousRanges(self, conn: sqlite3.Connection) -> List[tuple]:
        cursor = conn.cursor()
        cursor.execute("SELECT log_id FROM Logs")
        logs = [row[0] for row in cursor.fetchall()]
        
        if not logs:
            return []

        logs.sort()
        result = []
        start = logs[0]

        for i in range(1, len(logs)):
            if logs[i] != logs[i-1] + 1:
                result.append((start, logs[i-1]))
                start = logs[i]

        result.append((start, logs[-1]))
        return result

The code first retrieves all log_id values from the database. After checking for an empty table, it sorts the logs. Using a single loop, it detects gaps and appends ranges to the result list. Finally, it appends the last range and returns the full list of ranges.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "sort"
)

func findContinuousRanges(db *sql.DB) [][2]int {
    rows, _ := db.Query("SELECT log_id FROM Logs")
    defer rows.Close()

    var logs []int
    for rows.Next() {
        var id int
        rows.Scan(&id)
        logs = append(logs, id)
    }

    if len(logs) == 0 {
        return nil
    }

    sort.Ints(logs)
    result := make([][2]int, 0)
    start := logs[0]

    for i := 1; i < len(logs); i++ {
        if logs[i] != logs[i-1]+1 {
            result = append(result, [2]int{start, logs[i-1]})
            start = logs[i]
        }
    }
    result = append(result, [2]int{start, logs[len(logs)-1]})
    return result
}

In Go, we handle SQL queries with database/sql and store log_id values in a slice. Sorting is done with sort.Ints. Ranges are appended as [2]int arrays. The logic mirrors Python, with differences in type handling and slices.

Worked Examples

Input: [1, 2, 3, 7, 8, 10]

Iteration	Current log	Start	Action	Result
1	2	1	2 = 1+1, continue	[]
2	3	1	3 = 2+1, continue	[]
3	7	1	7 != 3+1, append (1,3), start=7	[(1,3)]
4	8	7	8 = 7+1, continue	[(1,3)]
5	10	7	10 != 8+1, append (7,8), start=10	[(1,3),(7,8)]
End	-	10	Append last range (10,10)	[(1,3),(7,8),(10,10)]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, linear scan is O(n)
Space	O(n)	Store logs in memory and result list

The sorting step is the most expensive operation. Additional space is needed to store logs in memory and the result ranges.

Test Cases

# test cases
assert Solution().findContinuousRanges(sqlite3.connect(':memory:')) == []  # empty table
assert Solution().findContinuousRanges(sqlite3.connect(':memory:')) == [(1,1)]  # single entry
assert Solution().findContinuousRanges(sqlite3.connect(':memory:')) == [(1,3),(7,8),(10,10)]  # example case
assert Solution().findContinuousRanges(sqlite3.connect(':memory:')) == [(1,5)]  # consecutive only
assert Solution().findContinuousRanges(sqlite3.connect(':memory:')) == [(1,1),(3,3),(5,5)]  # all isolated

Test	Why
empty table	handles no data gracefully
single entry	handles minimal input
example case	validates correctness on problem-provided input
consecutive only	tests fully contiguous range
all isolated	tests multiple single-element ranges

Edge Cases

One edge case is an empty Logs table. Our implementation immediately returns an empty result list, preventing errors from attempting to access elements of an empty list. Another edge case is a table with a single log_id. The solution correctly treats it as a range from that value to itself. A third edge case is multiple non-consecutive single-element ranges, where each log_id is isolated. By checking for gaps between consecutive elements, the algorithm correctly appends each as a range of length one. These cases cover potential pitfalls that could arise if the code assumed the presence of multiple consecutive numbers or did not handle empty input.