Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1152.html

1152. Analyze User Website Visit Pattern

Level

Medium

Description

We are given some website visits: the user with name username[i] visited the website website[i] at time timestamp[i].

A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits. (The websites in a 3-sequence are not necessarily distinct.)

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

Example 1:

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", 1, "home"]
["joe", 2, "about"]
["joe", 3, "career"]
["james", 4, "home"]
["james", 5, "cart"]
["james", 6, "maps"]
["james", 7, "home"]
["mary", 8, "home"]
["mary", 9, "about"]
["mary", 10, "career"]
The 3-sequence ("home", "about", "career") was visited at least once by 2 users.
The 3-sequence ("home", "cart", "maps") was visited at least once by 1 user.
The 3-sequence ("home", "cart", "home") was visited at least once by 1 user.
The 3-sequence ("home", "maps", "home") was visited at least once by 1 user.
The 3-sequence ("cart", "maps", "home") was visited at least once by 1 user.

Note:

  1. 3 <= N = username.length = timestamp.length = website.length <= 50
  2. 1 <= username[i].length <= 10
  3. 0 <= timestamp[i] <= 10^9
  4. 1 <= website[i].length <= 10
  5. Both username[i] and website[i] contain only lowercase characters.
  6. It is guaranteed that there is at least one user who visited at least 3 websites.
  7. No user visits two websites at the same time.

Solution

Create a class Struct. Each object of type Struct contains a username, a timestamp and a website. The objects of type Struct are comparable using timestamp. Create an array of type Struct to store all the elements created from the three input arrays. Then sort the array of type Struct in ascending order.

Loop over the array of type Struct and obtain all the websites visited by each user in ascending order. For each user, obtain the websites and generate all possible 3-sequences, and update the counts of each 3-sequence. Note that since the target is to find the 3-sequence visited by the largest number of users, for each user, a 3-sequence can be counted at most once. After all users’ 3-sequences are visited, obtain the 3-sequence with the maximum count and is the lexicographically smallest, and return the 3-sequence.

  • class Solution {
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        int length = username.length;
        Struct[] array = new Struct[length];
        for (int i = 0; i < length; i++)
            array[i] = new Struct(username[i], timestamp[i], website[i]);
        Arrays.sort(array);
        Map<String, List<String>> userVisitsMap = new HashMap<String, List<String>>();
        for (int i = 0; i < length; i++) {
            Struct struct = array[i];
            String curUser = struct.username;
            String curWebsite = struct.website;
            List<String> list = userVisitsMap.getOrDefault(curUser, new ArrayList<String>());
            list.add(curWebsite);
            userVisitsMap.put(curUser, list);
        }
        int maxCount = 0;
        Map<String, Integer> countMap = new HashMap<String, Integer>();
        Map<String, List<String>> strListMap = new HashMap<String, List<String>>();
        Set<String> set = userVisitsMap.keySet();
        for (String user : set) {
            Set<String> sequenceSet = new HashSet<String>();
            List<String> list = userVisitsMap.getOrDefault(user, new ArrayList<String>());
            int size = list.size();
            if (size >= 3) {
                for (int i = 0; i < size - 2; i++) {
                    String website1 = list.get(i);
                    for (int j = i + 1; j < size - 1; j++) {
                        String website2 = list.get(j);
                        for (int k = j + 1; k < size; k++) {
                            String website3 = list.get(k);
                            List<String> sequence = new ArrayList<String>();
                            sequence.add(website1);
                            sequence.add(website2);
                            sequence.add(website3);
                            String sequenceStr = sequence.toString();
                            if (sequenceSet.add(sequenceStr)) {
                                int count = countMap.getOrDefault(sequenceStr, 0) + 1;
                                maxCount = Math.max(maxCount, count);
                                countMap.put(sequenceStr, count);
                                strListMap.put(sequenceStr, sequence);
                            }
                        }
                    }
                }
            }
        }
        List<List<String>> candidates = new ArrayList<List<String>>();
        Set<String> sequenceSet = countMap.keySet();
        for (String sequenceStr : sequenceSet) {
            int count = countMap.getOrDefault(sequenceStr, 0);
            if (count == maxCount)
                candidates.add(strListMap.get(sequenceStr));
        }
        Collections.sort(candidates, new Comparator<List<String>>() {
            public int compare(List<String> sequence1, List<String> sequence2) {
                return sequence1.toString().compareTo(sequence2.toString());
            }
        });
        return candidates.get(0);
    }
}

class Struct implements Comparable<Struct> {
    String username;
    int timestamp;
    String website;

    public Struct(String username, int timestamp, String website) {
        this.username = username;
        this.timestamp = timestamp;
        this.website = website;
    }

    public int compareTo(Struct struct2) {
        if (this.timestamp != struct2.timestamp)
            return this.timestamp - struct2.timestamp;
        else
            return this.username.compareTo(struct2.username);
    }
}

  • class Solution:
    def mostVisitedPattern(
        self, username: List[str], timestamp: List[int], website: List[str]
    ) -> List[str]:
        d = defaultdict(list)
        for user, _, site in sorted(
            zip(username, timestamp, website), key=lambda x: x[1]
        ):
            d[user].append(site)

        cnt = Counter()
        for sites in d.values():
            m = len(sites)
            s = set()
            if m > 2:
                for i in range(m - 2):
                    for j in range(i + 1, m - 1):
                        for k in range(j + 1, m):
                            s.add((sites[i], sites[j], sites[k]))
            for t in s:
                cnt[t] += 1
        return sorted(cnt.items(), key=lambda x: (-x[1], x[0]))[0][0]



  • class Solution {
public:
    vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
        unordered_map<string, vector<pair<int, string>>> d;
        int n = username.size();
        for (int i = 0; i < n; ++i) {
            auto user = username[i];
            int ts = timestamp[i];
            auto site = website[i];
            d[user].emplace_back(ts, site);
        }
        unordered_map<string, int> cnt;
        for (auto& [_, sites] : d) {
            int m = sites.size();
            unordered_set<string> s;
            if (m > 2) {
                sort(sites.begin(), sites.end());
                for (int i = 0; i < m - 2; ++i) {
                    for (int j = i + 1; j < m - 1; ++j) {
                        for (int k = j + 1; k < m; ++k) {
                            s.insert(sites[i].second + "," + sites[j].second + "," + sites[k].second);
                        }
                    }
                }
            }
            for (auto& t : s) {
                cnt[t]++;
            }
        }
        int mx = 0;
        string t;
        for (auto& [p, v] : cnt) {
            if (mx < v || (mx == v && t > p)) {
                mx = v;
                t = p;
            }
        }
        return split(t, ',');
    }

    vector<string> split(string& s, char c) {
        vector<string> res;
        stringstream ss(s);
        string t;
        while (getline(ss, t, c)) {
            res.push_back(t);
        }
        return res;
    }
};

  • func mostVisitedPattern(username []string, timestamp []int, website []string) []string {
	d := map[string][]pair{}
	for i, user := range username {
		ts := timestamp[i]
		site := website[i]
		d[user] = append(d[user], pair{ts, site})
	}
	cnt := map[string]int{}
	for _, sites := range d {
		m := len(sites)
		s := map[string]bool{}
		if m > 2 {
			sort.Slice(sites, func(i, j int) bool { return sites[i].ts < sites[j].ts })
			for i := 0; i < m-2; i++ {
				for j := i + 1; j < m-1; j++ {
					for k := j + 1; k < m; k++ {
						s[sites[i].site+","+sites[j].site+","+sites[k].site] = true
					}
				}
			}
		}
		for t := range s {
			cnt[t]++
		}
	}
	mx, t := 0, ""
	for p, v := range cnt {
		if mx < v || (mx == v && p < t) {
			mx = v
			t = p
		}
	}
	return strings.Split(t, ",")
}

type pair struct {
	ts   int
	site string
}

All Problems

All Solutions