Sliding window technique in Data Structures Theory - Full Explanation

Introduction

Imagine you need to find patterns or sums in a list of numbers without checking every possible group from scratch. Doing this repeatedly can be slow and tiring. The sliding window technique helps by moving a fixed-size window across the list, updating results efficiently as it goes.

Explanation

Window Definition

The sliding window is a subset of elements from the list, usually continuous, that moves step-by-step. Its size can be fixed or variable depending on the problem. This window represents the current group of elements being analyzed.

The window is a moving subset of elements used to focus on a part of the data at a time.

Window Movement

Instead of recalculating everything for each new position, the window moves by removing the element that goes out and adding the new element that comes in. This reduces repeated work and speeds up processing.

The window moves by sliding forward, updating results incrementally rather than starting over.

Fixed vs Variable Window Size

Some problems require a window of fixed size, like finding the maximum sum of 3 consecutive numbers. Others need a variable size window that grows or shrinks based on conditions, such as finding the smallest subarray with a sum above a target.

Window size can be fixed or flexible depending on the problem's needs.

Efficiency Benefits

By reusing previous calculations and only updating what changes, the sliding window technique reduces time complexity from potentially quadratic to linear. This makes it practical for large datasets.

Sliding window improves efficiency by avoiding repeated full calculations.

Real World Analogy

Imagine reading a long book with a small bookmark that covers a few lines. You move the bookmark down line by line to focus on different parts without rereading the whole page each time. This helps you quickly find important information.

Window Definition → The bookmark covering a few lines of text

Window Movement → Sliding the bookmark down one line at a time

Fixed vs Variable Window Size → Changing the bookmark size to cover more or fewer lines depending on what you want to read

Efficiency Benefits → Not rereading the entire page every time, saving time and effort

Diagram

Diagram

List:  [1] [2] [3] [4] [5] [6] [7]
Window:     ┌─────┐
            │ 2 3 4 │
Move →     ┌─────┐
            │ 3 4 5 │
Move →     ┌─────┐
            │ 4 5 6 │

This diagram shows a fixed-size window moving step-by-step over a list of numbers.

Key Facts

Sliding window → A technique that moves a subset of data over a larger dataset to analyze parts efficiently.

Fixed window size → A window that stays the same size as it moves across the data.

Variable window size → A window that can grow or shrink based on conditions during processing.

Time complexity improvement → Sliding window reduces repeated calculations, often lowering time complexity from O(n²) to O(n).

Code Example

Data Structures Theory

def max_sum_subarray(arr, k):
    if len(arr) < k:
        return None
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

# Example usage
arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(arr, k))

Common Confusions

Believing the sliding window recalculates the entire window sum or result each time it moves.

Believing the sliding window recalculates the entire window sum or result each time it moves. The sliding window updates results by removing the old element and adding the new one, avoiding full recalculation.

Thinking sliding window only works with fixed-size windows.

Thinking sliding window only works with fixed-size windows. Sliding window can handle both fixed and variable window sizes depending on the problem.

Summary

Sliding window moves a subset of data across a larger set to analyze parts efficiently without repeating work.

It can use fixed or variable window sizes depending on the problem requirements.

This technique improves performance by updating results incrementally, often reducing time complexity to linear.

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