## Similar Problems

Similar Problems not available

# Analyze User Website Visit Pattern - Leetcode Solution

## Companies:

LeetCode: Analyze User Website Visit Pattern Leetcode Solution

Difficulty: Medium

Topics: hash-table sorting array

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:

- Create a dictionary (user_history) that contains browsing history for each user.
- Create a dictionary (user_sequences) that contains all possible 3-sequences visited by each user.
- Iterate over the browsing history of each user, create all possible 3-sequences and add them to the dictionary user_sequences.
- 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.
- 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.

## Analyze User Website Visit Pattern Solution Code

`1`