LeetCode 1152: Analyze User Website Visit Pattern

link

Time: \mathcal{O}(n^4), space: \mathcal{O}(n^3).

class Solution:
    def mostVisitedPattern(
        self, username: List[str], timestamp: List[int], website: List[str]
    ) -> List[str]:
        # O(N * lgN)
        info = sorted([(t, u, w) for t, u, w in zip(timestamp, username, website)])

        def get_patterns(sites):
            patterns = []
            for i in range(len(sites)):
                for j in range(i + 1, len(sites)):
                    for k in range(j + 1, len(sites)):
                        patterns.append((sites[i], sites[j], sites[k]))

            return patterns

        # O(N)
        user_visits = {}
        for _, u, w in info:
            if u not in user_visits:
                user_visits[u] = [w]
            else:
                user_visits[u].append(w)

        user_patterns = {}
        # O(N^3)
        for u in username:
            visits = user_visits[u]
            user_patterns[u] = set(get_patterns(visits))

        def get_score(p):
            nonlocal user_patterns
            score = 0
            for u, patterns in user_patterns.items():
                if p in patterns:
                    score += 1

            return score

        max_score = 0
        max_pattern = None
        website = [w for _, _, w in info]
        # O(N^3)
        for p in get_patterns(website):
            # O(N)
            score = get_score(p)
            if score > max_score:
                max_score = score
                max_pattern = p
            elif score == max_score and max_pattern and p < max_pattern:
                max_pattern = p

        return max_pattern

Leave a comment