Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1152.html
1152. Analyze User Website Visit Pattern
Level
Medium
Description
We are given some website visits: the user with name username[i]
visited the website website[i]
at time timestamp[i]
.
A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits. (The websites in a 3-sequence are not necessarily distinct.)
Find the 3-sequence visited by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.
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", 1, "home"]
["joe", 2, "about"]
["joe", 3, "career"]
["james", 4, "home"]
["james", 5, "cart"]
["james", 6, "maps"]
["james", 7, "home"]
["mary", 8, "home"]
["mary", 9, "about"]
["mary", 10, "career"]
The 3-sequence ("home", "about", "career") was visited at least once by 2 users.
The 3-sequence ("home", "cart", "maps") was visited at least once by 1 user.
The 3-sequence ("home", "cart", "home") was visited at least once by 1 user.
The 3-sequence ("home", "maps", "home") was visited at least once by 1 user.
The 3-sequence ("cart", "maps", "home") was visited at least once by 1 user.
Note:
3 <= N = username.length = timestamp.length = website.length <= 50
1 <= username[i].length <= 10
0 <= timestamp[i] <= 10^9
1 <= website[i].length <= 10
- Both
username[i]
andwebsite[i]
contain only lowercase characters. - It is guaranteed that there is at least one user who visited at least 3 websites.
- No user visits two websites at the same time.
Solution
Create a class Struct
. Each object of type Struct
contains a username, a timestamp and a website. The objects of type Struct
are comparable using timestamp. Create an array of type Struct
to store all the elements created from the three input arrays. Then sort the array of type Struct
in ascending order.
Loop over the array of type Struct
and obtain all the websites visited by each user in ascending order. For each user, obtain the websites and generate all possible 3-sequences, and update the counts of each 3-sequence. Note that since the target is to find the 3-sequence visited by the largest number of users, for each user, a 3-sequence can be counted at most once. After all users’ 3-sequences are visited, obtain the 3-sequence with the maximum count and is the lexicographically smallest, and return the 3-sequence.
-
class Solution { public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) { int length = username.length; Struct[] array = new Struct[length]; for (int i = 0; i < length; i++) array[i] = new Struct(username[i], timestamp[i], website[i]); Arrays.sort(array); Map<String, List<String>> userVisitsMap = new HashMap<String, List<String>>(); for (int i = 0; i < length; i++) { Struct struct = array[i]; String curUser = struct.username; String curWebsite = struct.website; List<String> list = userVisitsMap.getOrDefault(curUser, new ArrayList<String>()); list.add(curWebsite); userVisitsMap.put(curUser, list); } int maxCount = 0; Map<String, Integer> countMap = new HashMap<String, Integer>(); Map<String, List<String>> strListMap = new HashMap<String, List<String>>(); Set<String> set = userVisitsMap.keySet(); for (String user : set) { Set<String> sequenceSet = new HashSet<String>(); List<String> list = userVisitsMap.getOrDefault(user, new ArrayList<String>()); int size = list.size(); if (size >= 3) { for (int i = 0; i < size - 2; i++) { String website1 = list.get(i); for (int j = i + 1; j < size - 1; j++) { String website2 = list.get(j); for (int k = j + 1; k < size; k++) { String website3 = list.get(k); List<String> sequence = new ArrayList<String>(); sequence.add(website1); sequence.add(website2); sequence.add(website3); String sequenceStr = sequence.toString(); if (sequenceSet.add(sequenceStr)) { int count = countMap.getOrDefault(sequenceStr, 0) + 1; maxCount = Math.max(maxCount, count); countMap.put(sequenceStr, count); strListMap.put(sequenceStr, sequence); } } } } } } List<List<String>> candidates = new ArrayList<List<String>>(); Set<String> sequenceSet = countMap.keySet(); for (String sequenceStr : sequenceSet) { int count = countMap.getOrDefault(sequenceStr, 0); if (count == maxCount) candidates.add(strListMap.get(sequenceStr)); } Collections.sort(candidates, new Comparator<List<String>>() { public int compare(List<String> sequence1, List<String> sequence2) { return sequence1.toString().compareTo(sequence2.toString()); } }); return candidates.get(0); } } class Struct implements Comparable<Struct> { String username; int timestamp; String website; public Struct(String username, int timestamp, String website) { this.username = username; this.timestamp = timestamp; this.website = website; } public int compareTo(Struct struct2) { if (this.timestamp != struct2.timestamp) return this.timestamp - struct2.timestamp; else return this.username.compareTo(struct2.username); } }
-
class Solution: def mostVisitedPattern( self, username: List[str], timestamp: List[int], website: List[str] ) -> List[str]: d = defaultdict(list) for user, _, site in sorted( zip(username, timestamp, website), key=lambda x: x[1] ): d[user].append(site) cnt = Counter() for sites in d.values(): m = len(sites) s = set() if m > 2: for i in range(m - 2): for j in range(i + 1, m - 1): for k in range(j + 1, m): s.add((sites[i], sites[j], sites[k])) for t in s: cnt[t] += 1 return sorted(cnt.items(), key=lambda x: (-x[1], x[0]))[0][0]
-
class Solution { public: vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) { unordered_map<string, vector<pair<int, string>>> d; int n = username.size(); for (int i = 0; i < n; ++i) { auto user = username[i]; int ts = timestamp[i]; auto site = website[i]; d[user].emplace_back(ts, site); } unordered_map<string, int> cnt; for (auto& [_, sites] : d) { int m = sites.size(); unordered_set<string> s; if (m > 2) { sort(sites.begin(), sites.end()); for (int i = 0; i < m - 2; ++i) { for (int j = i + 1; j < m - 1; ++j) { for (int k = j + 1; k < m; ++k) { s.insert(sites[i].second + "," + sites[j].second + "," + sites[k].second); } } } } for (auto& t : s) { cnt[t]++; } } int mx = 0; string t; for (auto& [p, v] : cnt) { if (mx < v || (mx == v && t > p)) { mx = v; t = p; } } return split(t, ','); } vector<string> split(string& s, char c) { vector<string> res; stringstream ss(s); string t; while (getline(ss, t, c)) { res.push_back(t); } return res; } };
-
func mostVisitedPattern(username []string, timestamp []int, website []string) []string { d := map[string][]pair{} for i, user := range username { ts := timestamp[i] site := website[i] d[user] = append(d[user], pair{ts, site}) } cnt := map[string]int{} for _, sites := range d { m := len(sites) s := map[string]bool{} if m > 2 { sort.Slice(sites, func(i, j int) bool { return sites[i].ts < sites[j].ts }) for i := 0; i < m-2; i++ { for j := i + 1; j < m-1; j++ { for k := j + 1; k < m; k++ { s[sites[i].site+","+sites[j].site+","+sites[k].site] = true } } } } for t := range s { cnt[t]++ } } mx, t := 0, "" for p, v := range cnt { if mx < v || (mx == v && p < t) { mx = v t = p } } return strings.Split(t, ",") } type pair struct { ts int site string }