Consistent Logs

# Consistent Logs ## Problem Statement The developers of a social media network application are analyzing user behavior through event logs. They have $n$ event logs, where $userEvent_i$ represents the unique identifier (userID) of the user who triggered the $i$-th event. Your task is to find the maximum possible length of a *consistent subarray* of these event logs. A subarray is defined as a contiguous sequence of elements within the $userEvent$ array. A subarray is considered *consistent* if the frequency of its most frequent user matches the frequency of the least frequent user in the *entire* $userEvent$ array. Formally, let $F_{full}(u)$ be the frequency of $userID \ u$ in the entire $userEvent$ array. The minimum frequency in the full array is defined as $min\_freq_{full} = \min_{u \text{ present in } userEvent} (F_{full}(u))$. For a given subarray $userEvent[L \dots R]$, let $F_{sub}(u)$ be the frequency of $userID \ u$ within this subarray. The subarray $userEvent[L \dots R]$ is consistent if $\max_{u \text{ present in } userEvent[L \dots R]} (F_{sub}(u)) = min\_freq_{full}$. Your goal is to determine the maximum length of such a consistent subarray. ## Input Format The first line contains an integer $n$ ($1 \le n \le 3 \times 10^5$), representing the total number of user events. The next $n$ lines each contain an integer $userEvent_i$ ($1 \le userEvent_i \le 10^9$), representing the userID of the $i$-th event. ## Output Format Output a single integer, the maximum length of a consistent subarray. ## Sample Test Cases ### Sample Input 1 ``` 10 1 2 1 3 4 2 4 3 3 4 ``` ### Sample Output 1 ``` 8 ``` ### Sample Input 2 ``` 3 9 9 9 ``` ### Sample Output 2 ``` 3 ``` ## Constraints - $1 \le n \le 3 \times 10^5$ - $1 \le userEvent_i \le 10^9$ - Time limit: 1 second - Memory limit: 256 MB ## Explanation ### Sample 1 Explanation For the given input $userEvent = [1, 2, 1, 3, 4, 2, 4, 3, 3, 4]$: 1. **Calculate full array frequencies:** - $userID \ 1: 2$ times - $userID \ 2: 2$ times - $userID \ 3: 3$ times - $userID \ 4: 3$ times 2. **Determine $min\_freq_{full}$:** The minimum frequency among all users in the full array is $2$. 3. **Find longest consistent subarray:** We need to find the longest subarray where the maximum frequency of any user within that subarray is exactly $2$. Consider the subarray $userEvent[0 \dots 7] = [1, 2, 1, 3, 4, 2, 4, 3]$. Its length is $8$. Within this subarray, the frequencies are: - $userID \ 1: 2$ times - $userID \ 2: 2$ times - $userID \ 3: 2$ times - $userID \ 4: 2$ times The maximum frequency within this subarray is $2$, which matches $min\_freq_{full}$. This subarray is consistent. It can be shown that no longer consistent subarray exists. Thus, the maximum consistent log length is $8$. ### Sample 2 Explanation For the given input $userEvent = [9, 9, 9]$: 1. **Calculate full array frequencies:** $userID \ 9: 3$ times. 2. **Determine $min\_freq_{full}$:** The minimum frequency in the full array is $3$. 3. **Find longest consistent subarray:** The only subarray of length $3$ is $[9, 9, 9]$. Within this subarray, $userID \ 9$ appears $3$ times. The maximum frequency is $3$, which matches $min\_freq_{full}$. Thus, the maximum consistent log length is $3$.