Count Windows That Satisfy a Rule
At-most-K minus at-most-(K-1) trick.
Count Windows That Satisfy a Rule is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Counting, Not Measuring
Sometimes you must count subarrays meeting a rule, not find the longest one. A small trick turns this into easy sliding-window work. 🔢
The Exactly-K Challenge
Counting subarrays with exactly K of something directly is awkward. The boundary keeps flipping, which makes a single clean window hard.
The At-Most Reframe
Counting subarrays with at most K is much easier with one window. As you expand right, every valid left gives a counted subarray.
The Subtraction Trick
Exactly K equals atMost(K) minus atMost(K - 1). Two easy counts combine into the tricky one you actually want.
answer = at_most(k) - at_most(k - 1)Build the Helper
Write one function that counts subarrays with at most k. It slides a window and shrinks whenever the count exceeds k.
def at_most(k):
left = 0
total = 0Shrink on Violation
Expand right and update the window. While it holds more than k, move left forward to bring it back into range.
while count > k:
# remove a[left]
left += 1Add the Window Count
After fixing the window, every subarray ending at right with a start from left onward is valid. Add right minus left plus one.
total += right - left + 1Why That Count Works
For a fixed right, the valid starts are left, left+1, up to right. That is exactly right - left + 1 subarrays, all satisfying at-most-k.
Combine the Two Calls
Run the helper twice and subtract. Each call is O(n), so the full exactly-K count is still linear overall.
return at_most(k) - at_most(k - 1)Guard the Edge
When k is zero, atMost(k - 1) would use negative one. Handle that case so the helper still returns a sensible zero count.
Where It Applies
This at-most minus at-most idea fits counting subarrays with exactly K distinct values, K odds, or any monotonic per-window property.
Quick Check
You want to count subarrays with exactly K distinct elements.
Recap
Counting exactly K is just atMost(K) minus atMost(K - 1). Each helper slides a window in O(n), so the whole count stays linear. ✅
Frequently asked questions
Is the “Count Windows That Satisfy a Rule” lesson free?
Yes — the full text of “Count Windows That Satisfy a Rule” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Count Windows That Satisfy a Rule”?
At-most-K minus at-most-(K-1) trick. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Count Windows That Satisfy a Rule” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Fixed-Size Window Sums
- Variable Window with Two Pointers
- Longest Substring Without Repeats
- Count Windows That Satisfy a Rule