Consecutive Numbers - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given a table or sequence of logged numbers. The task is to return all values that appear at least three times consecutively. Order matters: the same number must appear in three adjacent records, not just three total occurrences.
Approach 1: Sliding Window Using Array Traversal (O(n) time, O(1) space)
Traverse the ordered records and examine a window of three consecutive positions at a time. For index i, compare nums[i], nums[i-1], and nums[i-2]. If all three values match, you found a valid consecutive sequence. This works because a run of three identical adjacent values guarantees the requirement. The algorithm performs a single linear scan and only stores the result set, so space complexity stays constant. This approach is conceptually identical to a sliding window over a fixed window size of three.
In SQL-based versions of the problem, the same logic is implemented using self joins or window functions like LAG() and LEAD() to compare neighboring rows. In imperative languages such as Python, Java, or C++, you simply iterate through the array and compare neighbors directly.
Approach 2: HashMap / Dictionary to Count Consecutive Streaks (O(n) time, O(n) space)
Track consecutive streaks while iterating through the sequence. Maintain a dictionary where the current number maps to its ongoing streak length. When the current value equals the previous value, increment the streak; otherwise reset the streak to 1. Once the streak reaches 3, record that number in the result. The hash map allows flexible tracking if the dataset is processed as a stream or if multiple sequences must be monitored simultaneously. Lookups and updates run in constant time using a hash map.
This approach is slightly more general than the sliding window technique because it explicitly tracks streak lengths rather than checking a fixed window. It is useful when the problem changes to "k consecutive occurrences" instead of exactly three.
Recommended for interviews: The sliding window traversal is the most expected solution. It shows you recognize that only adjacent comparisons are required and that a constant-size window solves the problem in O(n) time and O(1) space. Mentioning the hash map streak approach demonstrates deeper understanding and adaptability if the requirement changes to variable-length sequences. Both approaches are common patterns when working with ordered datasets or database logs.
Approach 1: 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.
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.
Complexity
Time Complexity: O(n), where n is the number of elements in the list. Space Complexity: O(1).
Approach 2: 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.
In C, we use an auxiliary array to mimic a hashmap for counting occurrences of numbers. We focus on consecutive occurrences rather than entire counts, thus determining which numbers are consecutive.
Complexity
Time Complexity: O(n). Space Complexity: O(1) since we use only limited extra space.
Approach 3: Two Joins
We can use two joins to solve this problem.
First, we perform a self-join with the condition l1.num = l2.num and l1.id = l2.id - 1, so that we can find all numbers that appear at least twice in a row. Then, we perform another self-join with the condition l2.num = l3.num and l2.id = l3.id - 1, so that we can find all numbers that appear at least three times in a row. Finally, we only need to select the distinct l2.num.
Approach 4: Window Function
We can use the window functions LAG and LEAD to obtain the num of the previous row and the next row of the current row, and record them in the fields a and b, respectively. Finally, we only need to filter out the rows where a = num and b = num, which are the numbers that appear at least three times in a row. Note that we need to use the DISTINCT keyword to remove duplicates from the results.
We can also group the numbers by using the IF function to determine whether the num of the current row is equal to the num of the previous row. If they are equal, we set it to 0, otherwise we set it to 1. Then, we use the window function SUM to calculate the prefix sum, which is the grouping identifier. Finally, we only need to group by the grouping identifier and filter out the numbers with a row count greater than or equal to 3 in each group. Similarly, we need to use the DISTINCT keyword to remove duplicates from the results.
Code
MySQL
Approach 5: Default Approach
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Using Array Traversal | Time Complexity: O(n), where n is the number of elements in the list. Space Complexity: O(1). |
| HashMap/Dictionary to Count Occurrences and Track Sequences | Time Complexity: O(n). Space Complexity: O(1) since we use only limited extra space. |
| Two Joins | — |
| Window Function | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Using Array Traversal | O(n) | O(1) | Best general solution when data is ordered and you only need to check fixed-length consecutive values |
| HashMap / Dictionary Streak Tracking | O(n) | O(n) | Useful when tracking variable-length sequences or processing streaming data |
Video Solution
LeetCode 180: Consecutive Numbers [SQL] • Frederik Müller • 27,581 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Consecutive Numbers easy or hard?
How to solve Consecutive Numbers in O(n)?
What is the best approach for Consecutive Numbers?
What data structure is used in Consecutive Numbers?
What is the time complexity of Consecutive Numbers?
Consecutive Numbers Python or Java solution approach?
Is Consecutive Numbers asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Consecutive Numbers with our built-in code editor and test cases.
Practice on FleetCode