1152.Analyze User Website Visit Pattern

• Link:1152. Analyze User Website Visit Pattern - Medium
• Track: NeetCode150

Question

Restate the problem

• Given three arrays username, timestamp, website (each index = one visit event)
• find the 3-sequence of websites visited by the most users.
• A 3-sequence is any ordered triple (a, b, c) from a user’s visit history (not necessarily consecutive).
• Return the lexicographically smallest if there’s a tie.

Edge Case

• A user with fewer than 3 visits → combinations returns nothing, skipped naturally
• Same user visits same pattern multiple times → count only once per user (use set)
• Tie on count → return lexicographically smallest pattern

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Sort + itertools.combinations	$O(n\log n+U{m}^3)$	$O(U{m}^3)$
Method 2	Sort + Manual triple loop	$O(n\log n+U{m}^3)$	$O(U{m}^3)$

Method 1

Key

• Use set(combinations(sites, 3)) per user
• the set prevents counting the same pattern twice for one user. Sort by timestamp first so combinations are in the correct order.

Approach

1. Sort all events by timestamp, then group websites by user
2. For each user, generate all unique 3-sequences using combinations wrapped in a set
3. Count how many users have each pattern
4. Return the pattern with the highest count — lexicographically smallest on tie

Complexity

• Time Complexity: $O(n\log n+U\cdot m^3)$
  • $n$ visits to sort
  • $U$ users each with up to $m$ visits
• Space Complexity: $O(U\cdot m^3)$ — storing all patterns

Code

from collections import defaultdict
from itertools import combinations
from typing import List
 
class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        # Step 1: group visits by user, sorted by timestamp
        visits = defaultdict(list)
        for t, u, w in sorted(zip(timestamp, username, website)):
            visits[u].append(w)
 
        # Step 2: count each 3-sequence across users
        # set() ensures same pattern counted once per user even if visited multiple times
        pattern_count = defaultdict(int)
        for sites in visits.values():
            for pattern in set(combinations(sites, 3)):
                pattern_count[pattern] += 1
 
        # Step 3: highest count, lexicographically smallest on tie
        # sort key: (-count, pattern) → highest count first, lex smallest on tie
        ranked = sorted(pattern_count, key=lambda p: (-pattern_count[p], p))
        return list(ranked[0])

Method 2 - Sort + Manual triple loop

Key

Same logic as Method 1 but replaces itertools.combinations with explicit triple nested loops i < j < k. The set still deduplicates patterns per user. Identical complexity — just more verbose and easier to trace manually.

Approach

1. Sort events by timestamp, group by user
2. For each user, iterate all index triples (i, j, k) where i < j < k to build 3-sequences
3. Use a set per user to deduplicate, then increment pattern_count
4. Sort by (-count, pattern) and return the first

Complexity

• Time Complexity: $O(n\log n+U\cdot m^3)$ — same as Method 1
• Space Complexity: $O(U\cdot m^3)$

Code

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        combine = sorted(zip(timestamp, username, website))
        visited = defaultdict(list)
        for t, u, web in combine:
            visited[u].append(web)
 
        pattern_count = defaultdict(int)
        for web in visited.values(): # e.g. ['home', 'about', 'career']
            n = len(web)
            seen = set()
            for i in range(n):
                for j in range(i + 1, n):
                    for k in range(j + 1, n):
                        seen.add((web[i], web[j], web[k]))
 
            for path in seen:
                pattern_count[path] += 1
 
        res = sorted(pattern_count.keys(), key=lambda x: (-pattern_count[x], x))[0]
        return list(res)

---

Mistake