LeetCode 180 - Consecutive Numbers

This problem asks us to find numbers in a table that appear at least three times consecutively in order of their id. The table Logs consists of two columns: id and num, where id is an auto-incrementing primary key and num is a string representing a number.

leetcodemediumdatabase

LeetCode Problem 180

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to find numbers in a table that appear at least three times consecutively in order of their id. The table Logs consists of two columns: id and num, where id is an auto-incrementing primary key and num is a string representing a number. The consecutive property is determined by the order of id, so we are not concerned with the overall frequency of a number in the table, but rather with sequences of repeated numbers in contiguous rows.

The input represents a list of logs in sequential order, and the output is a table containing a single column, ConsecutiveNums, which lists all numbers that satisfy the "three consecutive appearances" condition. There are no explicit constraints on the size of the table, but since this is a database problem, we can assume it may contain thousands to millions of rows. Edge cases include sequences that appear exactly three times, sequences that appear more than three times, and numbers that appear non-consecutively.

The problem guarantees that the id column uniquely identifies each row and increments by 1, which simplifies detecting consecutive numbers. It does not require the output to be sorted, giving some flexibility in the query.

Approaches

The brute-force approach involves self-joining the table multiple times to check for sequences of three consecutive rows with the same number. Specifically, we can join Logs with itself twice, offsetting by 1 and 2, and check whether num in all three rows matches. While this approach is correct, it requires multiple table scans and joins, which is inefficient for large datasets.

The optimal approach leverages window functions, specifically the LEAD function in SQL. By looking at the current row and the next two rows simultaneously, we can check for three consecutive identical numbers in a single pass. This approach avoids expensive joins and scales well for large tables.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Uses multiple self-joins; inefficient for large tables
Optimal O(n) O(n) Uses window functions to check sequences in a single scan

Algorithm Walkthrough

  1. Use the LEAD function: For each row, compute the values of num in the next one and two rows using LEAD(num, 1) and LEAD(num, 2). This allows us to access consecutive rows without joining the table multiple times.
  2. Compare values: Check if the current num matches the next two numbers. This ensures that there is a sequence of three consecutive identical numbers.
  3. Select distinct numbers: Since a number might appear in multiple overlapping sequences of three, use DISTINCT to avoid duplicates in the output.
  4. Return the results: Output the resulting numbers in a single column called ConsecutiveNums.

This approach works because the window function evaluates the next rows in the sequence efficiently, and the comparison guarantees at least three consecutive occurrences.

Python Solution

class Solution:
    def consecutiveNumbers(self, logs: list[dict]) -> list[dict]:
        result = set()
        n = len(logs)
        for i in range(n - 2):
            if logs[i]['num'] == logs[i+1]['num'] == logs[i+2]['num']:
                result.add(logs[i]['num'])
        return [{'ConsecutiveNums': num} for num in result]

In this Python implementation, we iterate over the logs, checking each triplet of consecutive rows for equality. We use a set to store numbers that satisfy the condition, ensuring no duplicates, and then convert the set into the required list of dictionaries format.

Go Solution

package main

type Log struct {
    ID  int
    Num string
}

func ConsecutiveNumbers(logs []Log) []map[string]string {
    resultMap := make(map[string]bool)
    n := len(logs)
    for i := 0; i <= n-3; i++ {
        if logs[i].Num == logs[i+1].Num && logs[i].Num == logs[i+2].Num {
            resultMap[logs[i].Num] = true
        }
    }
    result := make([]map[string]string, 0, len(resultMap))
    for num := range resultMap {
        result = append(result, map[string]string{"ConsecutiveNums": num})
    }
    return result
}

In Go, we define a Log struct to model the input. We use a map as a set to track numbers meeting the consecutive condition and then convert it into a slice of maps for the final output. The approach is analogous to Python.

Worked Examples

Example Input:

Logs = [
  {ID:1, Num:"1"},
  {ID:2, Num:"1"},
  {ID:3, Num:"1"},
  {ID:4, Num:"2"},
  {ID:5, Num:"1"},
  {ID:6, Num:"2"},
  {ID:7, Num:"2"}
]

Iteration Trace:

i logs[i]['num'] logs[i+1]['num'] logs[i+2]['num'] Add to result? result set
0 "1" "1" "1" Yes {"1"}
1 "1" "1" "2" No {"1"}
2 "1" "2" "1" No {"1"}
3 "2" "1" "2" No {"1"}
4 "1" "2" "2" No {"1"}
5 "2" "2" N/A No {"1"}

Final output: [{"ConsecutiveNums":"1"}]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the logs array to check triplets
Space O(n) Storing unique numbers in a set or map

The time complexity is linear because each row is examined only once, and the space complexity depends on the number of distinct consecutive numbers, which is at most n in the worst case.

Test Cases

# Provided example
assert Solution().consecutiveNumbers([
    {'ID':1, 'Num':'1'},
    {'ID':2, 'Num':'1'},
    {'ID':3, 'Num':'1'},
    {'ID':4, 'Num':'2'},
    {'ID':5, 'Num':'1'},
    {'ID':6, 'Num':'2'},
    {'ID':7, 'Num':'2'}
]) == [{'ConsecutiveNums':'1'}]  # 1 appears consecutively three times

# Edge case: exactly three consecutive at end
assert Solution().consecutiveNumbers([
    {'ID':1, 'Num':'3'},
    {'ID':2, 'Num':'3'},
    {'ID':3, 'Num':'4'},
    {'ID':4, 'Num':'4'},
    {'ID':5, 'Num':'4'}
]) == [{'ConsecutiveNums':'4'}]

# Edge case: multiple sequences
assert set(tuple(d.items())[0] for d in Solution().consecutiveNumbers([
    {'ID':1, 'Num':'5'},
    {'ID':2, 'Num':'5'},
    {'ID':3, 'Num':'5'},
    {'ID':4, 'Num':'6'},
    {'ID':5, 'Num':'6'},
    {'ID':6, 'Num':'6'},
])) == {('ConsecutiveNums', '5'), ('ConsecutiveNums', '6')}

# Edge case: no consecutive numbers
assert Solution().consecutiveNumbers([
    {'ID':1, 'Num':'7'},
    {'ID':2, 'Num':'8'},
    {'ID':3, 'Num':'7'}
]) == []

# Edge case: all numbers the same
assert Solution().consecutiveNumbers([
    {'ID':1, 'Num':'9'},
    {'ID':2, 'Num':'9'},
    {'ID':3, 'Num':'9'},
    {'ID':4, 'Num':'9'},
]) == [{'ConsecutiveNums':'9'}]
Test Why
Provided example Validates detection of a sequence of three consecutive numbers
Sequence at end Ensures last triplet is detected
Multiple sequences Confirms algorithm handles multiple valid sequences
No consecutive numbers Tests empty output case
All numbers same Confirms algorithm handles sequences longer than three

Edge Cases

One important edge case is when the table contains fewer than three rows. In such cases, it is impossible to have three consecutive numbers, so the algorithm correctly returns an empty result.

Another edge case is sequences that overlap, e.g., four or more consecutive numbers. The algorithm handles this by adding the number once to a set, avoiding duplicate entries even if multiple triplets overlap.

A third edge case is non-numeric values in the num column. Since the problem treats num as a string, our comparison works correctly without numeric conversion, and sequences of identical strings are detected.