Retiago Drago

Posted on

# Consecutive Numbers | LeetCode | MSSQL

## Problem Statement

We are given a `Logs` table structured as:

Column Name Type
id int
num varchar

The `id` column is the primary key and is an autoincrement column.

Our task is to write an SQL query to find all numbers that appear at least three times consecutively. We can return the result table in any order.

Example:

Input:

id num
1 1
2 1
3 1
4 2
5 1
6 2
7 2

Output:

ConsecutiveNums
1

Here, '1' is the only number that appears consecutively for at least three times.

## Solution Approaches

We will walk through five different solutions to this problem, highlighting their differences, strengths, and weaknesses.

### Approach 1: Using LEAD, LAG with CTE

The first approach uses `LEAD` and `LAG` window functions with a Common Table Expression (CTE) to create a virtual table that includes the current number, its previous two numbers, and its next two numbers. It then identifies the distinct numbers that appear consecutively three times.

``````WITH lead_lag AS (
SELECT
num,
LAG(num, 1) OVER (ORDER BY id) [prev_num],
LAG(num, 2) OVER (ORDER BY id) [prev2_num],
LEAD(num, 1) OVER (ORDER BY id) [next_num],
LEAD(num, 2) OVER (ORDER BY id) [next2_num]
FROM Logs
)
SELECT DISTINCT num [ConsecutiveNums]
WHERE
(num = prev_num AND prev_num = prev2_num)
OR (prev_num = num AND num = next_num)
OR (num = next_num AND next_num = next2_num)
``````

This method uses explicit window functions for looking ahead and behind. Its runtime is 1302ms, beating 8.96% of LeetCode submissions.

### Approach 2: Using LEAD, LAG with Subquery

The second approach is similar to the first one, but it implements the window functions inside a subquery instead of a CTE.

``````SELECT DISTINCT num [ConsecutiveNums]
FROM
(
SELECT
num,
LAG(num, 1) OVER (ORDER BY id) [prev_num],
LAG(num, 2) OVER (ORDER BY id) [prev2_num],
LEAD(num, 1) OVER (ORDER BY id) [next_num],
LEAD(num, 2) OVER (ORDER BY id) [next2_num]
FROM Logs
) [l]
WHERE
(num = prev_num AND prev_num = prev2_num)
OR (prev_num = num AND num = next_num)
OR (num = next_num AND next_num = next2_num)
``````

Despite the similarity, this method is slightly less performant with a runtime of 1539ms, beating 5.11% of LeetCode submissions.

### Approach 3: Using CASE with CTE

The third approach simplifies the comparison logic by implementing a `CASE` statement that assigns a value to a flag (`is_valid`) indicating whether a number appears consecutively three times or not.

``````WITH consecutive_group AS (
SELECT
num,
CASE
WHEN
LAG(num, 2) OVER (ORDER BY id) = LAG(num, 1) OVER (ORDER BY id)
AND LAG(num, 1) OVER (ORDER BY id) = num
THEN 1
WHEN
LAG(num, 1) OVER (ORDER BY id) = num
AND num = LEAD(num, 1) OVER (ORDER BY id)
THEN 1
WHEN
num = LEAD(num, 1) OVER (ORDER BY id)
AND LEAD(num, 1) OVER (ORDER BY id) = LEAD(num, 2) OVER (ORDER BY id)
THEN 1
ELSE 0
END [is_valid]
FROM Logs
)
SELECT DISTINCT num [ConsecutiveNums]
FROM consecutive_group
WHERE is_valid = 1
``````

This method simplifies the final query and improves performance. The runtime is 914ms, beating 60.10% of LeetCode submissions.

### Approach 4: Using CASE with Subquery

Similar to the comparison between approaches 1 and 2, this approach is the subquery version of approach 3.

``````SELECT DISTINCT num [ConsecutiveNums]
FROM
(
SELECT
num,
CASE
WHEN
LAG(num, 2) OVER (ORDER BY id) = LAG(num, 1) OVER (ORDER BY id)
AND LAG(num, 1) OVER (ORDER BY id) = num
THEN 1
WHEN
LAG(num, 1) OVER (ORDER BY id) = num
AND num = LEAD(num, 1) OVER (ORDER BY id)
THEN 1
WHEN
num = LEAD(num, 1) OVER (ORDER BY id)
AND LEAD(num, 1) OVER (ORDER BY id) = LEAD(num, 2) OVER (ORDER BY id)
THEN 1
ELSE 0
END [is_valid]
FROM Logs
) [c]
WHERE is_valid = 1
``````

While being slightly less performant, the runtime is 988ms, beating 42.41% of LeetCode submissions.

### Approach 5: Simplified Approach with LEAD

In the final approach, we simplify the SQL query by focusing on the consecutive numbers in the 'future' and ignoring the 'past'. This is achieved by only using the `LEAD` window function.

``````SELECT DISTINCT num [ConsecutiveNums]
FROM (
SELECT
num,
LEAD(num, 1) OVER (ORDER BY id) AS next_num,
LEAD(num, 2) OVER (ORDER BY id) AS next2_num
FROM Logs
) [t]
WHERE num = next_num AND num = next2_num
``````

This method provides a cleaner syntax while maintaining a reasonable performance. The runtime is 1049ms, beating 30.79% of LeetCode submissions.

## Conclusion

We have explored five different methods to solve this problem, each with their unique strengths and trade-offs. Each method has shown a different use of window functions, subqueries, and common table expressions.

In terms of performance on LeetCode:

1. Approach 3 is the most performant (914ms runtime, beats 60.10%).
2. Approach 4 follows closely (988ms runtime, beats 42.41%).
3. Approach 5, although simplified, takes third place (1049ms runtime, beats 30.79%).
4. Approach 1, while detailed, comes fourth (1302ms runtime, beats 8.96%).
5. Approach 2, which uses a subquery, is the least performant (1539ms runtime, beats 5.11%).

Note that these rankings may vary based on the actual real-world RDBMS and data distribution.

The original problem can be found on LeetCode.

For more insightful solutions and tech-related content, feel free to connect with me on my Beacons page.

## ranggakd - Link in Bio & Creator Tools | Beacons

@ranggakd | center details summary summary Oh hello there I m a an Programmer AI Tech Writer Data Practitioner Statistics Math Addict Open Source Contributor Quantum Computing Enthusiast details center.

beacons.ai

Saba Shavidze • Edited

It does not work for :

### Input

``````Logs =
| id | num |
| -- | --- |
| 1  | 1   |
| 2  | 1   |
| 4  | 1   |
| 5  | 1   |
| 6  | 2   |
| 7  | 1   |
``````

### output is

``````| ConsecutiveNums |
| --------------- |
| 1               |
``````

### but expected

``````| ConsecutiveNums |
| --------------- |...
``````

We need to check the rows IDs:

## UPDATED

``````WITH cte AS (
SELECT num,
id,
CASE
WHEN LAG(num, 2) OVER (ORDER BY id) = LAG(num, 1) OVER (ORDER BY id)
AND LAG(num, 1) OVER (ORDER BY id) = num
AND LAG(id, 2) OVER (ORDER BY id) = LAG(id, 1) OVER (ORDER BY id) - 1
AND LAG(id, 1) OVER (ORDER BY id) = id - 1
THEN 1
WHEN LAG(num, 1) OVER (ORDER BY id) = num
AND num = LEAD(num, 1) OVER (ORDER BY id)
AND LAG(id, 1) OVER (ORDER BY id) = id - 1
AND id = LEAD(id, 1) OVER (ORDER BY id) - 1
THEN 1
WHEN num = LEAD(num, 1) OVER (ORDER BY id)
AND LEAD(num, 1) OVER (ORDER BY id) = LEAD(num, 2) OVER (ORDER BY id)
AND id = LEAD(id, 1) OVER (ORDER BY id) - 1
AND LEAD(id, 1) OVER (ORDER BY id) = LEAD(id, 2) OVER (ORDER BY id) - 1
THEN 1
ELSE 0
END AS [is_valid]
FROM Logs
)

SELECT DISTINCT num AS [ConsecutiveNums]
FROM cte
WHERE is_valid = 1;

``````