Problem Description

You are given three arrays that record website visit data:

• username: array of usernames
• website: array of website names
• timestamp: array of visit times

These arrays have the same length, and [username[i], website[i], timestamp[i]] means user username[i] visited website website[i] at time timestamp[i].

A pattern is defined as a sequence of exactly three websites (can be the same website repeated). For example:

• ["home", "away", "love"] - three different websites
• ["leetcode", "love", "leetcode"] - same website can appear multiple times
• ["luffy", "luffy", "luffy"] - all three can be the same website

The score of a pattern is the number of unique users who visited those three websites in that exact order (based on timestamps). The visits don't need to be consecutive - there can be other website visits in between, as long as the pattern websites are visited in the specified order.

For example:

• If a user visits ["home", "google", "away", "youtube", "love"] in that time order, they match the pattern ["home", "away", "love"]
• The pattern requires the websites to be visited in order according to their timestamps

Your task is to find the pattern with the highest score. If multiple patterns have the same highest score, return the lexicographically smallest one (comparing the patterns as tuples).

The solution approach involves:

1. Grouping website visits by user and sorting them by timestamp
2. For each user with at least 3 website visits, generating all possible 3-website combinations while preserving order
3. Counting how many unique users match each pattern
4. Returning the pattern with the highest count (or lexicographically smallest if there's a tie)

Intuition

The key insight is that we need to find patterns of three websites that are visited by multiple users in the same order. To approach this, we need to think about what information we actually need from the raw data.

First, we realize that the absolute timestamps don't matter - what matters is the relative order of visits for each user. So for each user, we need to know their sequence of website visits sorted by time.

Once we have each user's chronological visit sequence, we need to find all possible 3-website subsequences from their visits. Why subsequences and not just consecutive triplets? Because the problem states that the websites don't need to be visited contiguously - there can be other visits in between. For example, if a user visits ["A", "B", "C", "D", "E"], the pattern ["A", "C", "E"] is valid.

For a user with n website visits where n ≥ 3, we can form C(n, 3) different ordered triplets. We generate all these combinations using three nested loops: choosing the first website, then the second website from those that come after it, and finally the third website from those that come after the second.

An important detail is that we only want to count each pattern once per user. If a user visits ["A", "B", "A", "B"], the pattern ["A", "B", "B"] can be formed in multiple ways, but it should only count as 1 for this user. That's why we use a set to store unique patterns for each user before adding them to our global counter.

Finally, after counting how many users match each pattern, we need to handle ties. When multiple patterns have the same count, we return the lexicographically smallest one. This is naturally handled by sorting the patterns first by count (descending) and then by the pattern itself (ascending).

Learn more about Sorting patterns.

Solution Approach

The implementation follows these key steps:

Step 1: Organize data by user and timestamp

First, we create a dictionary d to group websites by user. We sort the input data by timestamp to ensure each user's website visits are in chronological order:

d = defaultdict(list)
for user, _, site in sorted(zip(username, timestamp, website), key=lambda x: x[1]):
    d[user].append(site)

The sorted() function with key=lambda x: x[1] sorts by the timestamp (second element). After this step, d[user] contains a list of websites that the user visited in chronological order.

Step 2: Generate all possible 3-website patterns for each user

For each user's website sequence, we generate all possible ordered triplets:

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

The three nested loops ensure we pick three websites in order: i < j < k. This maintains the chronological order requirement. We use a set s to store unique patterns for each user, preventing duplicate counting if the same pattern can be formed multiple ways from one user's visits.

Step 3: Count pattern occurrences across all users

After generating all unique patterns for a user, we add them to the global counter:

for t in s:
    cnt[t] += 1

Each pattern in the set increases the counter by 1, representing one user who matches that pattern.

Step 4: Find the pattern with highest score

Finally, we sort all patterns by their count (descending) and lexicographically (ascending) to handle ties:

return sorted(cnt.items(), key=lambda x: (-x[1], x[0]))[0][0]

The sorting key (-x[1], x[0]) means:

• -x[1]: Sort by count in descending order (negative for reverse)
• x[0]: Sort by pattern tuple lexicographically in ascending order

The [0][0] at the end extracts the pattern tuple from the first item (highest score, lexicographically smallest).

Time Complexity: O(n log n + u * m^3) where n is the total number of records, u is the number of unique users, and m is the maximum number of websites visited by a user.

Space Complexity: O(n + p) where p is the total number of unique patterns generated.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

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

Step 1: Organize data by user and timestamp

After sorting by timestamp and grouping by user:

• joe: ["home", "about", "career"]
• james: ["home", "cart", "maps", "home"]
• mary: ["home", "about", "career"]

Step 2: Generate all possible 3-website patterns for each user

For joe with ["home", "about", "career"]:

• Only one possible triplet: ("home", "about", "career")

For james with ["home", "cart", "maps", "home"]:

• Choosing indices (0,1,2): ("home", "cart", "maps")
• Choosing indices (0,1,3): ("home", "cart", "home")
• Choosing indices (0,2,3): ("home", "maps", "home")
• Choosing indices (1,2,3): ("cart", "maps", "home")

For mary with ["home", "about", "career"]:

• Only one possible triplet: ("home", "about", "career")

Step 3: Count pattern occurrences across all users

Pattern counts:

• ("home", "about", "career"): 2 users (joe and mary)
• ("home", "cart", "maps"): 1 user (james)
• ("home", "cart", "home"): 1 user (james)
• ("home", "maps", "home"): 1 user (james)
• ("cart", "maps", "home"): 1 user (james)

Step 4: Find the pattern with highest score

The pattern ("home", "about", "career") has the highest count of 2, so it's returned as the answer.

If there were a tie, for example if both ("home", "about", "career") and ("a", "b", "c") had count 2, we would return ("a", "b", "c") as it's lexicographically smaller.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m * k^3) where n is the total number of entries (length of username/timestamp/website arrays), m is the number of unique users, and k is the maximum number of websites visited by any single user. In the worst case where one user visits all n websites, this becomes O(n^3).

The space complexity is O(n + m * k^3). The dictionary d stores at most n website entries across all users. The set s for each user can contain at most C(k, 3) = k*(k-1)*(k-2)/6 unique 3-patterns, and the Counter cnt aggregates all unique patterns across all users. In the worst case with one user visiting all websites, this becomes O(n^3).

Breaking down the complexity:

• Sorting the initial data: O(n log n) time
• Building user-website dictionary: O(n) time and space
• For each user with k websites, generating all 3-patterns: O(k^3) time
• Storing unique patterns in set and counter: O(k^3) space per user
• Final sorting of counter items: O(p log p) where p is the number of unique patterns

The reference answer simplifies to O(n^3) for both time and space complexity by considering the worst-case scenario where a single user visits all n websites, making k = n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Duplicate Pattern Counting Per User

Issue: A critical mistake is counting the same pattern multiple times for a single user. If a user visits websites ["a", "b", "c", "b", "c"], the pattern ["a", "b", "c"] can be formed in multiple ways:

• Using indices (0, 1, 2)
• Using indices (0, 1, 4)
• Using indices (0, 3, 4)

Without proper handling, this pattern would be counted 3 times for this user, but it should only count once since it's still just one user matching the pattern.

Incorrect Code Example:

# WRONG: Directly adds to counter without deduplication
for sites in user_websites.values():
    m = len(sites)
    if m > 2:
        for i in range(m - 2):
            for j in range(i + 1, m - 1):
                for k in range(j + 1, m):
                    pattern_counter[(sites[i], sites[j], sites[k])] += 1

Solution: Use a set to store unique patterns for each user before counting:

# CORRECT: Use a set to ensure each pattern counts only once per user
for sites in user_websites.values():
    m = len(sites)
    unique_patterns = 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):
                    unique_patterns.add((sites[i], sites[j], sites[k]))
  
    # Now add each unique pattern once
    for pattern in unique_patterns:
        pattern_counter[pattern] += 1

Pitfall 2: Forgetting to Sort by Timestamp Before Grouping

Issue: The problem requires patterns to follow chronological order. If you group websites by user without first sorting by timestamp, the website order might be wrong.

Incorrect Code Example:

# WRONG: Groups websites without sorting by timestamp first
for i in range(len(username)):
    user_websites[username[i]].append(website[i])

Solution: Always sort the data by timestamp before grouping:

# CORRECT: Sort by timestamp before grouping
for user, time, site in sorted(zip(username, timestamp, website), key=lambda x: x[1]):
    user_websites[user].append(site)

Pitfall 3: Incorrect Lexicographical Comparison for Tie-Breaking

Issue: When multiple patterns have the same highest score, returning the wrong one due to incorrect sorting logic.

Incorrect Code Example:

# WRONG: Only sorts by count, doesn't handle lexicographical ordering
return max(pattern_counter.items(), key=lambda x: x[1])[0]

Solution: Use proper sorting with both count (descending) and lexicographical order (ascending):

# CORRECT: Sort by count (descending) then lexicographically (ascending)
sorted_patterns = sorted(pattern_counter.items(), key=lambda x: (-x[1], x[0]))
return list(sorted_patterns[0][0])