LeetCode 180 - Consecutive Numbers¶

Database Language: MySQL

Difficulty:

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 IF NOT EXISTS Logs (id INT PRIMARY KEY, num INT);
TRUNCATE TABLE Logs;
INSERT INTO Logs (id, num) VALUES ('1', '1');
INSERT INTO Logs (id, num) VALUES ('2', '1');
INSERT INTO Logs (id, num) VALUES ('3', '1');
INSERT INTO Logs (id, num) VALUES ('4', '2');
INSERT INTO Logs (id, num) VALUES ('5', '1');
INSERT INTO Logs (id, num) VALUES ('6', '2');
INSERT INTO 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

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

Either of these 2 queries yields the same result as well as the same query plan:

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	L1	ALL					7	100.00	Using temporary
1	SIMPLE	L2	eq_ref	PRIMARY	PRIMARY	4	func	1	14.29	Using where; Distinct
1	SIMPLE	L3	eq_ref	PRIMARY	PRIMARY	4	func	1	14.29	Using where; Distinct

Runtime: 436ms
Beats: 98.39% as of July 15, 2024

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)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	L1	ALL					7	100.00	Using temporary
1	SIMPLE	L2	eq_ref	PRIMARY	PRIMARY	4	func	1	14.29	Using where; Distinct
1	SIMPLE	L3	eq_ref	PRIMARY	PRIMARY	4	func	1	14.29	Using where; Distinct

Runtime: 424ms
Beats: 99.50% as of July 15, 2024

Solution Runtime Comparison¶

Here's the comparison of the fastest runtime for each of the solutions.

Solution #	Runtime	Beats
1 - Using INNER JOIN	436ms	98.39%
2 - Using EXISTS	424ms	99.50%

As shown above, the query plan using the EXISTS clause produces the same query plan as the one using the INNER JOIN in the first solution but somehow the runtime of the EXISTS solution is faster than the INNER JOIN solution.