|
| 1 | +##1. Hash Map |
| 2 | + |
| 3 | +::tabs-start |
| 4 | + |
| 5 | +```python |
| 6 | +classSolution: |
| 7 | +defmostVisitedPattern(self,username: List[str],timestamp: List[int],website: List[str]) -> List[str]: |
| 8 | + arr=list(zip(timestamp, username, website)) |
| 9 | + arr.sort() |
| 10 | + |
| 11 | + mp= defaultdict(list) |
| 12 | +for time, user, sitein arr: |
| 13 | + mp[user].append(site) |
| 14 | + |
| 15 | + count= defaultdict(int) |
| 16 | +for userin mp: |
| 17 | + patterns=set() |
| 18 | + cur= mp[user] |
| 19 | +for iinrange(len(cur)): |
| 20 | +for jinrange(i+1,len(cur)): |
| 21 | +for kinrange(j+1,len(cur)): |
| 22 | + patterns.add((cur[i], cur[j], cur[k])) |
| 23 | +for pin patterns: |
| 24 | + count[p]+=1 |
| 25 | + |
| 26 | + max_count=0 |
| 27 | + res=tuple() |
| 28 | +for patternin count: |
| 29 | +if count[pattern]> max_countor (count[pattern]== max_countand pattern< res): |
| 30 | + max_count= count[pattern] |
| 31 | + res= pattern |
| 32 | + |
| 33 | +returnlist(res) |
| 34 | +``` |
| 35 | + |
| 36 | +```java |
| 37 | +publicclassSolution { |
| 38 | +publicList<String>mostVisitedPattern(String[]username,int[]timestamp,String[]website) { |
| 39 | +int n= timestamp.length; |
| 40 | +List<int[]> arr=newArrayList<>(); |
| 41 | +for (int i=0; i< n; i++) arr.add(newint[]{timestamp[i], i}); |
| 42 | + arr.sort((a, b)->Integer.compare(a[0], b[0])); |
| 43 | + |
| 44 | +Map<String,List<String>> mp=newHashMap<>(); |
| 45 | +for (int[] p: arr) { |
| 46 | +int idx= p[1]; |
| 47 | + mp.computeIfAbsent(username[idx], k->newArrayList<>()).add(website[idx]); |
| 48 | + } |
| 49 | + |
| 50 | +Map<String,Integer> count=newHashMap<>(); |
| 51 | +for (String user: mp.keySet()) { |
| 52 | +List<String> cur= mp.get(user); |
| 53 | +Set<String> patterns=newHashSet<>(); |
| 54 | +for (int i=0; i< cur.size(); i++) |
| 55 | +for (int j= i+1; j< cur.size(); j++) |
| 56 | +for (int k= j+1; k< cur.size(); k++) |
| 57 | + patterns.add(cur.get(i)+"#"+ cur.get(j)+"#"+ cur.get(k)); |
| 58 | +for (String p: patterns) |
| 59 | + count.put(p, count.getOrDefault(p,0)+1); |
| 60 | + } |
| 61 | + |
| 62 | +String res=""; |
| 63 | +int max_count=0; |
| 64 | +for (String p: count.keySet()) { |
| 65 | +int c= count.get(p); |
| 66 | +if (c> max_count|| (c== max_count&& p.compareTo(res)<0)) { |
| 67 | + max_count= c; |
| 68 | + res= p; |
| 69 | + } |
| 70 | + } |
| 71 | +returnArrays.asList(res.split("#")); |
| 72 | + } |
| 73 | +} |
| 74 | +``` |
| 75 | + |
| 76 | +```cpp |
| 77 | +classSolution { |
| 78 | +public: |
| 79 | + vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) { |
| 80 | + int n = timestamp.size(); |
| 81 | + vector<pair<int,int>> arr; |
| 82 | + for (int i = 0; i < n; ++i) arr.push_back({timestamp[i], i}); |
| 83 | + sort(arr.begin(), arr.end(), |
| 84 | +[](auto& a, auto& b){ return a.first < b.first; }); |
| 85 | + |
| 86 | + unordered_map<string, vector<string>> mp; |
| 87 | + for (auto& p : arr) mp[username[p.second]].push_back(website[p.second]); |
| 88 | + |
| 89 | + unordered_map<string,int> count; |
| 90 | + for (auto& kv : mp) { |
| 91 | + auto& cur = kv.second; |
| 92 | + unordered_set<string> patterns; |
| 93 | + for (int i = 0; i < (int)cur.size(); ++i) |
| 94 | + for (int j = i + 1; j < (int)cur.size(); ++j) |
| 95 | + for (int k = j + 1; k < (int)cur.size(); ++k) |
| 96 | + patterns.insert(cur[i] + "#" + cur[j] + "#" + cur[k]); |
| 97 | + for (auto& p : patterns) ++count[p]; |
| 98 | + } |
| 99 | + |
| 100 | +int maxCnt =0; |
| 101 | + string res; |
| 102 | +for (auto& kv : count) |
| 103 | +if (kv.second > maxCnt || |
| 104 | + (kv.second == maxCnt && (res.empty() || kv.first < res))) { |
| 105 | + maxCnt = kv.second; |
| 106 | + res = kv.first; |
| 107 | + } |
| 108 | + |
| 109 | + vector<string> ans; |
| 110 | + string tmp; |
| 111 | + for (char ch : res) { |
| 112 | + if (ch == '#') { |
| 113 | + ans.push_back(tmp); |
| 114 | + tmp.clear(); |
| 115 | + } else { |
| 116 | + tmp += ch; |
| 117 | + } |
| 118 | + } |
| 119 | + ans.push_back(tmp); |
| 120 | + return ans; |
| 121 | +} |
| 122 | +}; |
| 123 | +``` |
| 124 | + |
| 125 | +```javascript |
| 126 | +classSolution { |
| 127 | +/** |
| 128 | + *@param{string[]}username |
| 129 | + *@param{number[]}timestamp |
| 130 | + *@param{string[]}website |
| 131 | + *@return{string[]} |
| 132 | +*/ |
| 133 | +mostVisitedPattern(username,timestamp,website) { |
| 134 | +constn=timestamp.length; |
| 135 | +constarr= []; |
| 136 | +for (let i=0; i< n; i++)arr.push([timestamp[i], i]); |
| 137 | +arr.sort((a,b)=> a[0]- b[0]); |
| 138 | + |
| 139 | +constmp=newMap(); |
| 140 | +for (const [,idx]of arr) { |
| 141 | +constuser= username[idx], site= website[idx]; |
| 142 | +if (!mp.has(user))mp.set(user, []); |
| 143 | +mp.get(user).push(site); |
| 144 | + } |
| 145 | + |
| 146 | +constcount=newMap(); |
| 147 | +for (constuserofmp.keys()) { |
| 148 | +constcur=mp.get(user); |
| 149 | +constpatterns=newSet(); |
| 150 | +for (let i=0; i<cur.length; i++) { |
| 151 | +for (let j= i+1; j<cur.length; j++) { |
| 152 | +for (let k= j+1; k<cur.length; k++) { |
| 153 | +patterns.add(`${cur[i]}#${cur[j]}#${cur[k]}`); |
| 154 | + } |
| 155 | + } |
| 156 | + } |
| 157 | +for (constpof patterns) { |
| 158 | +count.set(p, (count.get(p)||0)+1); |
| 159 | + } |
| 160 | + } |
| 161 | + |
| 162 | +let maxCnt=0, res=""; |
| 163 | +for (const [pat,c]ofcount.entries()) { |
| 164 | +if (c> maxCnt|| (c=== maxCnt&& (res===""|| pat< res))) { |
| 165 | + maxCnt= c; |
| 166 | + res= pat; |
| 167 | + } |
| 168 | + } |
| 169 | +returnres.split("#"); |
| 170 | + } |
| 171 | +} |
| 172 | +``` |
| 173 | + |
| 174 | +```csharp |
| 175 | +publicclassSolution { |
| 176 | +publicList<string>MostVisitedPattern(string[]username,int[]timestamp,string[]website) { |
| 177 | +intn=timestamp.Length; |
| 178 | +vararr=newList<(intt,inti)>(); |
| 179 | +for (inti=0;i<n;i++)arr.Add((timestamp[i],i)); |
| 180 | +arr.Sort((a,b)=>a.t.CompareTo(b.t)); |
| 181 | + |
| 182 | +varmp=newDictionary<string,List<string>>(); |
| 183 | +foreach (var (t,idx)inarr) { |
| 184 | +stringuser=username[idx],site=website[idx]; |
| 185 | +if (!mp.ContainsKey(user))mp[user]=newList<string>(); |
| 186 | +mp[user].Add(site); |
| 187 | + } |
| 188 | + |
| 189 | +varcount=newDictionary<string,int>(); |
| 190 | +foreach (varkvinmp) { |
| 191 | +varcur=kv.Value; |
| 192 | +varpatterns=newHashSet<string>(); |
| 193 | +for (inti=0;i<cur.Count;i++) |
| 194 | +for (intj=i+1;j<cur.Count;j++) |
| 195 | +for (intk=j+1;k<cur.Count;k++) |
| 196 | +patterns.Add($"{cur[i]}#{cur[j]}#{cur[k]}"); |
| 197 | +foreach (varpinpatterns) { |
| 198 | +count[p]=count.ContainsKey(p)?count[p]+1:1; |
| 199 | + } |
| 200 | + } |
| 201 | + |
| 202 | +intmaxCnt=0; |
| 203 | +stringres=""; |
| 204 | +foreach (varkvincount) { |
| 205 | +if (kv.Value>maxCnt|| |
| 206 | + (kv.Value==maxCnt&& |
| 207 | + (res==""||string.Compare(kv.Key,res,StringComparison.Ordinal)<0))) { |
| 208 | +maxCnt=kv.Value; |
| 209 | +res=kv.Key; |
| 210 | + } |
| 211 | + } |
| 212 | +returnnewList<string>(res.Split('#')); |
| 213 | + } |
| 214 | +} |
| 215 | +``` |
| 216 | + |
| 217 | +::tabs-end |
| 218 | + |
| 219 | +###Time & Space Complexity |
| 220 | + |
| 221 | +* Time complexity: $O(n \log n + n * u + n ^ 3 * w)$ |
| 222 | +* Space complexity: $O(n * u + n ^ 3 * w)$ |
| 223 | + |
| 224 | +>Where $n$ is the size of the array $timestamp$, $u$ is the maximum length of any string in the array $username$, and $w$ is the maximum length of any string in the array $website$. |