Domain 2MediumMEDIUM

Analyze User Website Visit Pattern

LeetCode problem 1152: Analyze User Website Visit Pattern (medium).

Domain: medium•Updated: 2026-09-09
#Array#Hash Table#Sort

Problem Breakdown

We need to identify a specific pattern of three website visits (a “3-sequence”) that is most popular across different users.

Inputs:

  • username: List of strings identifying who visited.
  • timestamp: List of integers indicating when each visit occurred.
  • website: List of strings for the URL/path visited at that time.

All three lists are aligned by index ii, meaning (username[i], timestamp[i], website[i]) is a single event.

Output: A list containing exactly 3 websites [w1, w2, w3]. This sequence must be valid (chronologically ordered) and visited by the maximum number of distinct users. If multiple sequences share that max count, return the one that comes first alphabetically (lexicographically smallest).

Implicit Constraints & Edge Cases:

  • User Isolation: A 3-sequence is only counted if all three visits belong to the same user. Visits from different users at similar times do not combine into a single sequence for counting purposes.
  • Chronology: For any triplet of websites chosen by a user, they must be ordered strictly by timestamp (t1<t2<t3t_1 < t_2 < t_3). Since timestamps are unique per visit (no two visits at same time), sorting the user’s history resolves this order automatically.
  • Small N: The total number of events N≤50N \le 50. This suggests we can afford combinatorial logic (O(N3)O(N^3)) without needing complex optimizations, but clarity is key for a senior engineer interview.
  • Guarantees: We are guaranteed at least one user visits ≥\ge 3 websites, so the result will never be undefined or empty regarding valid sequences.

Intuition

  1. Grouping by User: The core constraint is that a sequence must belong to a single user. If we treat all events as a flat stream, we lose ownership information. We need to partition the data into buckets per username.
  2. Ordering Visits: Within each bucket (user), visits might not be in chronological order relative to other users’ timestamps or even their own previous entries if input isn’t sorted globally by time for that user. However, since we only care about relative ordering within a user’s history, sorting the events of a specific user by timestamp is essential before extracting sequences.
  3. Generating Sequences: Once a user has kk visits in chronological order (sorted list), any combination of 3 distinct indices (i,j,k)(i, j, k) where 0≤i<j<k<size0 \le i < j < k < size forms a valid “3-sequence” because the timestamps are strictly increasing by definition.
  4. Counting and Selecting: We aggregate these sequences into a frequency map (e.g., Counter). Finally, we scan this map to find the maximum count. Python’s tuple comparison handles lexicographical ordering naturally when iterating or sorting keys with equal values.

Why Brute Force is Insufficient? A naive approach might try every triplet from the raw input arrays (O(N3)O(N^3)) and check if they belong to one user by checking username equality for all three indices. While technically O(N3)O(N^3), this misses the structural insight that we must group first. More importantly, without grouping, you cannot efficiently determine which users contributed to a specific sequence string combination because timestamps are not unique globally (though they might be in examples). Grouping ensures correctness and makes complexity analysis cleaner (∑(ki3)\sum \binom{k_i}{3} vs (N3)\binom{N}{3} where kik_i is visits per user).

Approach

  1. Data Structure Setup: Initialize a dictionary mapping username to a list of (timestamp, website) tuples.
  2. Grouping & Sorting: Iterate through the input arrays simultaneously (using zip). Populate the dictionary lists. For each user’s visit history, sort by timestamp ascendingly. This ensures that for any combination we pick later, the time order is respected implicitly.
  3. Sequence Extraction: Initialize a global counter (collections.Counter) to track frequency of website triplets. Iterate through every username in our dictionary:
    • Extract just the websites from their sorted history into a list (since timestamps are now ordered).
    • Generate all combinations of size 3 using indices i<j<ki < j < k.
    • Increment the counter for each resulting tuple (w[i], w[j], w[k]).
  4. Finding Result: Iterate through the items in our global counter. Track the maximum count seen so far (max_count). If a sequence has count > max_count, update result and reset tracking logic (or handle tie-breaking).
    • Optimization: Since we need lexicographically smallest on ties, it is often easier to sort all unique sequences found by frequency descending, then primary key ascending. Or simply iterate the counter items; if current count equals max_count but sequence < result_sequence, update.
  5. Return: Return the list of strings for the winning sequence.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N+K)O(N \log N + K) where NN is total visits and KK is number of unique valid sequences found (bounded by (N3)\binom{N}{3}).
    • Grouping takes O(N)O(N).
    • Sorting per user: In worst case one user has all NN, so O(Nlog⁡N)O(N \log N). If distributed, sum of sorts is bounded similarly.
    • Generating combinations: For a single user with kk visits, we generate (k3)\binom{k}{3} sequences. Summing over users, the total number of generated tuples across all inputs cannot exceed (N3)≈O(N3)\binom{N}{3} \approx O(N^3). With N=50N=50, this is roughly 20,000 operations, which is negligible.
    • Counter updates and final scan are linear with respect to unique sequences found (KK).
  • Space Complexity: O(K)O(K) where KK is the number of distinct website triplets encountered (stored in the counter) plus space for storing user visit lists. In worst case, this could be proportional to (N3)\binom{N}{3}.

Solution

from collections import defaultdict, Counter
import itertools

def mostVisitedPattern(username: list[str], timestamp: list[int], website: list[str]) -> list[str]:
    # 1. Group visits by username and store as (timestamp, website) tuples
    user_visits = defaultdict(list)
    
    for u_name, t_time, w_site in zip(username, timestamp, website):
        user_visits[u_name].append((t_time, w_site))
        
    # 2. Frequency map to count how many users visited each specific sequence
    pattern_counts = Counter()
    
    # 3. Process each user's history
    for visits in user_visits.values():
        if len(visits) < 3:
            continue
            
        # Sort by timestamp to ensure chronological order of websites
        visits.sort(key=lambda x: x[0])
        
        # Extract just the website names since they are now sorted chronologically
        sites = [w for _, w in visits]
        
        # Generate all combinations of 3 distinct indices (i < j < k)
        # Since we sorted by time, any combination forms a valid chronological sequence
        for triplet in itertools.combinations(sites, 3):
            pattern_counts[triplet] += 1
            
    # 4. Find the max count and handle lexicographical tie-breaking
    if not pattern_counts:
        return []

    best_sequence = None
    max_count = -1
    
    for sequence, count in pattern_counts.items():
        if count > max_count:
            max_count = count
            best_sequence = sequence
        elif count == max_count and (best_sequence is None or sequence < best_sequence):
            # Tie-breaker: lexicographically smallest
            best_sequence = sequence
            
    return list(best_sequence)

# Example usage matching the problem description logic implicitly handled above.

Edge Cases Handled

  • Users with fewer than 3 visits: The code checks if len(visits) < 3 and skips them, as they cannot form a valid triplet. This is safe because we only care about sequences formed by users who visited at least 3 times (guaranteed to exist).
  • Unsorted Input Timestamps per User: We explicitly sort each user’s visit list visits.sort(key=lambda x: x[0]) before generating combinations, ensuring the website order reflects time.
  • Lexicographical Ties: The logic inside the loop checks if a new sequence has an equal count to the current best but is lexicographically smaller (sequence < best_sequence). This ensures we return the correct tie-breaker result.
  • Empty Result (Theoretical): While constraints guarantee at least one valid user, the code handles if not pattern_counts just in case inputs were malformed or violated guarantees gracefully by returning an empty list.