Sliding Window on Arrays in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique in arrays?

It is a method to create a 'window' of fixed size that moves over the array to solve problems efficiently by avoiding repeated work.

beginner

Why is sliding window better than nested loops for some problems?

Because it reduces time complexity by reusing previous computations instead of recalculating for every new window, often changing O(n*k) to O(n).

beginner

In sliding window, what happens when the window moves forward?

The element leaving the window is removed from the current calculation, and the new element entering the window is added.

intermediate

How do you find the maximum sum of any subarray of size k using sliding window?

1. Calculate sum of first k elements.<br>2. Slide the window by one element at a time:<br> - Subtract element leaving window<br> - Add element entering window<br>3. Track the maximum sum found.

beginner

What is a common real-life example to understand sliding window?

Imagine looking through a fixed-size window on a moving train to see parts of the scenery. You only focus on what is inside the window as it moves forward.

What does the sliding window technique help to avoid?

A Recalculating values for overlapping parts of the array

B Sorting the array multiple times

C Using extra memory for storing all subarrays

D Ignoring elements outside the window

Sliding window avoids recalculating values for overlapping parts by updating the result incrementally.

If you want to find the average of every subarray of size 3, what is the first step?

A Sort the array

B Calculate sum of first 3 elements

C Find the maximum element

D Reverse the array

You start by calculating the sum of the first 3 elements to form the initial window.

When sliding the window forward by one element, what do you do?

A Add the new element and subtract the old element leaving the window

B Add both new and old elements

C Subtract both new and old elements

D Ignore the new element

You add the new element entering the window and subtract the element leaving to update the sum efficiently.

What is the time complexity of sliding window for fixed size k over an array of size n?

A O(n^2)

B O(n*k)

C O(n)

D O(k)

Sliding window processes each element once, resulting in O(n) time complexity.

Which problem is best suited for sliding window?

A Binary search in sorted array

B Sorting an array

C Finding shortest path in graph

D Finding max sum of subarrays of fixed size

Sliding window is ideal for problems involving fixed-size subarrays like max sum.

Explain how the sliding window technique works on arrays with an example.

Think about moving a fixed-size window over the array and updating sums.

Describe the benefits of using sliding window over nested loops for subarray problems.

Focus on how sliding window reduces repeated calculations.