LeetCode 180: Consecutive Numbers Solution in SQL Explained

Problem Statement

In LeetCode 180, you’re given a Logs table:

• id (int, primary key, ascending but not necessarily consecutive)
• num (int)

Your task is to write an SQL query to return all numbers that appear at least three times consecutively based on ascending id, in a result table with a single column ConsecutiveNums, ordered arbitrarily. This differs from string manipulation like LeetCode 179: Largest Number, focusing on sequence detection in a database.

Constraints

• Table has at least 1 row.
• id is ascending but may have gaps.
• num can be any integer.

Example

Let’s see a case:

Copy codeLogs table:
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 1   |
+----+-----+
Output:
+---------------+
| ConsecutiveNums |
+---------------+
| 1             |
+---------------+
Explanation:
<ul>
<li>ids 1,2,3: num=1,1,1 (3 consecutive).</li>
<li>ids 4,5,6: num=2,1,2 (no 3 consecutive).</li>
<li>ids 5,6,7: num=1,2,1 (no 3 consecutive).</li>
<li>Only 1 appears 3 times consecutively.</li>
</ul>

This shows we’re finding numbers with consecutive streaks.

Understanding the Problem

How do you solve LeetCode 180: Consecutive Numbers in SQL? We need to:

• Identify sequences where num repeats at least 3 times in a row based on ascending id.
• Handle gaps in id (e.g., not consecutive).
• Return distinct numbers meeting this criterion in a column ConsecutiveNums.

For [1:1, 2:1, 3:1, 4:2, 5:1, 6:2, 7:1], only 1 at ids 1,2,3 forms a streak of 3. We need a query to detect such sequences efficiently, not a ranking task like LeetCode 178: Rank Scores. We’ll use: 1. Triple Self Join: Clear, efficient—our best solution. 2. Window Function with LAG: Alternative approach.

Let’s dive into the best solution.

Best Solution: Triple Self Join Approach

Explanation

Triple Self Join finds consecutive numbers by:

• Joining the Logs table with itself three times (t1, t2, t3).
• Ensuring t1.id + 1 = t2.id and t2.id + 1 = t3.id for consecutive ids.
• Checking t1.num = t2.num = t3.num for matching numbers.
• Selecting distinct t1.num as ConsecutiveNums.

This ensures O(n) time with indexing on id, O(1) extra space beyond result, and clarity without requiring window functions, making it widely compatible.

For the example:

• Join on ids 1,2,3: all num=1, output 1.

Step-by-Step Example

Example: Logs = [1:1, 2:1, 3:1, 4:2, 5:1, 6:2, 7:1]

Goal: Return table with ConsecutiveNums = 1.

• Step 1: Self-join three times.
• t1: All rows.
• t2: Match t1.id + 1 = t2.id.
• t3: Match t2.id + 1 = t3.id.
• Step 2: Check consecutive ids and nums.
• (1,1), (2,1), (3,1): 1+1=2, 2+1=3, nums=1,1,1 → match.
• (2,1), (3,1), (4,2): nums=1,1,2 → no match.
• (3,1), (4,2), (5,1): nums=1,2,1 → no match.
• (4,2), (5,1), (6,2): nums=2,1,2 → no match.
• (5,1), (6,2), (7,1): nums=1,2,1 → no match.
• Step 3: Select distinct matches.
• Only 1 from ids 1,2,3.
• Finish: Return [1].

How the Code Works (Triple Self Join) – Detailed Line-by-Line Explanation

Here’s the SQL query with a thorough breakdown:

Copy code-- Line 1: Select distinct numbers
SELECT DISTINCT 
    t1.num AS ConsecutiveNums
    -- Distinct num from first table (e.g., 1)

-- Line 2: Join Logs table three times
FROM 
    Logs t1
    -- First instance (e.g., id=1, num=1)
JOIN 
    Logs t2
    -- Second instance (e.g., id=2, num=1)
ON 
    t1.id + 1 = t2.id
    -- Consecutive ids (e.g., 1+1=2)
JOIN 
    Logs t3
    -- Third instance (e.g., id=3, num=1)
ON 
    t2.id + 1 = t3.id
    -- Next consecutive id (e.g., 2+1=3)

-- Line 3: Match consecutive numbers
WHERE 
    t1.num = t2.num 
    AND t2.num = t3.num
    -- Ensure same num (e.g., 1=1=1)

This detailed breakdown clarifies how the triple self join efficiently finds consecutive numbers.

Alternative: Window Function with LAG Approach

Explanation

Window Function with LAG uses LAG to check previous values:

• Use LAG(num, 1) and LAG(num, 2) to get the previous two nums.
• Compare num with lags over a partition ordered by id.
• Filter where all three match, select distinct num.

It’s a practical alternative, O(n) time with window functions (database-dependent), O(n) space for window computation, but requires modern SQL support (e.g., MySQL 8.0+), and may be less intuitive.

For the example:

• LAG detects 1,1,1 at ids 1,2,3 → output 1.

Step-by-Step Example (Alternative)

For the same example:

• Step 1: Add lag columns.
• id=1: num=1, lag1=null, lag2=null.
• id=2: num=1, lag1=1, lag2=null.
• id=3: num=1, lag1=1, lag2=1 → match.
• Step 2: Filter matches.
• id=3: 1=1=1 → num=1.
• Step 3: Distinct.
• Output: 1.

How the Code Works (Window Function)

Copy codeSELECT DISTINCT num AS ConsecutiveNums
FROM (
    SELECT 
        num,
        LAG(num, 1) OVER (ORDER BY id) AS prev1,
        LAG(num, 2) OVER (ORDER BY id) AS prev2
    FROM Logs
) t
WHERE num = prev1 AND num = prev2

Complexity

• Triple Self Join:
• Time: O(n) – joins with indexing.
• Space: O(1) – minimal extra space.
• Window Function with LAG:
• Time: O(n) – window computation.
• Space: O(n) – window storage.

Efficiency Notes

Triple Self Join is the best solution with O(n) time and O(1) space, offering compatibility and clarity—Window Function with LAG matches time complexity but requires modern SQL support and O(n) space, making it elegant but less portable.

Key Insights

• Self Join: Direct sequence check.
• LAG: Window-based comparison.
• Consecutive: Id-based ordering.

Additional Example

Copy codeLogs:
| 1 | 2 |
| 2 | 2 |
| 3 | 2 |
| 4 | 3 |
Output:
| 2 |
Explanation: 2 appears 3 times consecutively.

Edge Cases

• No Streaks: [1,2,3] → [].
• Single Row: [1] → [].
• All Same: [1,1,1,1] → [1].

Both solutions handle these well.

Final Thoughts

LeetCode 180: Consecutive Numbers in SQL is a clever sequence challenge. The Triple Self Join solution excels with its efficiency and simplicity, while Window Function with LAG offers a modern alternative. Want more SQL? Try LeetCode 178: Rank Scores for ranking or explore Python Basics for coding skills. Ready to practice? Solve LeetCode 180 on LeetCode with [1:1, 2:1, 3:1, 4:2, 5:1, 6:2, 7:1], aiming for 1—test your skills now!