LeetCode Solutions Blog

Analyze User Website Visit Pattern

Number: 1108

Difficulty: Medium

Paid? Yes

Problem Description

Given three arrays—username, timestamp, and website—each index represents a user visiting a website at a particular time. Our goal is to determine the 3-sequence of websites (a pattern) that is visited by the largest number of unique users in the order they visited them. If there is a tie, return the lexicographically smallest pattern.

Key Insights

Combine the inputs into a single list of events and sort them by timestamp.
Group the visits by each user, preserving the sorted order.
Generate all unique combinations of 3-sequences for each user (order matters and non-contiguous visits are allowed).
Use a dictionary (or hash map) to map each 3-sequence pattern to the set of users who visited that pattern.
The problem constraints are small, so generating combinations per user (even using triple nested loops) is acceptable.
When multiple patterns have the same frequency, choose the lexicographically smallest one.

Space and Time Complexity

Time Complexity: O(U * L^3) where U is the number of users and L is the maximum length of visits per user (since we generate combinations of 3 visits per user). Sorting all events costs O(N log N) for N total events. Space Complexity: O(P) where P is the number of unique 3-sequence patterns stored in the dictionary, plus O(N) for grouping the events.

Solution

Aggregate the events by user while sorting them based on timestamp.
For each user, generate all sets of 3-website patterns (to avoid duplicate patterns per user).
Use a hash map to count the number of unique users for each pattern.
Traverse the map to find the pattern with the highest count. In case of a tie, compare patterns lexicographically.
Return the pattern that meets the criteria.

Code Solutions

# Python code solution for Analyze User Website Visit Pattern

from collections import defaultdict
from itertools import combinations

def mostVisitedPattern(username, timestamp, website):
    # Combine the logs into a list of tuples and sort by timestamp.
    logs = sorted(zip(timestamp, username, website))
    
    # Dictionary to hold each user's list of website visits
    user_visits = defaultdict(list)
    for time, user, site in logs:
        user_visits[user].append(site)
    
    # Dictionary to map a pattern (tuple of 3 websites) to set of users who visited that pattern
    pattern_users = defaultdict(set)
    
    # For each user, generate all unique 3-sequences from their visit list and update pattern_users
    for user, sites in user_visits.items():
        # Use set to avoid counting duplicate patterns from the same user multiple times
        seen_patterns = set()
        if len(sites) < 3:
            continue
        # Generate all 3-sequence combinations (order matters since visits are in time order)
        for pattern in combinations(sites, 3):
            if pattern not in seen_patterns:
                seen_patterns.add(pattern)
                pattern_users[pattern].add(user)
    
    # Find the pattern with the highest score (i.e., most users)
    # In case of a tie, lexicographically smallest pattern wins.
    max_count = 0
    result = None
    for pattern, users in pattern_users.items():
        count = len(users)
        if count > max_count or (count == max_count and (result is None or pattern < result)):
            max_count = count
            result = pattern
            
    return list(result)

# Example usage:
print(mostVisitedPattern(
    ["joe","joe","joe","james","james","james","james","mary","mary","mary"],
    [1,2,3,4,5,6,7,8,9,10],
    ["home","about","career","home","cart","maps","home","home","about","career"]
))