You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].
A pattern is a list of three websites (not necessarily distinct).
["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.
["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.
Note that the websites in a pattern do not need to be visited contiguously, they only need to be visited in the order they appeared in the pattern.
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: The tuples in this example are:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
The pattern ("home", "about", "career") has score 2 (joe and mary).
The pattern ("home", "cart", "maps") has score 1 (james).
The pattern ("home", "cart", "home") has score 1 (james).
The pattern ("home", "maps", "home") has score 1 (james).
The pattern ("cart", "maps", "home") has score 1 (james).
The pattern ("home", "home", "home") has score 0 (no user visited home 3 times).
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"]
Constraints:
3 <= username.length <= 501 <= username[i].length <= 10timestamp.length == username.length1 <= timestamp[i] <= 109website.length == username.length1 <= website[i].length <= 10username[i] and website[i] consist of lowercase English letters.[username[i], timestamp[i], website[i]] are unique.Problem Overview: Given parallel arrays username, timestamp, and website, determine the most common sequence of three websites visited by users in chronological order. Each user contributes at most one count per 3‑sequence, and ties are resolved using lexicographical order.
Approach 1: Brute Force Pattern Counting (O(n^4) time, O(n) space)
A naive method tries to generate every possible 3‑website sequence globally and checks how many users contain that sequence in order. For each candidate pattern, iterate through every user’s visit list and verify whether the sequence appears in chronological order. This involves nested iterations over websites and repeated scans of user histories. While straightforward, the repeated verification step makes the time complexity roughly O(n^4) in the worst case, so it quickly becomes impractical for larger inputs.
Approach 2: Hash Table + Sorting (O(n log n + c) time, O(n) space)
The efficient solution first sorts all visits by timestamp so each user’s browsing history is in chronological order. After sorting, build a hash map from user → list of visited websites. For each user, generate all possible combinations of three websites using three nested indices i < j < k. Store these patterns in a set to avoid counting duplicate patterns multiple times for the same user. Then update a global frequency map that counts how many users produced each 3‑sequence.
After processing all users, iterate through the frequency map to find the sequence with the highest count. If multiple patterns share the same frequency, choose the lexicographically smallest one. Sorting ensures correct visit order, and the hash table provides constant‑time updates when counting patterns. The overall cost is dominated by sorting O(n log n) plus generating combinations per user.
This approach relies heavily on sorting to maintain chronological order and hash tables for counting patterns efficiently. The input is stored in arrays, making iteration straightforward using basic array traversal.
Recommended for interviews: Interviewers expect the Hash Table + Sorting approach. Starting with a brute-force idea shows you understand the pattern search space, but optimizing with sorting and per‑user combination generation demonstrates strong problem‑solving skills and practical use of hash maps.
First, we use a hash table d to record the websites each user visits. Then we traverse d. For each user, we enumerate all the triplets they visited, count the occurrence of distinct triplets, and finally traverse all triplets, returning the one with the highest occurrence and the smallest lexicographic order.
The time complexity is O(n^3), and the space complexity is O(n^3). Here, n is the length of username.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pattern Counting | O(n^4) | O(n) | Conceptual baseline or for explaining the search space of all 3‑website sequences. |
| Hash Table + Sorting | O(n log n + c) | O(n) | General case. Efficiently counts unique 3‑website patterns per user after sorting visits by time. |
LeetCode 1152. Analyze User Website Visit Pattern - Interview Prep Ep 109 • Fisher Coder • 14,969 views views
Watch 9 more video solutions →Practice Analyze User Website Visit Pattern with our built-in code editor and test cases.
Practice on FleetCode