Sliding Window

Imagine that you're allowed to select 3 chocolate chip cookies in a contiguous subarray. Your goal is to find a window of 3 cookies with the most amount of chips!

The same concept can be applied to arrays or strings. The window boundry is defined by the left and right pointers as shown in the picture below:

Sliding window, k = 3

Example:

  1. Find the Maximum of subarray
  2. Detect repeating pattren in a string

There are 2 types of Sliding windows:

1. Fixed Window: Window size k is constant.

eg: Window of 3 cookies with the maximum amount of chips.

Fixed window, k = 3

2. Dynamic window: k changes.

eg: The smallest window with sum ≥ 7 

Dynamic Window

Sliding Window Algorithm

Imagine you have a long line of objects (an array), and you need to look at a fixed-sized group of them (the window, size k) and calculate something (like their sum).

1. The "Brute Force" (The Slow Way)
If you wanted to calculate the sum of every group of k=3 numbers, you would do this:
  •  Calculate the sum of Group 1.
  •  Calculate the sum of Group 2 (restarting the count).
  •  Calculate the sum of Group 3 (restarting the count)....and so on.
This is slow because you are doing a lot of unnecessary work.

2. The "Sliding Window" (The Fast Way)

The "Sliding Window" is a smart shortcut. Instead of restarting the calculation for the new group, you simply update the result from the previous group.
Steps:
Calculate the First Group: You calculate the sum of the very first window of size k (e.g., 1+5+2 = 8). This gives you your starting point.
   
 Slide: When you move the window one step to the right, only one number leaves and one new number enters.
   * Subtract the Old: Take the number that just left the group and subtract it from your current sum.
   * Add the New: Take the new number that just entered the group and add it to your current sum.

Algorithm


   Example:
  •    Array : [3, 4, 5, 3, 2, 7, 8] 
  •    k=3
  •    ProcessWindow =  Maximum sum

  • Window 1 : [3, 4, 5] (Sum: 12)
  • Slide Right: We drop the 3 and pick up the next element 3.
  • New Sum: 12 +3 - 3 =12

Workflow


This way, you find the new sum with just two quick operations (one subtraction and one addition) instead of recalculating all three numbers! You repeat this one-step update until you reach the end of the array.
This makes the algorithm extremely fast!



Comments

Post a Comment

Popular posts from this blog

1. Repeated DNA Sequences

Image
 T he  DNA sequence  is composed of a series of nucleotides abbreviated as  'A' ,  'C' ,  'G' , and  'T' For example,  "ACGAATTCCG"  is a  DNA sequence . When studying  DNA , it is useful to identify repeated sequences within the DNA. Given a string  s  that represents a  DNA sequence , return all the  10 -letter-long  sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in  any order .   Example 1: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"] Ex ample 2: Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Read more

Top K Elements

Image
  The  top k elements  pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as  k, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection. Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest k  elements. With this pattern, we either use a max heap or a min heap to find the smallest or largest k elements, respectively, because they allow us to efficiently maintain a collection of elements ordered in a way that gives us quick access to the smallest (min heap) or largest (max heap) element. Algorithm Max Heap => Smallest k elements Min Heap => Largest k elements Top 3 largest numbers
Read more

1. Valid palindrome

Image
Algorithm: Initialize two pointers, left at the start and right at the end of the string. Iterate until the left pointer is before the right pointer, skipping non-alphanumeric characters for both pointers. Compare characters positioned at the left and right pointers in lowercase; if they differ, return FALSE. Move left forward and right backward to check the next pair of characters. If the traversal completes without mismatches, return TRUE indicating the string is a palindrome. valid palindrome
Read more