1152. Analyze User Website Visit Pattern

https://leetcode.com/problems/analyze-user-website-visit-pattern/description/

Problem

You have given the website and user visits at the given time as below.

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

1. Pick any three websites (not necessarily distinct)
2. Find out the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.
3. This number is called the score for the pattern.
4. The goal is to return the pattern with the largest score.
5. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

For the above example, we can build the following tuples.

["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], 
["mary","career",10]

1. The pattern (“home”, “about”, “career”) has a score of 2 (joe and mary).
2. The pattern (“home”, “cart”, “maps”) has a score of 1 (james).
3. The pattern (“home”, “cart”, “home”) has a score of 1 (james).
4. The pattern (“home”, “maps”, “home”) has a score of 1 (james).
5. The pattern (“cart”, “maps”, “home”) has a score of 1 (james).
6. The pattern (“home”, “home”, “home”) has a score of 0 (no user visited home 3 times).

So answer is [“home”,”about”,”career”] .

Approach

Following are intuition

1. Every user visits websites and the websites for each user visit can form 3 — sequences.
2. Our goal is to find the most common 3-seq in those users.

Following is the approach to solve this.

1. We collect the time and website info according to every user.
2. n³ traverse all 3-seq in every user and use count map to record the 3-seq occurring times(remember to sort by time and avoid the same sequence in the same user)
3. Get the result

/**
 * @param {string[]} username
 * @param {number[]} timestamp
 * @param {string[]} website
 * @return {string[]}
 */
var mostVisitedPattern = function (username, timestamp, website) {
    const n = username.length;
    // Collect the website info for each user
    const userMap = new Map(); // <user, [web, time]
    for (let i = 0; i < n; i++) {
        const user = username[i];
        if (!userMap.has(user)) {
            userMap.set(user, []);
        }
        userMap.get(user).push([website[i], timestamp[i]]);
    }
    // Count map to record every 3 combination occuring time for the different user.
    const countMap = new Map(); // <pattern, count>
    let result = '';
    for (const user of userMap.keys()) {
        const visits = userMap.get(user);
        // Sort user visits based on time
        visits.sort((a, b) => a[1] - b[1]);
        // Bruteforce O(n^3) to find the pattern for each user
        const m = visits.length;
        const patternSet = new Set(); // <pattern>
        for (let i = 0; i < m; i++) {
            for (let j = i + 1; j < m; j++) {
                for (let k = j + 1; k < m; k++) {
                    const pattern = `${visits[i][0]} ${visits[j][0]} ${visits[k][0]}`;
                    if (!patternSet.has(pattern)) {
                        patternSet.add(pattern);
                        countMap.set(pattern, countMap.has(pattern) ? countMap.get(pattern) + 1 : 1);
                    }
                    // 1. new count is higher
                    // 2. If new count is same then choose with lexicographically lower
                    if (result === '' || countMap.get(result) < countMap.get(pattern) || (countMap.get(result) === countMap.get(pattern) && result > pattern)) {
                        result = pattern;
                    }
                }
            }
        }

    }
    // Calculate the right answer
    return result.split(' ');
};