603. Analyze User Website Visit Pattern
You are handed an access log as three parallel arrays: usernames[i], timestamps[i], and websites[i] together say that user usernames[i] opened page websites[i] at time timestamps[i]. The log is not sorted.
A pattern is an ordered list of exactly three pages. A user matches a pattern when, after arranging that user's own visits by timestamp, the three pages show up somewhere in that visit history in the given order — they do not have to be consecutive visits, and a pattern may repeat the same page (like (cart, cart, cart)). A user matches a given pattern at most once, no matter how many ways it can be picked out of their history.
Return the pattern matched by the largest number of distinct users, as a list of three page names. If several patterns tie, return the lexicographically smallest one (compare the three pages position by position, like words in a dictionary).
Example 1:
Input: usernames = [alice, alice, alice, bob, bob, bob, bob, bob, carol, carol, carol, dave], timestamps = [1..12], websites = [home, about, careers, home, cart, maps, home, about, home, about, careers, careers]
Output: ["home", "about", "careers"]
Explanation: alice and carol both visited home, then about, then careers — 2 distinct users. No pattern is matched by more than 2 users (bob's visits contain many patterns, but each is his alone, and dave only has one visit).
Example 2:
Input: usernames = [nina, nina, nina, nina], timestamps = [10, 20, 30, 40], websites = [beta, alpha, beta, alpha]
Output: ["alpha", "beta", "alpha"]
Explanation: nina's time-ordered history is beta, alpha, beta, alpha. Every 3-visit pattern she matches — (alpha, beta, alpha), (beta, alpha, alpha), (beta, alpha, beta), (beta, beta, alpha) — is matched by exactly 1 user, so the tie goes to the lexicographically smallest: (alpha, beta, alpha).
Constraints:
- 3 ≤ n ≤ 5000
- 1 ≤ timestamps[i] ≤ 10⁹, and all timestamps are distinct
- usernames[i] and websites[i] are 1-10 lowercase English letters
- At least one user has three or more visits, so an answer always exists
Hints:
The pattern order is time order, not input order. Group the visits by user, then sort each user's visits by timestamp (or sort the whole log once by timestamp before grouping).
One user can match many patterns, but each pattern only once. Build the set of all (a, b, c) triples that appear as a 3-visit subsequence of the user's history — a set kills the duplicates for free.
Map each pattern to the set of users who match it. The answer is the pattern with the biggest user set; break ties by comparing the triples lexicographically (tuples in Python and ordered maps in C++/Java compare exactly that way).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: 12 log entries: alice visits home→about→careers, bob visits home→cart→maps→home→about, carol visits home→about→careers, dave visits careers
Expected output: ["home", "about", "careers"]