Table of Contents
Problem Statement
Analyze User Website Visit Pattern LeetCode Solution – 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).
- For example,
["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.
- For example, if the pattern is
["home", "away", "love"], the score is the number of usersxsuch thatxvisited"home"then visited"away"and visited"love"after that. - Similarly, if the pattern is
["leetcode", "love", "leetcode"], the score is the number of usersxsuch thatxvisited"leetcode"then visited"love"and visited"leetcode"one more time after that. - Also, if the pattern is
["luffy", "luffy", "luffy"], the score is the number of usersxsuch thatxvisited"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.
Example
Test Case 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).
Approach:
There are a lot of traps in this problem. The purpose of the solution is to analyze user behavior like a user visiting 3 websites in different sequences. So the same 3 websites sequences for the same user only count once. (this point is very important).
Based on the above, my solution is here
- to use a new class VisitRecord to gather all the information together, sort them with timestamps
- analyze each user’s behavior, use dfs solution to get different 3 websites sequences
- to put all user’s visiting sequences into a map and count the maximum visiting times.
- take all the records that meet maximum visiting times and sort them lexicographically.
- return the first record.
or
- Create a dictionary with username as key and a list of tuples (website, timestamp) as value.
- For each username, sort the tuples based on the timestamp.
- Remove the timestamps from the tuples just add the websites as a list.
- For each username, get all the combinations of 3 websites using backtracking and store it in a dictionary with the tuple of websites as key and list of users as value
- Get the max size of users for each tuple of websites
- Get the lower lexical value of the tuple of websites if it is the same count.
Code for Analyze User Website Visit Pattern
Python Program
from collections import defaultdict
class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
dic = defaultdict(list)
for i in range(len(username)):
dic[username[i]].append((website[i], timestamp[i]))
for k, v in dic.items():
v.sort(key=lambda x: x[1])
new_v = []
for web, time in v:
new_v.append(web)
dic[k] = new_v
combs = defaultdict(list)
for k, v in dic.items():
self.get_all_combinations(v, combs, [], 0, k)
max_size = -1
for k, v in combs.items():
max_size = max(max_size, len(v))
max_list = []
for k, v in combs.items():
if len(v) == max_size and (not max_list or list(k) < max_list):
max_list = list(k)
return max_list
def get_all_combinations(self, website, combs, comb, start, user):
if user in combs[tuple(comb)]:
return
if len(comb) == 3:
combs[tuple(comb)].append(user)
return
for i in range(start, len(website)):
comb.append(website[i])
self.get_all_combinations(website, combs, comb, i+1, user)
comb.pop()C++ Program
class Solution {
public:
vector<string> mostVisitedPattern(vector<string>& name, vector<int>& timestamp, vector<string>& website) {
unordered_map<string, vector<string>> map;
unordered_map<string, int> freq;
vector<tuple<int, string, string>> order;
for(int i=0; i<timestamp.size(); i++){
order.push_back(make_tuple(timestamp[i], name[i], website[i]));
}
sort(order.begin(), order.end());
for(int i=0; i<name.size(); i++){
map[get<1>(order[i])].push_back(get<2>(order[i]));
}
for(auto iter=map.begin(); iter!=map.end(); ++iter){
int size=iter->second.size();
if(size<3){
continue;
}
unordered_set<string> set;
for(int i=0; i<size-2; i++){
string s=iter->second[i];
s+=" ";
for(int j=i+1; j<size-1; j++){
string s1=s+iter->second[j];
s1+=" ";
for(int z=j+1; z<size; z++){
set.insert(s1+iter->second[z]+" ");
}
}
}
for(string temp:set){
freq[temp]++;
}
}
vector<string> s;
int max=0;
for(auto iter=freq.begin(); iter!=freq.end(); ++iter){
if(iter->second>max){
s.clear();
max=iter->second;
s.push_back(iter->first);
}else if(iter->second==max){
s.push_back(iter->first);
}
}
sort(s.begin(), s.end());
vector<string> ans;
int start=0;
for(int i=0; i<s[0].size(); i++){
if(s[0][i]==' '){
ans.push_back(s[0].substr(start, i-start));
start=i+1;
}
}
return ans;
}
};Complexity Analysis for Analyze User Website Visit Pattern LeetCode Solution
Time Complexity: O(N^2)
Space Complexity: O(N)