Analyze User Website Visit Pattern

medium hash map sorting subsequence

Problem

You are given parallel arrays username, timestamp, and website describing one visit each. A "pattern" is an ordered sequence of exactly three websites. For each user, sort their visits by timestamp and take every 3-website subsequence (in time order). Count, across users, how many distinct users exhibit each pattern. Return the pattern visited by the most users; if several tie, return the lexicographically smallest one.

Input

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

Output["home","about","career"]

Pattern ("home","about","career") is shared by joe (and is the only candidate seen by a user), making it the most-visited pattern.

username (comma-separated)

timestamp (comma-separated)

website (comma-separated)

from collections import defaultdict
from itertools import combinations

def most_visited_pattern(username, timestamp, website):
    visits = defaultdict(list)
    for u, t, w in sorted(zip(username, timestamp, website), key=lambda x: x[1]):
        visits[u].append(w)
    count = defaultdict(int)
    for sites in visits.values():
        for pat in set(combinations(sites, 3)):
            count[pat] += 1
    return list(max(count, key=lambda p: (count[p], [-ord(c) for c in "".join(p)])))

function mostVisitedPattern(username, timestamp, website) {
  const idx = [...username.keys()].sort((a, b) => timestamp[a] - timestamp[b]);
  const visits = new Map();
  for (const i of idx) {
    if (!visits.has(username[i])) visits.set(username[i], []);
    visits.get(username[i]).push(website[i]);
  }
  const count = new Map();
  for (const sites of visits.values()) {
    const seen = new Set();
    for (let a = 0; a < sites.length; a++)
      for (let b = a + 1; b < sites.length; b++)
        for (let c = b + 1; c < sites.length; c++) {
          const key = sites[a] + "#" + sites[b] + "#" + sites[c];
          if (seen.has(key)) continue;
          seen.add(key);
          count.set(key, (count.get(key) || 0) + 1);
        }
  }
  let best = null;
  for (const [key, cnt] of count)
    if (best === null || cnt > count.get(best) ||
        (cnt === count.get(best) && key < best)) best = key;
  return best.split("#");
}

class Solution {
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        Integer[] idx = new Integer[username.length];
        for (int i = 0; i < idx.length; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> timestamp[a] - timestamp[b]);
        Map<String, List<String>> visits = new HashMap<>();
        for (int i : idx)
            visits.computeIfAbsent(username[i], k -> new ArrayList<>()).add(website[i]);
        Map<String, Integer> count = new HashMap<>();
        String best = null;
        for (List<String> s : visits.values()) {
            Set<String> seen = new HashSet<>();
            for (int a = 0; a < s.size(); a++)
              for (int b = a + 1; b < s.size(); b++)
                for (int c = b + 1; c < s.size(); c++) {
                    String key = s.get(a) + "#" + s.get(b) + "#" + s.get(c);
                    if (!seen.add(key)) continue;
                    count.merge(key, 1, Integer::sum);
                    if (best == null || count.get(key) > count.get(best)
                        || (count.get(key).equals(count.get(best)) && key.compareTo(best) < 0))
                        best = key;
                }
        }
        return Arrays.asList(best.split("#"));
    }
}

vector<string> mostVisitedPattern(vector<string>& username,
                                   vector<int>& timestamp, vector<string>& website) {
    vector<int> idx(username.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){ return timestamp[a] < timestamp[b]; });
    unordered_map<string, vector<string>> visits;
    for (int i : idx) visits[username[i]].push_back(website[i]);
    map<string, int> count;
    for (auto& [u, s] : visits) {
        set<string> seen;
        for (size_t a = 0; a < s.size(); a++)
          for (size_t b = a + 1; b < s.size(); b++)
            for (size_t c = b + 1; c < s.size(); c++) {
                string key = s[a] + "#" + s[b] + "#" + s[c];
                if (!seen.insert(key).second) continue;
                count[key]++;
            }
    }
    string best;
    int bc = -1;
    for (auto& [k, v] : count) if (v > bc) { bc = v; best = k; }
    vector<string> res; string cur;
    for (char ch : best) { if (ch == '#') { res.push_back(cur); cur.clear(); } else cur += ch; }
    res.push_back(cur);
    return res;
}

Explanation

We need the 3-website pattern (an ordered triple) shared by the most distinct users, with ties broken by the lexicographically smallest pattern. The plan: group each user's visits in time order, enumerate every 3-site subsequence per user, and tally with a hash map.

First we sort all visits by timestamp and append each website into a list per username, so every user's sites are in chronological order.

For each user we generate all (a, b, c) subsequences with a < b < c by index. Crucially we use a per-user set so a pattern is counted once per user even if it can be formed multiple ways — we are counting users, not occurrences.

We bump count[pattern] and track the best as we go: a pattern wins if its count is higher, or equal but it sorts smaller as a string. The keys join the three sites with "#" so string comparison gives lexicographic order.

Example: with joe visiting home, about, career, his only triple is ("home","about","career"); no other pattern is shared by more users, so that triple is the answer.

Time: O(U · k³ + P log P) Space: O(P)