⚡Flashcard Drill➔
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

  1. Group visits by user and sort each user's visits by timestamp to obtain the chronological website sequence.
  2. 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.
  3. Count how many users produced each pattern.
  4. Pick the pattern with the highest count; ties are broken by lexicographic order, which min over 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 min over 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems