1152.Analyze_User_Website_Visit_Pattern(Medium).md

1152. Analyze User Website Visit Pattern (Medium)

Date and Time: Apr 17, 2025

Link: https://leetcode.com/problems/analyze-user-website-visit-pattern

Question:

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

• For example, ["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.

The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

• For example, if the pattern is ["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.

• Similarly, if the pattern is ["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.

• Also, if the pattern is ["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.

Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Note that the websites in a pattern do not need to be visited contiguously, they only need to be visited in the order they appeared in the pattern.

Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation:

The tuples in this example are:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
The pattern ("home", "about", "career") has score 2 (joe and mary).
The pattern ("home", "cart", "maps") has score 1 (james).
The pattern ("home", "cart", "home") has score 1 (james).
The pattern ("home", "maps", "home") has score 1 (james).
The pattern ("cart", "maps", "home") has score 1 (james).
The pattern ("home", "home", "home") has score 0 (no user visited home 3 times).

Example 2:

Input: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
Output: ["a","b","a"]

Example 3:

Input: username = ["dowg","dowg","dowg"], timestamp = [158931262,562600350,148438945], website = ["y","loedo","y"]
Output: ["y","y","loedo"]

Constraints:

• 3 <= username.length <= 50

• 1 <= username[i].length <= 10

• timestamp.length == username.length

• 1 <= timestamp[i] <= 10^9

• website.length == username.length

• 1 <= website[i].length <= 10

• username[i] and website[i] consist of lowercase English letters.

• It is guaranteed that there is at least one user who visited at least three websites.

• All the tuples [username[i], timestamp[i], website[i]] are unique.

Walk-through:

1. Zip (timestamp, username, webstie) together, and sort the zipped logs by timestamp. Because timestamp is not sorted, we have to make sure each website follow the ascending timestamp to form pattern.

2. Loop over logs and associate each site with the user, we will have user_sites dictionary, where we save all the websites that a user has.

3. Loop over user_sites to form combination from each user's website list, associate the pattern we form with the user in pattern_user dictionary. Remember to add user to set() instead of list[] to avoid duplicate users.

4. Loop over pattern_user to check how many users we have for each pattern by comparing the length of users, if they have the same length, we update pattern if the current one is lexicographically smaller than the previous pattern.

Python Solution:

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        # Zip (timestamp, username, website), sort by timestamp, O(n)
        # Loop over zipped logs, save each website with the user
        # Form combination from each user's sites to form combination
        # Use pattern_user dictionary to map each pattern with user
        # Find patterns, know how many users for each pattern
        # If a new pattern has more users, we update. Or, a new pattern has same number of users update the smaller lexicographical one

        # TC: O(n), n=len(username), SC: O(n)
        logs = sorted(zip(timestamp, username, website))

        # user_sites {user: [websites]}
        user_sites = collections.defaultdict(list)
        for _, user, site in logs:
            user_sites[user].append(site)

        # pattern_user {pattern: set(users)}
        pattern_users = collections.defaultdict(set)
        for user, sites in user_sites.items():
            patterns = set(combinations(sites, 3))
            # Associate each pattern with user
            for pat in patterns:
                pattern_users[pat].add(user)
        
        # Find the max score pattern
        score, pattern = 0, None
        for pat, users in pattern_users.items():
            # when pattern has more users or same len but smaller letter
            if len(users) > score or (len(users) == score and pat < pattern):
                score = len(users)
                pattern = pat
        return pattern

Time Complexity: $O(n)$
Space Complexity: $O(n)$