Grouping and Sequence

What is this?

You have a pile of shuffled train tickets and want the longest unbroken stretch of consecutive seat numbers. The wasteful method: pick a ticket, hunt for the next number, then the next, and repeat that hunt for every ticket. The efficient method: spread them all out first so any number can be found instantly, then only start counting from a ticket whose predecessor is missing — the head of a run. Every run is then walked exactly once.

That discipline — a set for instant lookup, plus a rule about where you are allowed to start — is the first half of this chapter. The second half scales the same grouping instinct up to a log of user activity.

💡 Fun fact: Longest Consecutive Sequence is the classic demonstration that O(n) can hide inside a nested loop. The inner while looks like it makes the whole thing quadratic, and interviewers will push on exactly that. The answer is an amortisation argument: the inner loop only runs for run heads, and across all heads it visits each value at most once. Being able to say that cleanly is worth more than the code.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: a hash structure makes lookup free, but free lookup alone does not make an algorithm linear — you also need a rule that stops you re-walking the same work. "Only start from a run head" and "group first, then tally once per group" are two versions of that rule.

1. The run-head discipline

Given [100, 4, 200, 1, 3, 2], build a set and then ask, for each value v, is v - 1 in the set?

set = {100, 4, 200, 1, 3, 2}

v=100 → 99 absent  → HEAD. walk 100, 101? no        → length 1
v=4   → 3 present  → skip (4 is mid-run)
v=200 → 199 absent → HEAD. walk 200, 201? no        → length 1
v=1   → 0 absent   → HEAD. walk 1,2,3,4, 5? no      → length 4  ✅
v=3   → 2 present  → skip
v=2   → 1 present  → skip

The three skips are the whole optimisation. Without the head check, starting at 4 would re-walk 4, starting at 3 would re-walk 3,4, and the cost becomes quadratic on a long run. With it, every value is visited at most twice — once in the outer loop, once inside the run that owns it.

Sorting is the honest baseline here at O(n log n), and worth stating before you give the linear answer. The hash version wins only because the set converts "what comes next" into O(1).

2. The group-then-tally shape

The second problem swaps values for records. When rows carry a key (a user, a session, a device), the reflex is:

1. Group rows by that key.
2. Order each group by whatever gives it meaning — usually time.
3. Enumerate the combinations you care about within a group.
4. Tally those combinations across all groups, then pick the winner by a stated tie-break.

The reason step 3 is safe is that groups are small and independent. Enumerating every 3-page journey for one user with 10 visits is 120 combinations; doing it across the raw log without grouping would be meaningless as well as huge.

3. Where you'll actually meet this

• Product analytics. "What is the most common three-screen path before checkout?" is Analyze User Website Visit Pattern verbatim — group by user, order by timestamp, count journeys.
• Fraud and abuse detection. Consecutive-ID runs betray scripted account creation; grouping events per actor before scoring is the standard first step.
• Inventory and allocation. Longest run of consecutive free seats, ports, IPs or block numbers — the run-head sweep over an allocation table.
• Log processing. Sessionisation groups raw events by user and orders them by time before any pattern is extracted, exactly like step 2 above.
• Databases. GROUP BY plus a window function is the engine's version of this shape; recognising it in application code is the same skill.

4. Problems in this chapter

▶ Longest Consecutive Sequence

Find the longest run of consecutive integers in an unsorted array, in O(n). A set gives lookup, the run-head check gives linearity, and the amortisation argument is what the interviewer is actually testing.
Pattern: set membership + run heads. Target: O(n) time, O(n) space.

▶ Analyze User Website Visit Pattern

Find the 3-page pattern visited by the most distinct users, breaking ties lexicographically. Group visits by user, sort each user's visits by timestamp, enumerate their 3-page subsequences as a set (so one user cannot vote twice for the same pattern), then tally.
Pattern: group → order → enumerate → tally. Target: O(u · k³) over users and their visit counts.

5. Common pitfalls 🚫

• Skipping the head check. The code still returns the right answer and still passes small tests — it just becomes O(n²) on a single long run, which is the exact input the interviewer will reach for.
• Sorting "to be safe" and calling it O(n). If you sort, say O(n log n). Claiming linear while sorting is worse than giving the sorted answer honestly.
• Counting a user twice in the pattern problem. One user visiting A→B→C through several routes must contribute one vote — deduplicate that user's patterns with a set before tallying.
• Forgetting the tie-break. "Lexicographically smallest among the most frequent" is part of the specification, not a detail; sorting the candidate patterns at the end is the simplest fix.
• Sorting visits by the wrong key. Timestamps, not insertion order — the input is explicitly unordered.
• Duplicates in the value set. Duplicates in the input collapse in a set, which is correct here, but say so rather than letting the interviewer wonder if you noticed.

6. Key takeaways

1. Free lookup is not enough — you also need a rule that prevents re-walking work. The run-head check is that rule.
2. Amortisation is the answer to "isn't that quadratic?" Each value participates in exactly one run.
3. Group before you compute. Independent groups let you enumerate combinations that would be nonsense across the raw collection.
4. Deduplicate within a group before tallying across groups, or one heavy actor dominates the result.
5. State the sorted baseline first. O(n log n) then O(n) shows you know what the hash structure is buying.
6. Why interviewers like it: it separates candidates who reach for a set from candidates who can explain why using one is linear.

Order: Longest Consecutive Sequence → Analyze User Website Visit Pattern.