Consistent Logs
The developers of a social media app want to analyze user behavior. There are $n$ event logs where $userEvent[i]$ is the userId of the user who triggered the $i$-th event. A subarray of the logs is called consistent if the frequency of the most frequent user within that subarray equals the frequency of the least frequent user over the WHOLE array.
First compute $minFreq$, the smallest value-frequency taken over the entire array. Then find the maximum length of a contiguous subarray in which the maximum in-window value-frequency equals $minFreq$ (equivalently, no value inside the subarray appears more than $minFreq$ times, and at least one value reaches exactly $minFreq$).
A subarray is a contiguous block of elements.
Implement:
def findConsistentLogs(userEvent): # returns int: the maximum length of consistent logs
Constraints:
Example: $n = 10$, $userEvent = [1, 2, 1, 3, 4, 2, 4, 3, 3, 4]$. The frequencies of values 1 and 2 are 2; the frequencies of 3 and 4 are 3, so $minFreq = 2$. The longest valid subarray is $[1, 2, 1, 3, 4, 2, 4, 3]$ of length 8, in which every value appears exactly twice. The answer is 8.
Hints
- First reduce the problem: compute one number, the minimum value-frequency over the whole array. Call it minFreq. The window condition is just 'no value appears more than minFreq times'.
- Use a two-pointer sliding window keeping a count map. Track how many distinct values currently exceed minFreq; shrink from the left until that counter is zero, then record the window length. Use a dict since values reach 10^9.
Worked Solution
Compute the global minimum frequency, then run a sliding window that never lets any value's in-window count exceed $minFreq$.
Steps: 1. Count every value over the whole array; let $minFreq$ be the smallest of those counts. 2. Slide a window $[left, right]$ with a per-value count map. As we extend $right$, if a value's count reaches $minFreq + 1$, the window is invalid, so advance $left$ (decrementing counts) until that value drops back to $minFreq$. 3. The longest valid window is the answer. The longest valid window necessarily has some value reaching exactly $minFreq$, because a window strictly longer than any single value's allowed $minFreq$ occurrences must contain a value at the cap; and the global minimum guarantees at least one value can reach $minFreq$.
Why $O(n)$ matters: values are up to
```python from collections import Counter
def findConsistentLogs(userEvent): minFreq = min(Counter(userEvent).values()) cnt = {} left = 0 best = 0 over = 0 # number of distinct values currently exceeding minFreq for right, v in enumerate(userEvent): cnt[v] = cnt.get(v, 0) + 1 if cnt[v] == minFreq + 1: over += 1 while over > 0: lv = userEvent[left] if cnt[lv] == minFreq + 1: over -= 1 cnt[lv] -= 1 left += 1 best = max(best, right - left + 1) return best ```
Complexity: $O(n)$ time, $O(n)$ space. Each index enters and leaves the window at most once.
Intuition
The constraint 'max in-window frequency equals the global min frequency' is an upper bound: every value may appear at most minFreq times in a valid window. Upper-bounded counts are exactly what a sliding window handles in linear time. The maximal window will always touch the cap, so you only need to enforce the ceiling, not the equality explicitly.