Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
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"]

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.

Solution

Method 1 - Brute Force with Hash Map

Intuition: We want to find the 3-website pattern visited in order by the largest number of users. For each user, we can generate all possible 3-sequences of their website visits, then count how many users have each pattern.

Approach:

  1. Combine the input arrays into a list of (username, timestamp, website) tuples and sort by timestamp.
  2. For each user, collect their website visit order.
  3. For each user, generate all unique 3-sequences (patterns) from their visit order.
  4. Use a map to count how many unique users have each pattern.
  5. Return the lexicographically smallest pattern with the highest user count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from collections import defaultdict
from itertools import combinations

class Solution:
    def mostVisitedPattern(self, username, timestamp, website):
        # Step 1: Sort the visits by timestamp
        data = sorted(zip(timestamp, username, website))
        # Step 2: Build user -> list of websites in order
        user_web = defaultdict(list)
        for _, user, web in data:
            user_web[user].append(web)
        # Step 3: For each user, get all unique 3-sequences
        pattern_users = defaultdict(set)
        for user, webs in user_web.items():
            patterns = set(combinations(webs, 3))
            for pat in patterns:
                pattern_users[pat].add(user)
        # Step 4: Find the pattern with max users, lex smallest
        max_count = 0
        answer = tuple()
        for pat, users in pattern_users.items():
            if len(users) > max_count or (len(users) == max_count and pat < answer):
                max_count = len(users)
                answer = pat
        return list(answer)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.*;
class Solution {
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        int n = username.length;
        List<int[]> visits = new ArrayList<>();
        for (int i = 0; i < n; ++i) visits.add(new int[]{timestamp[i], i});
        visits.sort(Comparator.comparingInt(a -> a[0]));
        Map<String, List<String>> userWeb = new HashMap<>();
        for (int[] v : visits) {
            String user = username[v[1]];
            String web = website[v[1]];
            userWeb.computeIfAbsent(user, k -> new ArrayList<>()).add(web);
        }
        Map<String, Set<String>> patternUsers = new HashMap<>();
        for (String user : userWeb.keySet()) {
            List<String> webs = userWeb.get(user);
            Set<String> patterns = new HashSet<>();
            int m = webs.size();
            for (int i = 0; i < m; ++i)
                for (int j = i+1; j < m; ++j)
                    for (int k = j+1; k < m; ++k)
                        patterns.add(webs.get(i) + "," + webs.get(j) + "," + webs.get(k));
            for (String pat : patterns)
                patternUsers.computeIfAbsent(pat, x -> new HashSet<>()).add(user);
        }
        int max = 0;
        String res = "";
        for (String pat : patternUsers.keySet()) {
            int cnt = patternUsers.get(pat).size();
            if (cnt > max || (cnt == max && pat.compareTo(res) < 0)) {
                max = cnt;
                res = pat;
            }
        }
        return Arrays.asList(res.split(","));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
        int n = username.size();
        vector<tuple<int, string, string>> data;
        for (int i = 0; i < n; ++i)
            data.emplace_back(timestamp[i], username[i], website[i]);
        sort(data.begin(), data.end());
        map<string, vector<string>> userWeb;
        for (auto& [t, u, w] : data)
            userWeb[u].push_back(w);
        map<vector<string>, set<string>> patternUsers;
        for (auto& [user, webs] : userWeb) {
            set<vector<string>> patterns;
            int m = webs.size();
            for (int i = 0; i < m; ++i)
                for (int j = i+1; j < m; ++j)
                    for (int k = j+1; k < m; ++k)
                        patterns.insert({webs[i], webs[j], webs[k]});
            for (auto& pat : patterns)
                patternUsers[pat].insert(user);
        }
        int maxc = 0;
        vector<string> ans;
        for (auto& [pat, users] : patternUsers) {
            if ((int)users.size() > maxc || ((int)users.size() == maxc && pat < ans)) {
                maxc = users.size();
                ans = pat;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import (
    "sort"
)
func mostVisitedPattern(username []string, timestamp []int, website []string) []string {
    n := len(username)
    type visit struct{ t int; u, w string }
    data := make([]visit, n)
    for i := 0; i < n; i++ {
        data[i] = visit{timestamp[i], username[i], website[i]}
    }
    sort.Slice(data, func(i, j int) bool { return data[i].t < data[j].t })
    userWeb := map[string][]string{}
    for _, v := range data {
        userWeb[v.u] = append(userWeb[v.u], v.w)
    }
    patternUsers := map[[3]string]map[string]struct{}{}
    for user, webs := range userWeb {
        m := len(webs)
        patterns := map[[3]string]struct{}{}
        for i := 0; i < m; i++ {
            for j := i+1; j < m; j++ {
                for k := j+1; k < m; k++ {
                    pat := [3]string{webs[i], webs[j], webs[k]}
                    patterns[pat] = struct{}{}
                }
            }
        }
        for pat := range patterns {
            if patternUsers[pat] == nil {
                patternUsers[pat] = map[string]struct{}{}
            }
            patternUsers[pat][user] = struct{}{}
        }
    }
    maxc := 0
    var ans [3]string
    for pat, users := range patternUsers {
        if len(users) > maxc || (len(users) == maxc && less(pat, ans)) {
            maxc = len(users)
            ans = pat
        }
    }
    return []string{ans[0], ans[1], ans[2]}
}
func less(a, b [3]string) bool {
    for i := 0; i < 3; i++ {
        if a[i] < b[i] { return true }
        if a[i] > b[i] { return false }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun mostVisitedPattern(username: Array<String>, timestamp: IntArray, website: Array<String>): List<String> {
        val n = username.size
        val data = (0 until n).map { Triple(timestamp[it], username[it], website[it]) }.sortedBy { it.first }
        val userWeb = mutableMapOf<String, MutableList<String>>()
        for ((_, user, web) in data) userWeb.getOrPut(user) { mutableListOf() }.add(web)
        val patternUsers = mutableMapOf<List<String>, MutableSet<String>>()
        for ((user, webs) in userWeb) {
            val patterns = mutableSetOf<List<String>>()
            for (i in 0 until webs.size)
                for (j in i+1 until webs.size)
                    for (k in j+1 until webs.size)
                        patterns.add(listOf(webs[i], webs[j], webs[k]))
            for (pat in patterns) patternUsers.getOrPut(pat) { mutableSetOf() }.add(user)
        }
        var maxc = 0
        var ans = listOf<String>()
        for ((pat, users) in patternUsers) {
            if (users.size > maxc || (users.size == maxc && (ans.isEmpty() || pat < ans))) {
                maxc = users.size
                ans = pat
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

use std::collections::{HashMap, HashSet};
pub struct Solution;
impl Solution {
    pub fn most_visited_pattern(username: Vec<String>, timestamp: Vec<i32>, website: Vec<String>) -> Vec<String> {
        let mut data: Vec<(i32, &String, &String)> = (0..username.len())
            .map(|i| (timestamp[i], &username[i], &website[i]))
            .collect();
        data.sort();
        let mut user_web: HashMap<&String, Vec<&String>> = HashMap::new();
        for (_, user, web) in &data {
            user_web.entry(user).or_default().push(web);
        }
        let mut pattern_users: HashMap<[&String; 3], HashSet<&String>> = HashMap::new();
        for (user, webs) in &user_web {
            let m = webs.len();
            let mut patterns = HashSet::new();
            for i in 0..m {
                for j in i+1..m {
                    for k in j+1..m {
                        patterns.insert([webs[i], webs[j], webs[k]]);
                    }
                }
            }
            for pat in patterns {
                pattern_users.entry(pat).or_default().insert(user);
            }
        }
        let mut maxc = 0;
        let mut ans: Option<[&String; 3]> = None;
        for (pat, users) in pattern_users {
            if users.len() > maxc || (users.len() == maxc && (ans.is_none() || pat < ans.unwrap())) {
                maxc = users.len();
                ans = Some(pat);
            }
        }
        ans.unwrap().iter().map(|s| (*s).clone()).collect()
    }
}

Complexity

  • ⏰ Time complexity: O(U * W^3), where U is the number of users and W is the max number of websites visited by a user (since we generate all 3-sequences per user).
  • 🧺 Space complexity: O(P + N), where P is the number of unique patterns and N is the input size.