[Coding Test] Consistent Logs

The developers of a social media network app want to analyze user behavior. They have n event logs where userEventIds[i] represents the userID of the user who triggered the ith event.

The team aims to find subarrays of the logs that are consistent, meaning the frequency of the most frequent user in the subarray matches the frequency of the least frequent user in the entire array.

Return the maximum length of these consistent logs.

Note: A subarray is a contiguous group of elements in an array.

Examples

Example 1:

Input: userEventIds = [1,2,1,3,4,2,4,3,3,4]Output: 8
Explanation: 
- The frequencies of userIDs 1 and 2 are 2.
- The frequencies of userIDs 3 and 4 are 3.
- The minimum frequency in the array is 2.
- The longest valid subarray has 8 elements: [1,2,1,3,4,2,4,3].
- The frequencies of 1, 2, 3, and 4 in this subarray are 2, 2, 1, and 2 respectively.
- The frequency of the most common element in the subarray is 2, which equals the minimum frequency in the entire array.

Example 2:

Input: userEventIds = [1,1,1,2,2]Output: 4
Explanation:
- User 1 appears 3 times, user 2 appears 2 times.
- Minimum frequency is 2.
- The longest consistent subarray is [1,1,2,2] with length 4.
- In this subarray, user 1 appears 2 times (max frequency = 2 = minimum frequency).

Example 3:

Input: userEventIds = [1,2,3,4,5]Output: 5
Explanation:
- All users appear exactly 1 time.
- Minimum frequency is 1.
- The entire array is consistent since max frequency in any subarray ≤ 1.

Constraints

1 <= userEventIds.length <= 10^5

1 <= userEventIds[i] <= 10^6

How to approach?

Brute Force

function findConsistentLogs(userEventIds: number[]): number {
    const totalFrequency = new Map<number, number>();
    for (const userId of userEventIds) {
        totalFrequency.set(userId, (totalFrequency.get(userId) || 0) + 1);
    }

    const minFrequency = Math.min(...totalFrequency.values());
    
    let maxLength = 0;

    for (let start = 0; start < userEventIds.length; start++) {
        const subarrayFrequency = new Map<number, number>();
        let currentMaxFreq = 0;
        
        for (let end = start; end < userEventIds.length; end++) {
            const userId = userEventIds[end];

            const newCount = (subarrayFrequency.get(userId) || 0) + 1;
            subarrayFrequency.set(userId, newCount);

            currentMaxFreq = Math.max(currentMaxFreq, newCount);

            if (currentMaxFreq === minFrequency) {
                maxLength = Math.max(maxLength, end - start + 1);
            }

            if (currentMaxFreq > minFrequency) {
                break;
            }
        }
    }
    
    return maxLength;
}

1. create total Frequency map
2. create for loop to check all the userId in the input array and set the user Id with count.
3. check the minimum frequency in the map and set it as variable.
4. set maxLength as 0.
5. create for loop using start index and create subArray Frequency map and set the current Max Frequency as 0.
6. create for loop using end index and set the intial value as start index.
7. create useId using end index.
8. create newCount using count in the frequency map, get it and + 1.
9. compare current max freq value and newCount value.
10. if the minFrequency value is same as the current max frequency value then set maxLenght as the bigger one between maxLength and the curren end index-start index +1.
11. when the current max freq is bigger than min frequency then inner for loop is break.
12. lastly return the maxLength.

summary

check all the possible subarray, and check the maxLength. when unique users number k is increasing it will have overhead. Time Complexity is O(n²), why? because it's using double loop to check all the possibilities of subArray.

Sliding Window

function findConsistentLogs(userEventIds) {
        
    const totalFrequency = new Map();
    
    for (const userId of userEventIds) {
        totalFrequency.set(userId, (totalFrequency.get(userId) || 0) + 1);
    }
        
    const minFrequency = Math.min(...totalFrequency.values());
          
    let maxLength = 0;        
    let start = 0;            
    const windowFrequency = new Map();  
    
    for (let end = 0; end < userEventIds.length; end++) {
        const userId = userEventIds[end];

        windowFrequency.set(userId, (windowFrequency.get(userId) || 0) + 1);

        while (windowFrequency.get(userId) >= minFrequency) {
            const leftUserId = userEventIds[start];
            windowFrequency.set(leftUserId, windowFrequency.get(leftUserId) - 1);
            start++;
        }
        maxLength = Math.max(maxLength, end - start + 1);
    }

    return maxLength;
}

1. create total Frequency map and use the for loop to find the minimum frequency.
2. set maxLength, start as 0, create window Frequency map.
3. create for loop using end index, set the userId using end index.
4. window frequency map will have the userId and its count between start and end index.
5. create while loop to check if the userId count in window frequency map is bigger than the minimum frequency value.
6. if it is bigger then create the leftUserId using start index, and set the count as -1 and plus 1 to start index.
7. compare maxLength and the window length.
8. lastly return the maxLength.

summary

in this approach, it only iterate one time on the input array to check the valid subarray and return the maxLength. It will have the O(n) Time complexity.