Sliding window technique in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique?

The sliding window technique is a method used to solve problems that involve arrays or lists by creating a 'window' of elements and moving it across the data to find a solution efficiently.

beginner

How does the sliding window technique improve efficiency?

It avoids repeated work by reusing previous calculations as the window moves, reducing the time complexity compared to checking all possible subarrays or segments.

beginner

Give a real-life example where the sliding window technique can be applied.

Checking the highest temperature over every 7-day period in a month can use a sliding window to move day by day, updating the highest temperature without rechecking all days each time.

intermediate

What are the two main types of sliding windows?

Fixed-size windows, which move by one element at a time, and variable-size windows, which can expand or shrink based on conditions.

beginner

Why is the sliding window technique preferred over brute force in many problems?

Because it reduces the number of operations by not recalculating everything from scratch for each new position, leading to faster and more efficient solutions.

What does the 'window' represent in the sliding window technique?

A The entire data set

B A subset of elements in a sequence

C A single element only

D An unrelated data structure

The window is a subset of elements that moves across the data to analyze parts of the sequence.

Which problem is best suited for the sliding window technique?

A Finding the maximum sum of any continuous subarray of fixed length

B Sorting an array

C Searching for a specific element in an unsorted list

D Calculating factorial of a number

Sliding window efficiently finds sums or other properties in continuous subarrays.

How does a fixed-size sliding window move?

A By doubling its size each time

B By jumping randomly

C It stays fixed and does not move

D By adding and removing one element at a time

A fixed-size window moves by removing the first element and adding the next element in the sequence.

What is a key benefit of using a variable-size sliding window?

A It never changes size

B It always processes the entire data set at once

C It can adjust to meet certain conditions dynamically

D It sorts the data automatically

Variable-size windows expand or shrink to satisfy problem-specific conditions.

Which of these is NOT a typical use case for sliding window?

A Binary search in a sorted array

B Calculating moving averages

C Finding longest substring without repeating characters

D Detecting patterns in streaming data

Binary search is a different algorithm and does not use sliding windows.

Explain the sliding window technique and how it helps solve problems involving arrays or lists.

Think about how you can look at parts of a list without starting over each time.

Describe the difference between fixed-size and variable-size sliding windows with examples.

Consider how the window size changes or stays the same.

Practice

1. What is the main purpose of the sliding window technique in data processing?

easy

A. To efficiently process continuous segments of data without repeated work

B. To sort data in ascending order

C. To store data permanently in memory

D. To randomly access elements in a list

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over data to process parts efficiently.

2. Step 2: Identify the main goal

   It avoids repeated calculations by updating results as the window moves, improving efficiency.

3. Final Answer:

   To efficiently process continuous segments of data without repeated work -> Option A

4. Quick Check:

   Sliding window = efficient continuous data processing [OK]

Hint: Think of a moving window checking parts step-by-step [OK]

Common Mistakes:

• Confusing sliding window with sorting algorithms
• Thinking it stores data permanently
• Assuming it accesses data randomly

2. Which of the following is the correct way to initialize a sliding window of size 3 over a list arr in Python?

easy

A. window = arr{0:3}

B. window = arr(0,3)

C. window = arr[0:3]

D. window = arr[3]

Solution

1. Step 1: Recall Python slicing syntax

   Python uses square brackets and colon to slice lists: arr[start:end] extracts elements from start up to but not including end.

2. Step 2: Apply slicing for window size 3

   To get first 3 elements, use arr[0:3]. Other options use incorrect syntax.

3. Final Answer:

   window = arr[0:3] -> Option C

4. Quick Check:

   Python slice for first 3 elements = arr[0:3] [OK]

Hint: Remember Python slices use square brackets and colon [OK]

Common Mistakes:

• Using parentheses instead of brackets for slicing
• Using curly braces which are invalid for lists
• Accessing a single element instead of a slice

3. Consider the Python code below using sliding window to find the maximum sum of any 3 consecutive numbers in arr:

arr = [2, 1, 5, 1, 3, 2]
window_sum = sum(arr[0:3])
max_sum = window_sum
for i in range(3, len(arr)):
    window_sum += arr[i] - arr[i-3]
    if window_sum > max_sum:
        max_sum = window_sum
print(max_sum)

What is the output?

medium

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Calculate initial window sum

   Sum of first 3 elements: 2 + 1 + 5 = 8. Set max_sum = 8.

2. Step 2: Slide window and update sums

   i=3: window_sum = 8 + arr[3] - arr[0] = 8 + 1 - 2 = 7 (max_sum=8)
   i=4: window_sum = 7 + arr[4] - arr[1] = 7 + 3 - 1 = 9 (max_sum=9)
   i=5: window_sum = 9 + arr[5] - arr[2] = 9 + 2 - 5 = 6 (max_sum=9)

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Max sum of 3 consecutive = 9 [OK]

Hint: Add new element, subtract old element to update sum [OK]

Common Mistakes:

• Recalculating sum of window each time instead of updating
• Mixing up indices when subtracting old element
• Not updating max_sum correctly

4. The following code attempts to find the minimum sum of any 2 consecutive numbers in arr using sliding window:

arr = [4, 3, 7, 1, 2]
window_sum = arr[0] + arr[1]
min_sum = window_sum
for i in range(2, len(arr)):
    window_sum = window_sum + arr[i] - arr[i-1]
    if window_sum < min_sum:
        min_sum = window_sum
print(min_sum)

What is the error in this code?

medium

A. The window size is incorrectly handled in subtraction index

B. The loop range should start from 1, not 2

C. The initial window sum is calculated incorrectly

D. The comparison operator in if statement is wrong

Solution

1. Step 1: Analyze window size and indices

   The window size is 2. When sliding to include arr[i], subtract the leaving element arr[i-2].

2. Step 2: Identify the error

   Code subtracts arr[i-1], but should subtract arr[i-2]. arr[i-1] remains in the window.

3. Step 3: Verify with trace

   i=2: should be 7 + 7 - 4 = 10, but code 7 + 7 - 3 = 11 (wrong).

4. Final Answer:

   The window size is incorrectly handled in subtraction index -> Option A

5. Quick Check:

   For size k=2, subtract arr[i-k] [OK]

Hint: Check subtraction index matches window size [OK]

Common Mistakes:

• Using wrong index for element leaving the window
• Starting loop at wrong index
• Incorrect initial sum calculation

5. You want to find the longest substring of a string s that contains at most 2 distinct characters using the sliding window technique. Which approach correctly applies the sliding window here?

hard

A. Fix window size to 2 and slide over the string

B. Expand the window by moving right pointer, shrink from left when distinct chars exceed 2

C. Count total distinct characters in the string once and return that count

D. Use nested loops to check all substrings of length 2

Solution

1. Step 1: Understand problem requirements

   We want the longest substring with at most 2 distinct characters, so window size is variable.

2. Step 2: Apply sliding window logic

   Expand window by moving right pointer. If distinct chars exceed 2, shrink window from left until condition holds.

3. Step 3: Evaluate options

   Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 matches this approach. Fix window size to 2 and slide over the string fixes window size incorrectly. Options C and D do not use sliding window properly.

4. Final Answer:

   Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 -> Option B

5. Quick Check:

   Variable window size with condition check = Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 [OK]

Hint: Adjust window size dynamically based on distinct chars count [OK]

Common Mistakes:

• Fixing window size instead of adjusting dynamically
• Not shrinking window when condition breaks
• Using brute force nested loops instead of sliding window