339. Analyze User Website Visit Pattern
You are given three arrays: username, website, and timestamp, all of the same length n.
The ith tuple [username[i], website[i], timestamp[i]] represents that user username[i] visited website website[i] at time timestamp[i].
A pattern is a sequence of exactly three websites (not necessarily distinct) visited by the same user in chronological order.
- For example, if the pattern is ["home", "work", "gym"], the score counts how many users visited these three pages in this exact order (not necessarily consecutively).
- If the pattern is ["striver", "youtube", "striver"], the score counts users who visited "striver", then "youtube", then returned to "striver" again later.
- If the pattern is ["takeuforward", "takeuforward", "takeuforward"], the score counts users who visited the "takeuforward" page at three different timestamps in chronological order.
Important: The three websites in a pattern don't need to be consecutive visits — there can be other page visits in between. We only care about maintaining the relative chronological order.
Your task is to find the most visited pattern — the pattern visited by the maximum number of distinct users. If multiple patterns have the same maximum count, return the lexicographically smallest one.
Example 1:
Input : username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"],
timestamp = [1,2,3,4,5,6,7,8,9,10],
website["home","about","career","home","cart","maps","home","home","about","career"]
Output : ["home", "about", "career"]
Explanation :
joe visited "home" -> "about" -> "career"
james visited "home" -> "cart" -> "maps" and "cart" -> "maps" -> "home"
mary visited "home" -> "about" -> "career"
The pattern "home" -> "about" -> "career" was visited by both joe and mary, while no other pattern was visited by more than one user.
Example 2:
Input : username = ["ua","ua","ua","ub","ub","ub"],
timestamp = [1,2,3,4,5,6],
website = ["a","b","a","a","b","c"]
Output : ["a","b","a"]
Explanation :
Step 1: Grouping User Visits
Each user’s website visit history (sorted by timestamp):
- User "ua" → [(1, "a"), (2, "b"), (3, "a")]
- User "ub" → [(4, "a"), (5, "b"), (6, "c")]
Step 2: Generating 3-sequence Patterns
Each user has visited at least 3 websites, so we form all possible 3-sequence patterns:
- User "ua":["a", "b", "a"]
- User "ub":["a", "b", "c"]
Step 3: Counting Frequency
- ["a", "b", "a"] → 1 occurrence
- ["a", "b", "c"] → 1 occurrence
Since both sequences appear only once, we select the lexicographically smallest sequence.
Step 4: Choosing the Lexicographically Smallest Sequence
- ["a", "b", "a"] comes before ["a", "b", "c"] in lexicographical order.
Now Your Turn!
Pick the correct output for the given inputInput : username = ["alice", "bob", "alice", "bob", "alice", "bob", "alice"],
timestamp = [1,2,3,4,5,6,7],
website = ["x", "y", "x", "y", "x", "y", "z"]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- n == username.length == timestamp.length == website.length
- 3 <= n <= 50
- 1 <= username[i].length, website[i].length <= 10
- 0 <= timestamp[i] <= 10^99
- username[i] and website[i] consist of lowercase English letters.
- It is guaranteed that the given timestamps are strictly increasing.