2Brute2Best
🔥0

Length of Longest Subarray With at Most K Frequency

Medium·LeetCode #2958 Pro OnlyPattern Transfer
LeetCode
01

Problem Statement

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

Call a subarray good if no value appears more than k times inside it.

Return the length of the longest good subarray.

Input

An integer array nums and an integer k.

Output

One integer: the length of the longest contiguous subarray in which every value appears at most k times.

Example 1
Input: nums = [1, 2, 3, 1, 2, 3, 1, 2], k = 2
Output: 6

[1, 2, 3, 1, 2, 3] has each value exactly twice. Adding one more element on either side would make some value appear 3 times.

Example 2
Input: nums = [1, 2, 1, 2, 1, 2, 1, 2], k = 1
Output: 2

Any 3 neighbours contain a repeated value, so the best is a pair like [1, 2].

Example 3
Input: nums = [5, 5, 5, 5, 5, 5, 5], k = 4
Output: 4

Four 5's are allowed, five are not.

Constraints
  • • 1 ≤ nums.length ≤ 10^5
  • • 1 ≤ nums[i] ≤ 10^9
  • • 1 ≤ k ≤ nums.length
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“longest subarray”
→ Contiguous range, maximise length → variable window.
“frequency of each element ≤ k”
→ The rule is about counts inside the window → frequency map.
“nums[i] up to 10^9”
→ Counts go in a hash map, not an array.
03

Approach Complexity Ladder

Brute Force — every start, grow until a value hits k + 1O(N²)O(N)

For each start, grow right with a fresh map until some count exceeds k

Optimal — sliding window, watch only the entering valueO(N)O(N)

Grow right; while the entering value's count > k, shrink left

Brute Force Intuition

Try every start. Grow the end one element at a time with a fresh count map. The moment the new element's count becomes k + 1, stop for this start. Keep the longest length seen.

Recognition rule for this sub-pattern:

Validity depends on the counts of things inside the window (distinct types, most frequent char, required letters). Keep a count map that updates on every add/remove.
Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track
C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track
Maximize the Confusion of an ExamMinimum Window Substring