Practice/Amazon/Leetcode 1152. Analyze User Website Visit Pattern

Leetcode 1152. Analyze User Website Visit Pattern

CodingMust

Problem

You work as a data analyst for a web analytics platform. Your task is to identify user navigation patterns by analyzing browsing sessions.

Given three parallel arrays representing user activity logs:

• users: an array of usernames
• timestamps: an array of integers representing when each page was visited
• pages: an array of page names that were visited

Each index across all three arrays represents a single page visit event. Your goal is to find the 3-page sequence (pattern) that was visited by the most unique users. The sequence must follow chronological order based on timestamps for each user.

Important considerations:

• Each user should only be counted once per pattern, even if they visit that pattern multiple times
• The pages in a pattern must appear in chronological order (based on timestamps), but don't need to be consecutive visits
• If multiple patterns are visited by the same number of users, return the lexicographically smallest pattern
• Users may visit the same page multiple times, and duplicate pages can appear in patterns

Return the winning 3-page pattern as an array of three page names.

Requirements

1. Group all visits by user
2. Sort each user's visits chronologically by timestamp
3. Generate all possible 3-page subsequences for each user (maintaining chronological order)
4. Count how many unique users visited each pattern
5. Return the pattern with the highest unique user count
6. Break ties using lexicographic ordering

Constraints

• 3 ≤ users.length ≤ 50
• users.length == timestamps.length == pages.length
• 1 ≤ pages[i].length ≤ 10
• timestamps[i] are unique within the same user's visits
• Each user has at least 3 page visits
• Page names consist of lowercase English letters only
• Time complexity target: O(n³) where n is the average number of visits per user
• Space complexity target: O(n³) for storing all patterns

Examples

Example 1:

` Input: users = ["alice", "alice", "alice", "bob", "bob", "bob"] timestamps = [1, 2, 3, 4, 5, 6] pages = ["home", "products", "checkout", "home", "products", "checkout"]

Output: ["home", "products", "checkout"]

Explanation:

• alice's chronological journey: home(1) -> products(2) -> checkout(3)
• bob's chronological journey: home(4) -> products(5) -> checkout(6)
• Both users visited the pattern (home, products, checkout)
• This pattern has 2 unique users, making it the most popular `

Example 2:

` Input: users = ["user1", "user1", "user1", "user1", "user1"] timestamps = [1, 2, 3, 4, 5] pages = ["a", "b", "c", "d", "e"]

Output: ["a", "b", "c"]

Explanation:

• user1's patterns: (a,b,c), (a,b,d), (a,b,e), (a,c,d), (a,c,e), (a,d,e), (b,c,d), (b,c,e), (b,d,e), (c,d,e)
• All patterns have 1 unique user
• Lexicographically smallest is (a,b,c) `

Example 3:

` Input: users = ["john", "john", "john", "john", "mary", "mary", "mary"] timestamps = [1, 2, 3, 4, 5, 6, 7] pages = ["x", "x", "y", "z", "x", "x", "y"]

Output: ["x", "x", "y"]

Explanation:

• john's journey: x(1) -> x(2) -> y(3) -> z(4)
• mary's journey: x(5) -> x(6) -> y(7)
• Pattern (x,x,y) is visited by both john and mary (2 users)
• This is the most popular pattern `