Solution Explanation for LeetCode 180: Consecutive Numbers

This problem requires finding numbers that appear at least three times consecutively in a table named Logs. The solutions presented use SQL queries. Let's break down each approach:

Solution 1: Two Joins

This approach uses multiple self-joins to identify consecutive numbers.

Logic:

1. First Join (l1 and l2): It joins the Logs table with itself (aliased as l1 and l2). The condition l1.id = l2.id - 1 AND l1.num = l2.num ensures that we are only considering pairs of consecutive rows with the same number. This finds consecutive pairs.

2. Second Join (l2 and l3): This joins the result from the first join with the Logs table again (aliased as l3). The condition l2.id = l3.id - 1 AND l2.num = l3.num extends the search to find a third consecutive row with the same number. This ensures at least three consecutive occurrences.

3. Result Selection: Finally, SELECT DISTINCT l2.num AS ConsecutiveNums selects the unique numbers (num) from the l2 alias (representing the middle number of the three consecutive occurrences) and names the column ConsecutiveNums.

MySQL Code:

SELECT DISTINCT l2.num AS ConsecutiveNums
FROM
    Logs AS l1
    JOIN Logs AS l2 ON l1.id = l2.id - 1 AND l1.num = l2.num
    JOIN Logs AS l3 ON l2.id = l3.id - 1 AND l2.num = l3.num;

Time Complexity: O(n^2), where n is the number of rows in the Logs table. Self-joins can lead to quadratic time complexity in the worst case.

Space Complexity: O(n) in the worst case, as the intermediate join results might store up to O(n) rows.

Solution 2: Window Function (LAG and LEAD)

This solution leverages MySQL's window functions LAG and LEAD for a more efficient approach.

Logic:

1. Window Function Application: The LAG(num) OVER () AS a and LEAD(num) OVER () AS b clauses retrieve the num value from the previous row (a) and the next row (b) for each row in the table, respectively. OVER() without a PARTITION BY clause means these operations are applied across the entire table.

2. Filtering: WHERE a = num AND b = num filters the results to keep only rows where the current num, the previous num, and the next num are all identical, indicating at least three consecutive occurrences.

3. Result Selection: SELECT DISTINCT num AS ConsecutiveNums selects the distinct numbers and renames the column.

MySQL Code:

WITH
    T AS (
        SELECT
            *,
            LAG(num) OVER () AS a,
            LEAD(num) OVER () AS b
        FROM Logs
    )
SELECT DISTINCT num AS ConsecutiveNums
FROM T
WHERE a = num AND b = num;

Time Complexity: O(n), where n is the number of rows. Window functions generally have linear time complexity.

Space Complexity: O(n) to store the intermediate results in the CTE (Common Table Expression) T.

Solution 3: Window Function (Grouping)

This method uses window functions differently to group consecutive numbers and then count occurrences within each group.

Logic:

1. Identify Group Boundaries: The CTE T uses LAG to compare the current num with the previous one. If they are different (IF(num = (LAG(num) OVER ()), 0, 1)), it sets st to 1, marking a potential start of a new group. Otherwise, st is 0.

2. Cumulative Sum for Grouping: CTE S computes the cumulative sum (SUM(st) OVER (ORDER BY id) AS p) of the st values. This assigns a unique group ID (p) to each consecutive sequence of identical numbers.

3. Filtering by Group Size: The final SELECT statement groups the rows by p and uses HAVING COUNT(1) >= 3 to keep only groups with at least three rows (three consecutive identical numbers). DISTINCT ensures only unique numbers are returned.

MySQL Code:

WITH
    T AS (
        SELECT
            *,
            IF(num = (LAG(num) OVER ()), 0, 1) AS st
        FROM Logs
    ),
    S AS (
        SELECT *, SUM(st) OVER (ORDER BY id) AS p
        FROM T
    )
SELECT DISTINCT num AS ConsecutiveNums
FROM S
GROUP BY p
HAVING COUNT(1) >= 3;

Time Complexity: O(n) due to the use of window functions.

Space Complexity: O(n) for the CTEs T and S.

Summary:

Solutions 2 and 3 using window functions are generally preferred over Solution 1 (multiple joins) because of their better time complexity (linear vs. quadratic). Solution 2 is arguably more concise and easier to understand for this specific problem. The choice between Solutions 2 and 3 might depend on personal preference and specific database optimization strategies. Solution 1 is provided for illustrative purposes to show an alternative, albeit less efficient, approach.