# LeetCode 180: Consecutive Numbers

## Problem Restatement

We are given a table named `Logs`.

| Column | Type |
|---|---|
| id | int |
| num | varchar |

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

| Item | Meaning |
|---|---|
| Input | Table `Logs(id, num)` |
| Output | One column named `ConsecutiveNums` |
| Rule | Return numbers that appear at least three times in adjacent rows |
| Order | Any order is accepted |

Expected output column:

```sql
ConsecutiveNums
```

## Examples

Input:

```text
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:

```text
+-----------------+
| 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:

```text
id, id + 1, id + 2
```

with the same `num`.

For example:

```text
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:

| Alias | Meaning |
|---|---|
| `l1` | First row |
| `l2` | Next row |
| `l3` | Row after that |

Then we require:

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

and:

```sql
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:

```sql
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:

```sql
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` expected | Joins on primary key `id` can use indexed lookups |
| Space | `O(k)` | The result stores distinct qualifying numbers |

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

## Implementation

```sql
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:

```sql
FROM Logs l1
```

Then it joins the next row:

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

Then it joins the row after that:

```sql
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:

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

Finally, this returns each qualifying number once:

```sql
SELECT DISTINCT
    l1.num AS ConsecutiveNums
```

## Alternative Implementation With Window Functions

We can also use `LAG` and `LEAD`.

```sql
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:

```sql
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:

```text
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
```

Test case 2:

```sql
DELETE FROM Logs;

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

Expected:

```text
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
```

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

Test case 3:

```sql
DELETE FROM Logs;

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

Expected:

```text
+-----------------+
| ConsecutiveNums |
+-----------------+
```

No number appears three times consecutively.

Test case 4:

```sql
DELETE FROM Logs;

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

Expected:

```text
+-----------------+
| ConsecutiveNums |
+-----------------+
| 7               |
| 8               |
+-----------------+
```