LeetCode 180 - Consecutive Numbers¶

Database Language: PostgreSQL

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

The query plan for this query is as follows:

Unique  (cost=113.58..113.59 rows=1 width=4)
  ->  Sort  (cost=113.58..113.59 rows=1 width=4)
        Sort Key: l1.num
        ->  Nested Loop  (cost=66.66..113.57 rows=1 width=4)
              Join Filter: (l1.num = l3.num)
              ->  Hash Join  (cost=66.50..111.25 rows=11 width=12)
                    Hash Cond: (((l1.id + 1) = l2.id) AND (l1.num = l2.num))
                    ->  Seq Scan on logs l1  (cost=0.00..32.60 rows=2260 width=8)
                    ->  Hash  (cost=32.60..32.60 rows=2260 width=8)
                          ->  Seq Scan on logs l2  (cost=0.00..32.60 rows=2260 width=8)
              ->  Index Scan using logs_pkey on logs l3  (cost=0.16..0.20 rows=1 width=8)
                    Index Cond: (id = (l2.id + 1))
                    Filter: (l2.num = num)

The fastest runtime for the query above is as follows:

Runtime: 244ms
Beats: 95.97% as of July 15, 2024

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:

Unique  (cost=113.55..113.56 rows=1 width=4)
  ->  Sort  (cost=113.55..113.56 rows=1 width=4)
        Sort Key: l1.num
        ->  Nested Loop  (cost=66.66..113.54 rows=1 width=4)
              ->  Hash Join  (cost=66.50..111.25 rows=11 width=12)
                    Hash Cond: (((l1.id + 1) = l2.id) AND (l1.num = l2.num))
                    ->  Seq Scan on logs l1  (cost=0.00..32.60 rows=2260 width=8)
                    ->  Hash  (cost=32.60..32.60 rows=2260 width=8)
                          ->  Seq Scan on logs l2  (cost=0.00..32.60 rows=2260 width=8)
              ->  Index Scan using logs_pkey on logs l3  (cost=0.16..0.20 rows=1 width=8)
                    Index Cond: (id = (l1.id + 2))
                    Filter: (l1.num = num)

Runtime: 240ms
Beats: 98.94% 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)

The query plan generated by PostgreSQL for this query is as follows:

Unique  (cost=113.55..113.56 rows=1 width=4)
  ->  Sort  (cost=113.55..113.56 rows=1 width=4)
        Sort Key: l1.num
        ->  Nested Loop  (cost=66.66..113.54 rows=1 width=4)
              ->  Hash Join  (cost=66.50..111.25 rows=11 width=12)
                    Hash Cond: (((l1.id + 1) = l2.id) AND (l1.num = l2.num))
                    ->  Seq Scan on logs l1  (cost=0.00..32.60 rows=2260 width=8)
                    ->  Hash  (cost=32.60..32.60 rows=2260 width=8)
                          ->  Seq Scan on logs l2  (cost=0.00..32.60 rows=2260 width=8)
              ->  Index Scan using logs_pkey on logs l3  (cost=0.16..0.20 rows=1 width=8)
                    Index Cond: (id = (l1.id + 2))
                    Filter: (l1.num = num)

And the fastest runtime for this query is as follows:

Runtime: 243ms
Beats: 96.86% as of July 15, 2024

Solution Runtime Comparison¶

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

Solution #	Runtime	Beats
1a - Using INNER JOIN	244ms	95.97%
1b - Using INNER JOIN	240ms	98.94%
2 - Using EXISTS	243ms	96.86%