NeetCode #101LC-1152MediumArrays & Hashing
← Back to All Problems#101 · #1152 · Analyze User Website Visit Pattern(用户网站访问行为分析)
📌 Problem Statement & Constraints
Given arrays
username, timestamp and website describing visits, find the pattern (an ordered triple of websites) visited by the most users. Ties are broken by choosing the lexicographically smallest pattern. Constraints: 3 <= username.length <= 50, timestamps are distinct, each user visits at least 3 distinct websites.💡 Core Algorithmic Approaches
- Group visits by user and sort each user's visits by timestamp to obtain the chronological website sequence.
- For each user, take the set of all 3-element combinations (subsequences, not necessarily contiguous) of their visit sequence -- the set removes duplicate patterns from the same user, since a pattern counts each user only once.
- Count how many users produced each pattern.
- Pick the pattern with the highest count; ties are broken by lexicographic order, which
minover tuples gives for free.
💻 Benchmark Python3 Implementation
class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int],
website: List[str]) -> List[str]:
from collections import defaultdict
from itertools import combinations
visits = defaultdict(list)
for u, t, w in sorted(zip(username, timestamp, website), key=lambda x: x[1]):
visits[u].append(w) # chronological per user
cnt = defaultdict(int)
for sites in visits.values():
for combo in set(combinations(sites, 3)): # set: one vote per user
cnt[combo] += 1
best = max(cnt.values())
return list(min(k for k, v in cnt.items() if v == best))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n + U * L^3) where U is the number of users and L the visits per user. Sorting dominates for typical inputs; the combination enumeration is bounded by 50 choose 3.
💾 Space Complexity
O(n) for the grouping and the pattern counter.
⚠️ Interview Pitfalls & Follow-ups
- Counting duplicate patterns within one user: a user must contribute at most one vote per pattern, hence the
set(combinations(...)). - Forgetting to sort by timestamp: the visit order would be arbitrary, and the pattern depends on chronology.
- Breaking ties the wrong way: the tie-break is the lexicographically smallest pattern, which
minover the tuples provides. - Using contiguous subarrays instead of combinations: the pattern is a subsequence of the user's visits, not necessarily consecutive.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.