LeetCode 180: Consecutive Numbers

Problem Restatement

We are given a table named Logs.

The column id is the primary key. It is an auto-increment column starting from 1.

We need to find every number that appears at least three times consecutively.

The result can be returned in any order. The output column should be named ConsecutiveNums. The official statement asks for all numbers that appear at least three times consecutively.

Input and Output

Expected output column:

ConsecutiveNums

Examples

Input:

Logs
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+

Rows 1, 2, and 3 all have num = 1.

So 1 appears at least three times consecutively.

Output:

+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

First Thought: Compare Each Row With the Next Two Rows

A number appears three times consecutively when we can find three adjacent rows:

id, id + 1, id + 2

with the same num.

For example:

id = 1, num = 1
id = 2, num = 1
id = 3, num = 1

These three rows form a valid consecutive group.

So the direct SQL idea is to join the table with itself three times:

Then we require:

l2.id = l1.id + 1
l3.id = l1.id + 2

and:

l1.num = l2.num
l2.num = l3.num

Key Insight

The id column gives the row order.

Because id is auto-incrementing from 1, three consecutive rows can be detected by checking adjacent id values.

So we do not need grouping first. We can look for any window of three adjacent rows with the same num.

Algorithm

1. Use Logs as l1.
2. Join Logs as l2, where l2.id = l1.id + 1.
3. Join Logs as l3, where l3.id = l1.id + 2.
4. Keep only rows where all three num values are equal.
5. Select DISTINCT l1.num so duplicate valid windows return only one row per number.
6. Rename the output column to ConsecutiveNums.

Correctness

A number should be returned only if it appears in three adjacent rows.

The joins enforce adjacency:

l2.id = l1.id + 1
l3.id = l1.id + 2

So l1, l2, and l3 represent three consecutive rows.

The equality checks enforce the same number:

l1.num = l2.num
l2.num = l3.num

Therefore, every returned value appears at least three times consecutively.

Now consider any number that appears at least three times consecutively. Among that run, take the first three rows. Their ids are consecutive, and their num values are equal. The joins will find those rows and return the number.

DISTINCT removes duplicate results when a number appears in a longer run, such as four or five times in a row.

Complexity

Without indexes, the database may choose a more expensive join plan. Since id is the primary key, the expected plan is efficient.

Implementation

SELECT DISTINCT
    l1.num AS ConsecutiveNums
FROM Logs l1
JOIN Logs l2
    ON l2.id = l1.id + 1
JOIN Logs l3
    ON l3.id = l1.id + 2
WHERE l1.num = l2.num
  AND l2.num = l3.num;

Code Explanation

This starts from each possible first row:

FROM Logs l1

Then it joins the next row:

JOIN Logs l2
    ON l2.id = l1.id + 1

Then it joins the row after that:

JOIN Logs l3
    ON l3.id = l1.id + 2

At this point, each joined result represents three consecutive rows.

This condition checks that all three rows have the same number:

WHERE l1.num = l2.num
  AND l2.num = l3.num

Finally, this returns each qualifying number once:

SELECT DISTINCT
    l1.num AS ConsecutiveNums

Alternative Implementation With Window Functions

We can also use LAG and LEAD.

WITH x AS (
    SELECT
        num,
        LAG(num) OVER (ORDER BY id) AS prev_num,
        LEAD(num) OVER (ORDER BY id) AS next_num
    FROM Logs
)
SELECT DISTINCT
    num AS ConsecutiveNums
FROM x
WHERE num = prev_num
  AND num = next_num;

Here each row compares itself with the previous row and the next row.

If all three values are equal, then the current row is the middle of a three-row consecutive group.

Testing

Test case 1:

CREATE TABLE Logs (
    id INT PRIMARY KEY,
    num VARCHAR(255)
);

INSERT INTO Logs (id, num) VALUES
(1, '1'),
(2, '1'),
(3, '1'),
(4, '2'),
(5, '1'),
(6, '2'),
(7, '2');

Expected:

+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

Test case 2:

DELETE FROM Logs;

INSERT INTO Logs (id, num) VALUES
(1, '1'),
(2, '1'),
(3, '1'),
(4, '1');

Expected:

+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

The DISTINCT matters here because there are two valid windows: ids 1,2,3 and ids 2,3,4.

Test case 3:

DELETE FROM Logs;

INSERT INTO Logs (id, num) VALUES
(1, '1'),
(2, '2'),
(3, '1'),
(4, '2');

Expected:

+-----------------+
| ConsecutiveNums |
+-----------------+

No number appears three times consecutively.

Test case 4:

DELETE FROM Logs;

INSERT INTO Logs (id, num) VALUES
(1, '7'),
(2, '7'),
(3, '7'),
(4, '8'),
(5, '8'),
(6, '8');

Expected:

+-----------------+
| ConsecutiveNums |
+-----------------+
| 7               |
| 8               |
+-----------------+