Sliding Window on Arrays in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum

What is the output of the following code that finds the maximum in each sliding window of size 3?

DSA C

int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int n = 8, k = 3;
int result[6];
int max_index = 0;
for (int i = 1; i < k; i++) {
    if (arr[i] > arr[max_index]) max_index = i;
}
result[0] = arr[max_index];
for (int i = k; i < n; i++) {
    if (max_index <= i - k) {
        max_index = i - k + 1;
        for (int j = max_index + 1; j <= i; j++) {
            if (arr[j] > arr[max_index]) max_index = j;
        }
    } else if (arr[i] > arr[max_index]) {
        max_index = i;
    }
    result[i - k + 1] = arr[max_index];
}
for (int i = 0; i <= n - k; i++) {
    printf("%d ", result[i]);
}

A 1 3 3 5 6 7

B 3 3 5 5 6 7

C 3 -1 5 3 6 7

D 3 3 5 3 6 7

💡 Hint

Track the maximum index carefully when the window slides.

The code finds the maximum in each window of size 3 by updating the max index when the window moves. The output is the maximum values for windows: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7].

❓ Predict Output

intermediate

Sum of Sliding Window

What is the output of this code that calculates the sum of each sliding window of size 4?

DSA C

int arr[] = {2, 1, 5, 1, 3, 2};
int n = 6, k = 4;
int sum = 0;
int result[3];
for (int i = 0; i < k; i++) {
    sum += arr[i];
}
result[0] = sum;
for (int i = k; i < n; i++) {
    sum += arr[i] - arr[i - k];
    result[i - k + 1] = sum;
}
for (int i = 0; i <= n - k; i++) {
    printf("%d ", result[i]);
}

A 11 10 9

B 9 10 12

C 2 1 5 1

D 9 10 11

💡 Hint

Add the new element and remove the old element from the sum as the window slides.

The sums for windows are: [2,1,5,1]=9, [1,5,1,3]=10, [5,1,3,2]=11.

🔧 Debug

advanced

Identify the error in sliding window minimum code

What error does the following code produce when trying to find the minimum in each sliding window of size 2?

DSA C

int arr[] = {4, 2, 12, 3, 5};
int n = 5, k = 2;
int min_index = 0;
for (int i = 1; i < k; i++) {
    if (arr[i] < arr[min_index]) min_index = i;
}
printf("%d ", arr[min_index]);
for (int i = k; i < n; i++) {
    if (min_index <= i - k) {
        min_index = i - k + 1;
        for (int j = min_index + 1; j <= i; j++) {
            if (arr[j] < arr[min_index]) min_index = j;
        }
    } else if (arr[i] < arr[min_index]) {
        min_index = i;
    }
    printf("%d ", arr[min_index]);
}

A Runtime error: out-of-bounds access

B No error, prints: 2 2 3 3

C No error, prints: 4 2 3 3

D Logic error: skips some minimum values

💡 Hint

Check the condition that updates min_index when the window slides.

The condition 'min_index < i - k' should be 'min_index <= i - k' to avoid accessing invalid indices. The current code can cause out-of-bounds access.

❓ Predict Output

advanced

Output of Sliding Window with Variable Window Size

What is the output of this code that prints the maximum of sliding windows with sizes increasing from 1 to 3?

DSA C

int arr[] = {1, 3, 2, 5};
int n = 4;
for (int k = 1; k <= 3; k++) {
    for (int i = 0; i <= n - k; i++) {
        int max_val = arr[i];
        for (int j = i + 1; j < i + k; j++) {
            if (arr[j] > max_val) max_val = arr[j];
        }
        printf("%d ", max_val);
    }
    printf("\n");
}

A

1 3 2 5 
3 2 5 
3 5 5 

B

1 3 2 5 
3 3 5 
2 5 5 

C

1 3 2 5 
3 3 5 
3 5 5 

D

1 3 2 5 
3 3 5 
3 3 5 

💡 Hint

For each window size, find the max in each window carefully.

For k=1: max values are elements themselves: 1 3 2 5 For k=2: windows [1,3], [3,2], [2,5] max are 3 3 5 For k=3: windows [1,3,2], [3,2,5] max are 3 5

🧠 Conceptual

expert

Sliding Window Algorithm Optimization

Which data structure is best suited to optimize the sliding window maximum problem to O(n) time complexity?

A Deque (double-ended queue)

B Priority Queue (Heap)

C Queue

D Stack

💡 Hint

Think about a structure that allows insertion and removal from both ends efficiently.

A deque allows adding and removing elements from both ends in O(1) time, which helps maintain candidates for maximum in the current window efficiently, achieving O(n) overall.