180. Consecutive Numbers
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 42.6%
Problem Breakdown
We are given a table Logs with columns id and num. The goal is to find all distinct numbers (num) that appear in at least three consecutive rows based on the primary key order of id.
Inputs: A SQL database containing the Logs table.
Outputs: A result set containing only the column num, where each number appears consecutively 3+ times.
Constraints & Edge Cases:
- Distinctness: If a number appears for four consecutive rows, it should appear once in the output (not repeated). We need to use
DISTINCT. - Consecutiveness Definition: Consecutive implies strictly adjacent IDs (
id + 1). Gaps in ID sequences break consecutiveness. - Empty Table/Insufficient Rows: If fewer than three rows exist, or no numbers meet the criteria, return an empty result set (handled naturally by SQL).
- Data Types:
numis integer; ensure we don’t accidentally cast strings to integers if schema allows mixed types (though problem implies standard int).
Intuition
First thought: “I can just count how many times each number appears.”
- Naive Approach:
SELECT num, COUNT(*) FROM Logs GROUP BY num HAVING COUNT(*) >= 3. - Why it fails: This counts total occurrences. It doesn’t verify if they are consecutive IDs (e.g., ID 1 and ID 5 both have ‘num’ = X). We need adjacency logic.
Next thought: “I can check neighbors.”
To find a sequence of three, I need to link row i with row i+1, which links to row i+2.
- Key Insight: Use self-joins on the table itself. Join the same table 3 times (aliases L, M, N). Match them such that their IDs are sequential (
L.id = M.id - 1andM.id = N.id - 1) AND their values match (num). - Optimization: Since we only need to know if a number exists in this sequence once per distinct value, wrapping the join result with
DISTINCT numis crucial.
Approach
We will use three self-joins on the Logs table:
- L (Left): Represents the first row of the triplet.
- M (Middle): Joined to L where
M.id = L.id + 1. - N (Right): Joined to M where
N.id = M.id + 1.
Logic:
- Filter rows where
L.num == M.numANDM.num == N.num. This ensures the value is identical across three consecutive IDs. - Select distinct
numfrom this joined result set. - Since
idis a primary key, it will be indexed by default in most SQL engines (like MySQL/Postgres), making these joins efficient ( per lookup) rather than full table scans.
Complexity Analysis
Time: where is the number of rows scanned, assuming id columns are Primary Keys with B-Tree indexes. The self-joins perform index lookups for neighbors in logarithmic time (), resulting in linear overall complexity relative to input size when indexing exists (standard assumption).
Space: auxiliary space relative to input size (excluding result set storage and join buffers), as we are not creating new data structures beyond standard SQL engine memory.
Solution
def solution():
"""
Returns the raw SQL query string for LeetCode 180: Consecutive Numbers.
Note: In a real database environment, this query is executed directly against 'Logs'.
This function simulates returning executable logic in an interview context
where we might need to return code strings depending on platform constraints.
"""
# Constructing the SQL solution as a string for submission/execution
sql_query = """
SELECT DISTINCT L.num AS num
FROM Logs L
JOIN Logs M ON L.id + 1 = M.id AND L.num = M.num
JOIN Logs N ON M.id + 1 = N.id AND M.num = N.num;
"""
return sql_query
# If executed in an environment with access to 'Logs' table:
# result = solution()
Edge Cases Handled
- No Consecutive Matches: The query returns an empty result set if no rows satisfy the join conditions (handled by SQL engine). Note that standard SQL does not return
NULLfor a missing row in this context, but rather zero rows. - Duplicate Sequences: If a number appears for 4 consecutive times, it matches multiple joins.
DISTINCT L.numensures only one row is returned per unique value sequence found (or simply the distinct values satisfying the condition). - Gaps in IDs: The condition
L.id + 1 = M.idexplicitly enforces strict adjacency; any gap (e.g., ID 5 and ID 7) breaks the join, correctly excluding non-consecutive occurrences of the same number.