#180 Consecutive Numbers - Solution

Table: Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
In SQL, id is the primary key for this table.
id is an autoincrement column starting from 1.

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.

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.

The Consecutive Numbers problem asks you to identify numbers in a log table that appear at least three times in a row. Since this is a database problem, the key idea is to compare rows with their neighboring rows based on the row order (usually defined by an id column).

One common approach is using self-joins. By joining the table with itself multiple times (e.g., comparing rows t1, t2, and t3), you can check whether the same value appears in three consecutive positions. If the values match and the IDs are sequential, that number qualifies as a valid result.

A more modern and cleaner method uses window functions such as LAG() or LEAD(). These functions allow you to access previous or next rows within the ordered dataset, making it easy to verify whether a number repeats consecutively.

Both strategies scan the dataset once or with minimal joins, leading to efficient performance for typical interview datasets. The main goal is correctly identifying consecutive row relationships while avoiding duplicate outputs.

Approach	Time Complexity	Space Complexity
Self Join on Consecutive IDs	O(n)	O(1)
Window Functions (LAG/LEAD)	O(n)	O(1)

Solutions (12)

Sliding Window Using Array Traversal

We can use a sliding window approach with a counter to track consecutive numbers as we iterate through the list.

Time Complexity: O(n), where n is the number of elements in the list. Space Complexity: O(1).

C C++Java Python C#JavaScript

1#include <stdio.h>
2#include <stdlib.h>
3
4void findConsecutiveNumbers(int nums[], int size) {
5    int count = 1, lastNum = nums[0];
6    for (int i = 1; i < size; i++) {
7        if (nums[i] == lastNum) {
8            count++;
9            if (count == 3) {
10                printf("%d\n", lastNum);
11                return;  // Return immediately after finding the first number
12            }
13        } else {
14            count = 1;
15            lastNum = nums[i];
16        }
17    }
18}
19
20int main() {
21    int nums[] = {1, 1, 1, 2, 1, 2, 2};
22    int size = sizeof(nums) / sizeof(nums[0]);
23    findConsecutiveNumbers(nums, size);
24    return 0;
25}
26

Explanation

In C, we traverse the array while maintaining a counter to track consecutive identical numbers. If the sequence reaches three and continues consecutively, the number is printed and the function terminates.

HashMap/Dictionary to Count Occurrences and Track Sequences

This approach uses a HashMap (or Dictionary in Python) to keep track of the sequence counts of numbers. This way, we can determine if any number is repeated consecutively at least three times.

Time Complexity: O(n). Space Complexity: O(1) since we use only limited extra space.

C C++Java Python C#JavaScript

1#include <iostream>
2#include <unordered_map>
#include <vector>
using namespace std;

vector<int> findConsecutiveNumbers(vector<int>& nums) {
    unordered_map<int, int> count;
    vector<int> result;
    int consecutive = 1;
    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i - 1]) {
            consecutive++;
            if (consecutive == 3 && count[nums[i - 1]] != 1) {
                result.push_back(nums[i]);
                count[nums[i]] = 1;
            }
        } else {
            consecutive = 1;
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 1, 1, 2, 1, 2, 2};
    vector<int> result = findConsecutiveNumbers(nums);
    for (int num : result) cout << num << endl;
    return 0;
}