Sliding Window on Arrays in DSA C++ - Build from Scratch

Sliding Window on Arrays

📖 Scenario: Imagine you are analyzing daily temperatures over a week. You want to find the highest temperature recorded in every 3-day period.

🎯 Goal: Build a program that uses the sliding window technique to find the maximum temperature in every window of size 3 in the array of temperatures.

📋 What You'll Learn

Create an array called temperatures with exactly these values: {30, 32, 31, 35, 33, 34, 36}

Create an integer variable called window_size and set it to 3

Use a for loop with variable i to slide the window over the array and find the maximum temperature in each window

Print the maximum temperatures for each window separated by spaces

💡 Why This Matters

🌍 Real World

Sliding window technique is used in analyzing time series data like temperatures, stock prices, or sensor readings to find trends or peaks in fixed-size intervals.

💼 Career

Understanding sliding window algorithms is important for roles in data analysis, software development, and system optimization where efficient data processing is required.

1

Create the temperature array

Create an integer array called temperatures with these exact values: {30, 32, 31, 35, 33, 34, 36}

DSA C++

# Your code here

Hint

Use C++ array syntax with int temperatures[] = { ... };

2

Set the window size

Create an integer variable called window_size and set it to 3

DSA C++

int temperatures[] = {30, 32, 31, 35, 33, 34, 36};
# Your code here

Hint

Use int window_size = 3; to set the window size

3

Find maximum in each sliding window

Use a for loop with variable i from 0 to 7 - window_size to slide the window over temperatures. Inside the loop, find the maximum temperature in the current window of size window_size and store it in a variable called max_temp.

DSA C++

int temperatures[] = {30, 32, 31, 35, 33, 34, 36};
int window_size = 3;
// Your code here

Hint

Use nested loops: outer loop slides window, inner loop finds max in window

4

Print the maximum temperatures for each window

Inside the for loop, print the variable max_temp followed by a space. After the loop ends, print a newline.

DSA C++

int temperatures[] = {30, 32, 31, 35, 33, 34, 36};
int window_size = 3;
for (int i = 0; i  max_temp) {
            max_temp = temperatures[j];
        }
    }
    // Print max_temp followed by a space
}
// Print newline after loop

Hint

Use cout << max_temp << " " inside the loop and cout << endl; after the loop

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