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: