Length of Longest Subarray With at Most K Frequency

Length of Longest Subarray With at Most K Frequency - Problem

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,1,2,3], k = 2

› Output: 6

💡 Note: The whole array is good since each element appears at most 2 times: 1 appears 2 times, 2 appears 2 times, 3 appears 2 times.

Example 2 — Frequency Constraint

$ Input: nums = [1,2,1,2,1,2,1], k = 2

› Output: 4

💡 Note: Longest good subarray could be [1,2,1,2] with length 4. Element 1 appears 2 times and element 2 appears 2 times.

Example 3 — Single Element

$ Input: nums = [5,5,5,5,5], k = 4

› Output: 4

💡 Note: Element 5 can appear at most 4 times, so longest good subarray has length 4.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and frequency limit k

Process

Find longest subarray with all frequencies ≤ k

Output

Length of longest valid subarray

Key Takeaway

🎯 Key Insight: Use sliding window to maintain frequency constraints efficiently in O(n) time

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a sliding window that expands greedily and contracts only when frequency constraints are violated. The optimal approach uses two pointers with a hash map to track frequencies. Time: O(n), Space: O(min(n,k))

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window (Optimal)	O(n)	O(min(n,k))	Use expandable sliding window with frequency tracking
Brute Force - Check All Subarrays	O(n³)	O(n)	Check every possible subarray and count frequencies

Sliding Window (Optimal) — Algorithm Steps

Step 1: Initialize sliding window with left=0, right=0 and frequency map
Step 2: Expand right pointer, increment frequency of nums[right]
Step 3: If frequency > k, move left pointer until valid again
Step 4: Update maximum window size and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Move right pointer and add element to frequency map

Check Constraint

If frequency > k, shrink window from left

Update Maximum

Track the longest valid window seen

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int left = 0;
    int maxLength = 0;
    int freq[2001] = {0}; // Assuming values in range [-1000, 1000]
    
    for (int right = 0; right < numsSize; right++) {
        freq[nums[right] + 1000]++;
        
        while (freq[nums[right] + 1000] > k) {
            freq[nums[left] + 1000]--;
            left++;
        }
        
        int len = right - left + 1;
        if (len > maxLength) {
            maxLength = len;
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is visited at most twice (once by right, once by left pointer)

✓ Linear Growth

Space Complexity

O(min(n,k))

Hash map stores at most min(n, k*unique_elements) frequencies

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler