Analyze User Website Visit Pattern - Leetcode Solution

Problem Statement:

The problem statement can be found on the Leetcode website at the following link: https://leetcode.com/problems/analyze-user-website-visit-pattern/

You are given three arrays username, timestamp, and website of the same length N where the ith tuple means that the user with name username[i] visited the website website[i] at time timestamp[i].

A three-sequence is a list of not necessarily different websites of length 3 sorted in ascending order by the time of their visits.

Find the 3-sequence visited at least once by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.

Solution:

Approach:

We will start with creating a list that contains browsing history for each user. We will use a dictionary for this purpose, where the key will be the name of the user, and the value will be a list containing the websites visited by the user.

Next, we will create a dictionary that contains all possible 3-sequences visited by each user. We will iterate over the browsing history of each user, create all possible 3-sequences and add them to the dictionary. The key will be the 3-sequence, and the value will be a set of users who visited this sequence.

Finally, we will iterate over the dictionary containing all the 3-sequences and count the number of users who visited each 3-sequence. We will also keep track of the 3-sequence that has been visited by the largest number of users.

At the end of our computation, we will return the lexicographically smallest 3-sequence that has been visited by the largest number of users.

Algorithm:

1. Create a dictionary (user_history) that contains browsing history for each user.
2. Create a dictionary (user_sequences) that contains all possible 3-sequences visited by each user.
3. Iterate over the browsing history of each user, create all possible 3-sequences and add them to the dictionary user_sequences.
4. Iterate over the dictionary user_sequences, count the number of users who visited each 3-sequence and keep track of the 3-sequence that has been visited by the largest number of users.
5. Return the lexicographically smallest 3-sequence that has been visited by the largest number of users.

Code:

The Python code for the mentioned algorithm is as follows:

from collections import defaultdict
import itertools

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        
        # Step 1: Create a dictionary (user_history) that contains browsing history for each user.
        user_history = defaultdict(list)
        for i in range(len(username)):
            user_history[username[i]].append((timestamp[i], website[i]))

        # Step 2: Create a dictionary (user_sequences) that contains all possible 3-sequences visited by each user.
        user_sequences = defaultdict(set)
        for user in user_history.keys():
            sites = user_history[user]
            for seq in itertools.combinations(sites, 3):
                user_sequences[seq].add(user)

        # Step 3: Iterate over the dictionary user_sequences, count the number of users who visited each 3-sequence and keep track of the 3-sequence that has been visited by the largest number of users.
        max_count = 0
        max_seq = None
        freq = defaultdict(int)
        for seq in user_sequences.keys():
            count = len(user_sequences[seq])
            freq[seq] = count
            if count > max_count:
                max_count = count
                max_seq = seq
            elif count == max_count:
                if seq < max_seq:
                    max_seq = seq

        # Step 5: Return the lexicographically smallest 3-sequence that has been visited by the largest number of users.
        return list(max_seq)

Time Complexity:

The time complexity of this algorithm is O(N^3), where N is the length of the input arrays. This is because we need to iterate over all the possible 3-sequences for each user, which gives us a complexity of O(N^3).

Space Complexity:

The space complexity of this algorithm is O(N^2). We are using two dictionaries to store the browsing history and 3-sequences, respectively, for each user. The size of the 3-sequences dictionary is also O(N^2) because the maximum number of 3-sequences possible is N choose 3.

1