Sliding Window on Arrays in DSA C++ - Deep Dive

Overview - Sliding Window on Arrays

What is it?

Sliding Window on Arrays is a technique to efficiently process parts of an array by moving a fixed-size window across it. Instead of recalculating results for each new window from scratch, it updates the result by removing the effect of the element leaving the window and adding the new element entering. This method helps solve problems like finding sums, maximums, or other properties in subarrays quickly.

Why it matters

Without sliding window, many problems require recalculating values for every subarray, leading to slow solutions that waste time and resources. Sliding window makes these calculations fast and practical, enabling real-time data processing, smoother user experiences, and efficient algorithms in fields like streaming data, network monitoring, and more.

Where it fits

Before learning sliding window, you should understand arrays and basic loops. After mastering it, you can explore advanced topics like two-pointer techniques, prefix sums, and dynamic programming optimizations.

Mental Model

Core Idea

Sliding window moves a fixed-size segment over an array, updating results incrementally instead of recalculating everything each time.

Think of it like...

Imagine cleaning a long hallway with a small carpet. You roll the carpet forward one step at a time, cleaning only the new spot while forgetting the old one, instead of cleaning the whole hallway repeatedly.

Array: [1, 3, 5, 2, 8, 7, 4]
Window size: 3

Positions of window:
[1, 3, 5] 2  8  7  4
 1 [3, 5, 2]  8  7  4
 1  3 [5, 2, 8] 7  4
 1  3  5 [2, 8, 7] 4
 1  3  5  2 [8, 7, 4]

Each step moves the window one element right, updating the result.

Build-Up - 7 Steps

1

Foundation

Understanding Arrays and Subarrays

Concept: Learn what arrays and subarrays are, and how to access elements and slices.

An array is a list of elements stored in order. A subarray is a continuous part of the array. For example, in [1, 2, 3, 4], [2, 3] is a subarray. You can access elements by their index, starting at 0.

Result

You can identify any subarray by its start and end positions.

Knowing how to work with arrays and subarrays is essential because sliding window operates on these continuous segments.

2

Foundation

Brute Force Subarray Processing

Concept: Calculate results for each subarray by checking all elements every time.

To find the sum of every subarray of size k, loop through the array, and for each position, sum the next k elements. For example, for array [1, 2, 3, 4] and k=2: - sum of [1, 2] = 3 - sum of [2, 3] = 5 - sum of [3, 4] = 7 This method repeats work and is slow for large arrays.

Result

Time complexity is O(n*k), which is inefficient for big data.

Understanding brute force highlights the need for a better approach to avoid repeated work.

3

Intermediate

Sliding Window Basic Technique

Concept: Use a window that moves across the array, updating results by adding and removing elements.

Instead of summing all elements each time, keep track of the current window sum. When moving the window right by one, subtract the element leaving the window and add the new element entering. For example, with array [1, 2, 3, 4] and k=2: - Start sum = 1 + 2 = 3 - Move window: sum = 3 - 1 + 3 = 5 - Move window: sum = 5 - 2 + 4 = 7 This reduces repeated calculations.

Result

Time complexity improves to O(n), making it efficient for large arrays.

Knowing how to update results incrementally is the key to sliding window's efficiency.

4

Intermediate

Implementing Sliding Window in C++

🤔Before reading on: do you think we need nested loops or just one loop to implement sliding window? Commit to your answer.

Concept: Write code that uses one loop to move the window and update the result.

Example code to find max sum of subarrays of size k: #include #include #include int maxSumSubarray(const std::vector& arr, int k) { int window_sum = 0, max_sum = INT_MIN; for (int i = 0; i < arr.size(); ++i) { window_sum += arr[i]; if (i >= k - 1) { if (window_sum > max_sum) max_sum = window_sum; window_sum -= arr[i - k + 1]; } } return max_sum; } int main() { std::vector arr = {1, 3, 2, 5, 1, 1, 2, 3}; int k = 3; std::cout << maxSumSubarray(arr, k) << std::endl; return 0; }

Result

Output: 10 (sum of subarray [3, 2, 5])

Using a single loop with incremental updates simplifies code and improves performance.

5

Intermediate

Handling Variable Window Sizes

🤔Before reading on: do you think sliding window can handle windows that change size during processing? Commit to your answer.

Concept: Extend sliding window to support windows that grow or shrink based on conditions.

Sometimes problems require windows that are not fixed size. For example, find the smallest subarray with sum at least S. We expand the window by moving the right pointer until sum >= S, then shrink from the left to find the minimal size. This uses two pointers moving independently, adjusting window size dynamically.

Result

Allows solving more complex problems like variable-length subarrays efficiently.

Understanding dynamic window sizes unlocks a wider range of problem-solving techniques.

6

Advanced

Optimizing with Deques for Max/Min Windows

🤔Before reading on: do you think just adding and removing elements is enough to find max in a sliding window? Commit to your answer.

Concept: Use a double-ended queue (deque) to track candidates for max or min in the window efficiently.

To find max in each window of size k, keep indexes of elements in a deque. Remove indexes of elements smaller than the new element from the back. The front of the deque always holds the index of the max element. When the window moves, remove indexes outside the window from the front. This approach finds max in O(n) time. Example code snippet: #include #include #include std::vector maxSlidingWindow(const std::vector& nums, int k) { std::deque dq; std::vector result; for (int i = 0; i < nums.size(); ++i) { while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) { while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); result.push_back(nums[dq.front()]); } } return result; } int main() { std::vector arr = {1,3,-1,-3,5,3,6,7}; int k = 3; auto res = maxSlidingWindow(arr, k); for (int v : res) std::cout << v << ' '; return 0; }

Result

Output: 3 3 5 5 6 7

Using a deque cleverly maintains candidates for max/min, avoiding full scans and achieving linear time.

7

Expert

Sliding Window in Streaming and Real-Time Systems

🤔Before reading on: do you think sliding window can be applied when data arrives continuously and infinitely? Commit to your answer.

Concept: Apply sliding window techniques to process data streams where the full array is not known upfront.

In streaming data, you cannot store all elements. Sliding window algorithms keep only the current window's data or summary statistics. For example, in network monitoring, sliding window counts packets in the last minute by updating counts as new packets arrive and old ones expire. This requires careful memory and time management to handle infinite or very large data efficiently.

Result

Enables real-time analytics and monitoring with limited memory and fast updates.

Understanding sliding window in streaming contexts reveals its power beyond static arrays, crucial for modern data applications.

Under the Hood

Sliding window works by maintaining a subset of the array elements defined by two pointers or indexes: the start and end of the window. Instead of recalculating results for each new window, it updates the previous result by removing the contribution of the element leaving the window and adding the new element entering. Data structures like queues or deques help maintain order and properties (like max or min) efficiently. This incremental update reduces time complexity from O(n*k) to O(n) or better.

Why designed this way?

The technique was designed to optimize repeated calculations over overlapping subarrays, which are common in many problems. Early solutions recalculated from scratch, wasting time. Sliding window leverages the overlap between consecutive windows to reuse computations. Alternatives like prefix sums help for sums but not for max/min efficiently, so sliding window with deques fills that gap.

Array: [a0, a1, a2, a3, ..., an]

Window start -> s
Window end   -> e

Process:
  ┌─────────────┐
  │ a_s ... a_e │  <-- current window
  └─────────────┘

Move window:
  Remove a_s from result
  Add a_{e+1} to result
  s++, e++

Data structures:
  - For sums: simple variables
  - For max/min: deque maintains candidates

Loop until e reaches end of array.

Myth Busters - 4 Common Misconceptions

Quick: Does sliding window always require a fixed window size? Commit to yes or no.

Common Belief: Sliding window only works with fixed-size windows.

Reality: Sliding window can handle variable-size windows by adjusting start and end pointers based on conditions.

Why it matters: Believing this limits problem-solving ability, missing solutions to many real problems like smallest subarray with sum >= S.

Quick: Is sliding window always faster than prefix sums? Commit to yes or no.

Common Belief: Sliding window is always the fastest method for subarray problems.

Reality: Sliding window is efficient for many problems but prefix sums or other methods can be faster or simpler for some queries.

Why it matters: Choosing sliding window blindly can lead to overcomplicated or less efficient solutions.

Quick: Does sliding window require extra memory proportional to the window size? Commit to yes or no.

Common Belief: Sliding window always needs extra memory equal to the window size.

Reality: For sums, sliding window uses constant extra memory; for max/min, it uses a deque which can be smaller than the window size.

Why it matters: Overestimating memory needs may discourage using sliding window in memory-sensitive applications.

Quick: Can sliding window find max in O(n) without scanning each window fully? Commit to yes or no.

Common Belief: Finding max in each window requires scanning all elements in that window every time.

Reality: Using a deque, sliding window finds max in O(n) total time without full scans per window.

Why it matters: Not knowing this leads to inefficient code and missed optimization opportunities.

Expert Zone

1

When using deques for max/min, the order of insertion and removal is critical to maintain correctness and efficiency.

2

Sliding window algorithms can be combined with binary search or hashing to solve complex substring or subarray problems.

3

In streaming data, sliding window implementations must handle element expiration carefully to avoid stale data affecting results.

When NOT to use

Sliding window is not suitable when subarrays are non-continuous or when queries require random access to arbitrary subarrays. Alternatives like segment trees, binary indexed trees, or prefix sums are better in those cases.

Production Patterns

Sliding window is widely used in real-time analytics, network traffic monitoring, video frame processing, and financial data analysis to maintain rolling statistics efficiently.

Connections

Two Pointer Technique

Sliding window is a specialized form of the two pointer technique where pointers define a window.

Understanding sliding window deepens comprehension of two pointer methods used in sorting, searching, and partitioning problems.

Queue Data Structure

Sliding window uses queues or deques to maintain order and efficiently update window properties.

Knowing queue operations helps implement sliding window algorithms that track max/min values without scanning.

Real-Time Signal Processing

Sliding window mirrors how signals are processed in chunks over time for filtering or analysis.

Recognizing this connection shows sliding window's role beyond arrays, in continuous data and engineering fields.

Common Pitfalls

#1 Recalculating the entire window sum every time the window moves.

Wrong approach:

for (int i = 0; i <= n - k; ++i) {
int sum = 0;
for (int j = i; j < i + k; ++j) {
sum += arr[j];
}
cout << sum << endl;
}

Correct approach:

int window_sum = 0;
for (int i = 0; i < k; ++i) window_sum += arr[i];
cout << window_sum << endl;
for (int i = k; i < n; ++i) {
window_sum += arr[i] - arr[i - k];
cout << window_sum << endl;
}

Root cause:

Not realizing that the window overlaps and previous sum can be reused.

#2 Removing elements from the deque incorrectly, causing wrong max values.

Wrong approach:

while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); // uses < instead of <=

Correct approach:

while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();

Root cause:

Misunderstanding strict vs non-strict comparison leads to incorrect deque state.

#3 Not removing elements outside the window from the front of the deque.

Wrong approach:

if (dq.front() < i - k + 1) { /* forgot to pop front */ }

Correct approach:

while (!dq.empty() && dq.front() <= i - k) dq.pop_front();

Root cause:

Forgetting to maintain window boundaries causes stale elements to affect results.

Key Takeaways

Sliding window is a powerful technique to process continuous parts of arrays efficiently by updating results incrementally.

It reduces time complexity from quadratic to linear for many subarray problems by avoiding repeated calculations.

Using data structures like deques allows sliding window to solve max/min queries in linear time.

Sliding window extends beyond fixed sizes to variable windows and streaming data, broadening its applicability.

Understanding sliding window connects to other key concepts like two pointers and queues, enriching problem-solving skills.

Practice

1. What is the main purpose of the sliding window technique on arrays?

easy

A. To find the maximum element in the entire array

B. To sort the array in ascending order

C. To efficiently process subarrays of fixed size without recomputing everything

D. To reverse the array elements

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over the array to process subarrays efficiently.

2. Step 2: Identify the purpose

   It avoids recomputing sums or other values for each subarray by updating results incrementally.

3. Final Answer:

   To efficiently process subarrays of fixed size without recomputing everything -> Option C

4. Quick Check:

   Sliding window = efficient fixed-size subarray processing [OK]

Hint: Think of a moving window that updates results quickly [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses arrays
• Assuming it finds max of whole array only

2. Which of the following is the correct syntax to start a sliding window loop of size k over an array arr of length n in C++?

easy

A. for (int i = k; i < n; i++)

B. for (int i = 0; i < n; i += k)

C. for (int i = 0; i < n + k; i++)

D. for (int i = 0; i <= n - k; i++)

Solution

1. Step 1: Determine valid window start indices

   The window of size k can start at indices from 0 up to n-k to fit inside the array.

2. Step 2: Check loop condition

   The loop must run while i <= n-k to include the last valid window.

3. Final Answer:

   for (int i = 0; i <= n - k; i++) -> Option D

4. Quick Check:

   Loop runs from 0 to n-k inclusive [OK]

Hint: Window start max index = n - k [OK]

Common Mistakes:

• Using i < n instead of i <= n-k
• Incrementing i by k skips windows
• Starting loop at k instead of 0

3. What is the output of the following C++ code?

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int n = 9, k = 5;
int max_sum = 0, window_sum = 0;
for (int i = 0; i < k; i++) {
    window_sum += arr[i];
}
max_sum = window_sum;
for (int i = k; i < n; i++) {
    window_sum += arr[i] - arr[i - k];
    if (window_sum > max_sum) max_sum = window_sum;
}
std::cout << max_sum << std::endl;

medium

A. 18

B. 17

C. 16

D. 19

Solution

1. Step 1: Calculate initial window sum of first 5 elements

   Sum = 1+3+2+6+(-1) = 11

2. Step 2: Slide window and update sums

   Next windows:
   i=5: sum=11+4-1=14
   i=6: sum=14+1-3=12
   i=7: sum=12+8-2=18
   i=8: sum=18+2-6=14
   Max sum found is 18

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Add new element, subtract old element in window [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Off-by-one errors in loop limits

4. Identify the bug in this sliding window code that finds the minimum sum of subarrays of size k:

int min_sum = INT_MAX, window_sum = 0;
for (int i = 0; i < n; i++) {
    window_sum += arr[i];
    if (i >= k) {
        window_sum -= arr[i - k - 1];
    }
    if (i >= k - 1 && window_sum < min_sum) {
        min_sum = window_sum;
    }
}

medium

A. The subtraction should happen when i >= k, but the subtraction index is off by one

B. The subtraction should happen when i >= k - 1, not i >= k

C. The subtraction should happen when i >= k, but loop should start from i = 1

D. The condition should be i > k instead of i >= k

Solution

1. Step 1: Check subtraction timing

   The condition if (i >= k) for subtraction is correct; it starts after the first full window of size k.

2. Step 2: Identify the index bug

   The code subtracts arr[i - k - 1], but it should be arr[i - k]. This is off-by-one; for i = k, it subtracts arr[-1] instead of arr[0].

3. Final Answer:

   The subtraction should happen when i >= k, but the subtraction index is off by one -> Option A

4. Quick Check:

   Index i - k - 1 causes arr[-1] access [OK]

Hint: Check when subtraction starts and which element is removed [OK]

Common Mistakes:

• Starting subtraction too early or too late
• Using wrong index for subtraction
• Not updating min_sum correctly

5. Given an array arr and an integer k, how would you find the maximum average of any subarray of size k using the sliding window technique?

hard

A. Calculate sum of all subarrays of size k and divide each by k, then find max average

B. Use sliding window to find max sum of subarrays of size k, then divide max sum by k

C. Sort the array and take average of last k elements

D. Use two nested loops to check all subarrays and keep track of max average

Solution

1. Step 1: Use sliding window to find max sum of size k

   Sliding window efficiently finds max sum by adding new element and removing old one.

2. Step 2: Calculate max average from max sum

   Divide the max sum by k to get the maximum average.

3. Final Answer:

   Use sliding window to find max sum of subarrays of size k, then divide max sum by k -> Option B

4. Quick Check:

   Max average = max sum / k using sliding window [OK]

Hint: Find max sum first, then divide by k for average [OK]

Common Mistakes:

• Sorting array instead of using sliding window
• Using nested loops causing inefficiency
• Dividing sums incorrectly