Analyze User Website Visit Pattern

Medium · Arrays & Hashing · Explanation and code example

Hash Map

How it works

We need to find the most common 3-website pattern visited by users in sequential order. The key insight is that we should group each user's website visits in chronological order, then generate all possible 3-site combinations for each user. By counting how many distinct users visit each pattern, we can find the most popular one.

Since we want patterns across different users (not repeated visits by the same user), we use a set for each user's patterns before counting. This ensures each user contributes at most once to each pattern's count.

Steps

  1. Sort all visits by timestamp to ensure chronological order.
  2. Group websites by user, maintaining the order of visits.
  3. For each user, generate all possible 3-website patterns using three nested loops i, j, k. Store patterns in a set to avoid counting duplicates from the same user.
  4. Count how many users have each pattern.
  5. Return the pattern with the highest count, breaking ties lexicographically.

Complexity

  • Time complexity: O(n log n + n * u + n ^ 3 * w)
  • Space complexity: O(n * u + n ^ 3 * w)

Where n is the size of the array timestamp, u is the maximum length of any string in the array username, and w is the maximum length of any string in the array website.

Things to watch for

Counting Duplicate Patterns From the Same User

When a user visits enough websites to generate the same 3-site pattern multiple times, you should only count that pattern once per user. Failing to use a set for each user's patterns will inflate the count incorrectly.

Not Sorting Visits by Timestamp Before Grouping

The pattern must follow chronological order of visits. If you group websites by user without first sorting by timestamp, the patterns will be in arbitrary order and produce wrong results.

Incorrect Lexicographic Comparison for Tie-Breaking

When multiple patterns have the same count, you must return the lexicographically smallest one. Comparing concatenated strings with a separator may not give correct lexicographic ordering of the tuple components.

Python code example

from typing import List
from collections import defaultdict

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        arr = list(zip(timestamp, username, website))
        arr.sort()

        mp = defaultdict(list)
        for time, user, site in arr:
            mp[user].append(site)

        count = defaultdict(int)
        for user in mp:
            patterns = set()
            cur = mp[user]
            for i in range(len(cur)):
                for j in range(i + 1, len(cur)):
                    for k in range(j + 1, len(cur)):
                        patterns.add((cur[i], cur[j], cur[k]))
            for p in patterns:
                count[p] += 1

        max_count = 0
        res = tuple()
        for pattern in count:
            if count[pattern] > max_count or (count[pattern] == max_count and pattern < res):
                max_count = count[pattern]
                res = pattern

        return list(res)

C++ code example

class Solution {
public:
    vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
        int n = timestamp.size();
        vector<pair<int,int>> arr;
        for (int i = 0; i < n; ++i) arr.push_back({timestamp[i], i});
        sort(arr.begin(), arr.end(),
             [](auto& a, auto& b){ return a.first < b.first; });

        unordered_map<string, vector<string>> mp;
        for (auto& p : arr) mp[username[p.second]].push_back(website[p.second]);

        unordered_map<string,int> count;
        for (auto& kv : mp) {
            auto& cur = kv.second;
            unordered_set<string> patterns;
            for (int i = 0; i < (int)cur.size(); ++i)
                for (int j = i + 1; j < (int)cur.size(); ++j)
                    for (int k = j + 1; k < (int)cur.size(); ++k)
                        patterns.insert(cur[i] + "#" + cur[j] + "#" + cur[k]);
            for (auto& p : patterns) ++count[p];
        }

        int maxCnt = 0;
        string res;
        for (auto& kv : count)
            if (kv.second > maxCnt ||
               (kv.second == maxCnt && (res.empty() || kv.first < res))) {
                maxCnt = kv.second;
                res = kv.first;
            }

        vector<string> ans;
        string tmp;
        for (char ch : res) {
            if (ch == '#') {
                ans.push_back(tmp);
                tmp.clear();
            } else {
                tmp += ch;
            }
        }
        ans.push_back(tmp);
        return ans;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations