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. This is 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, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
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. ✅
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
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. 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. The Coding Interview Prep course includes 4 lessons in total.
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, so you can start here or from the beginning and move at your own pace. This is lesson 4 of 4.
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