LeetCode 180 - Consecutive Numbers
Database Language: SQL Server
Difficulty: Medium
Problem Description
Input
Table: Logs
| Column Name | Type |
| ----------- | ------- |
| id | int |
| num | varchar |
In SQL, `id` is the primary key for this table. `id` is an autoincrement column.
Requirement
Find all numbers that appear at least three times consecutively.
Return the result table in any order.
The result format is in the following example.
Examples
Example 1
Input:
Logs table:
| id | num |
| -- | --- |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 1 |
| 6 | 2 |
| 7 | 2 |
Output
| ConsecutiveNums |
| --------------- |
| 1 |
Explanation
1 is the only number that appears consecutively for at least three times.
SQL Schema
CREATE TABLE [dbo].[Logs] (id INT PRIMARY KEY, num INT);
TRUNCATE TABLE [dbo].[Logs];
INSERT INTO [dbo].[Logs] (id, num) VALUES ('1', '1');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('2', '1');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('3', '1');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('4', '2');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('5', '1');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('6', '2');
INSERT INTO [dbo].[Logs] (id, num) VALUES ('7', '2');
Solutions
There are a couple of ways of finding all numbers that appear at least three times consecutively. First is by using INNER JOIN and joining the table to itself 3 times. Second is by using the EXISTS operator in the WHERE clause.
Solution #1 - Using INNER JOIN
To find all numbers that appear at least three times consecutively using INNER JOIN, the Logs table need to be self-joined to itself three times because we are looking for cases when a number appear consecutively at least three times.
Before finding all numbers that appear at least three times consecutively, let's first try to find all numbers that appear at least 2 times consecutively. The following query can be used to accomplish this:
SELECT DISTINCT L1.num AS ConsecutiveNums
FROM Logs L1 INNER JOIN Logs L2
ON L1.id + 1 = L2.id AND L1.num = L2.num
Based on this query, we are looking for a row where the current ID and the succeeding ID (`L1.id + 1 = L2.id`) have a `num` value that are the same (`L1.num = L2.num`).
The DISTINCT clause needs to be added in the query because a number can appear 2 times consecutively multiple times.
But the requirement is to find all numbers that appear at least three times consecutively instead of two times. The query can be extended by joining the `Logs` table again through the addition of the following INNER JOIN:
INNER JOIN Logs L3
ON L2.id + 1 = L3.id AND L2.num = L3.num
The full query now looks as follows:
# Final Solution 1 Query - Using INNER JOIN
SELECT DISTINCT L1.num AS ConsecutiveNums
FROM Logs L1 INNER JOIN Logs L2
ON L1.id + 1 = L2.id AND L1.num = L2.num
INNER JOIN Logs L3
ON L2.id + 1 = L3.id AND L2.num = L3.num
The query plan for this query is as follows:
|--Sort(DISTINCT ORDER BY:([L1].[num] ASC))
|--Nested Loops(Inner Join, OUTER REFERENCES:([L2].[num], [Expr1003]))
|--Compute Scalar(DEFINE:([Expr1003]=[leetcode].[dbo].[Logs].[id] as [L2].[id]+(1)))
| |--Nested Loops(Inner Join, OUTER REFERENCES:([L1].[num], [Expr1004]))
| |--Compute Scalar(DEFINE:([Expr1004]=[leetcode].[dbo].[Logs].[id] as [L1].[id]+(1)))
| | |--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L1]))
| |--Clustered Index Seek(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L2]),
SEEK:([L2].[id]=[Expr1004]),
WHERE:([leetcode].[dbo].[Logs].[num] as [L1].[num]=[leetcode].[dbo].[Logs].[num] as [L2].[num])
ORDERED FORWARD)
|--Clustered Index Seek(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L3]),
SEEK:([L3].[id]=[Expr1003]),
WHERE:([leetcode].[dbo].[Logs].[num] as [L2].[num]=[leetcode].[dbo].[Logs].[num] as [L3].[num])
ORDERED FORWARD)
The fastest runtime for the query above is as follows:
This query joins the `L1` Logs table with `L2` Logs table and then the `L2` Logs table with `L3` Logs table. Another way of joining the Logs tables is between the `L1` Logs table with `L2` Logs table and then between the `L1` Logs table with `L3` Logs table. The query will look as follows:
# Final Solution 1 Query - Using INNER JOIN
SELECT DISTINCT L1.num AS ConsecutiveNums
FROM Logs L1 INNER JOIN Logs L2
ON L1.id + 1 = L2.id AND L1.num = L2.num
INNER JOIN Logs L3
ON L1.id + 2 = L3.id AND L1.num = L3.num
The query plan for this alternative query is as follows:
|--Sort(DISTINCT ORDER BY:([L1].[num] ASC))
|--Nested Loops(Inner Join, OUTER REFERENCES:([L3].[num], [Expr1004]))
|--Nested Loops(Inner Join, OUTER REFERENCES:([L1].[num], [Expr1003]))
| |--Compute Scalar(DEFINE:([Expr1003]=[leetcode].[dbo].[Logs].[id] as [L1].[id]+(2),
[Expr1004]=[leetcode].[dbo].[Logs].[id] as [L1].[id]+(1)))
|--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L1]))
|--Clustered Index Seek(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L3]),
SEEK:([L3].[id]=[Expr1003]),
WHERE:([leetcode].[dbo].[Logs].[num] as [L1].[num]=[leetcode].[dbo].[Logs].[num] as [L3].[num])
ORDERED FORWARD)
|--Clustered Index Seek(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L2]),
SEEK:([L2].[id]=[Expr1004]),
WHERE:([leetcode].[dbo].[Logs].[num] as [L3].[num]=[leetcode].[dbo].[Logs].[num] as [L2].[num])
ORDERED FORWARD)
The fastest runtime for the query above is as follows:
Solution #2 - Using EXISTS
The second way of finding all numbers that appear at least three times consecutively is with the use of the EXISTS clause twice as part of the WHERE condition. The first EXISTS clause will check if the `num` value of the current ID is the same as the `num` value of the succeeding ID:
EXISTS (SELECT 'X' FROM Logs L2 WHERE L1.id + 1 = L2.id AND L1.num = L2.num)
The second EXISTS condition will check if the `num` value of the current ID is the same as the `num` value of the ID after the next ID (`L1.id + 2 = L3.id`):
EXISTS (SELECT 'X' FROM Logs L3 WHERE L1.id + 2 = L3.id AND L1.num = L3.num)
The full query that uses the EXISTS clause twice is as follows:
# Final Solution 2 Query - Using EXISTS
SELECT DISTINCT num AS ConsecutiveNums
FROM Logs L1
WHERE EXISTS (SELECT 'X' FROM Logs L2 WHERE L1.id + 1 = L2.id AND L1.num = L2.num) AND
EXISTS (SELECT 'X' FROM Logs L3 WHERE L1.id + 2 = L3.id AND L1.num = L3.num)
The query plan generated by SQL Server for this query is as follows:
|--Sort(DISTINCT ORDER BY:([L1].[num] ASC))
|--Nested Loops(Left Semi Join, WHERE:([Expr1005]=[leetcode].[dbo].[Logs].[id] as [L3].[id] AND
[leetcode].[dbo].[Logs].[num] as [L1].[num]=[leetcode].[dbo].[Logs].[num] as [L3].[num]))
|--Nested Loops(Left Semi Join, WHERE:([Expr1006]=[leetcode].[dbo].[Logs].[id] as [L2].[id] AND
[leetcode].[dbo].[Logs].[num] as [L1].[num]=[leetcode].[dbo].[Logs].[num] as [L2].[num]))
| |--Compute Scalar(DEFINE:([Expr1005]=[leetcode].[dbo].[Logs].[id] as [L1].[id]+(2),
[Expr1006]=[leetcode].[dbo].[Logs].[id] as [L1].[id]+(1)))
| | |--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L1]))
| |--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L2]))
|--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Logs].[PK_Logs] AS [L3]))
And the fastest runtime for this query is as follows:
Solution Runtime Comparison
Here's the comparison of the fastest runtime for each of the solutions.
| Solution # | Runtime | Beats |
| --------------------- | ------- | ------ |
| 1a - Using INNER JOIN | 533ms | 81.53% |
| 1b - Using INNER JOIN | 525ms | 83.15% |
| 2 - Using EXISTS | 576ms | 69.30% |
Related Articles: