L1. Introduction to Sliding Window and 2 Pointers | Templates | Patterns

About this video

• Video Title: L1. Introduction to Sliding Window and 2 Pointers | Templates | Patterns
• Channel: take U forward
• Speakers: Not specified in the transcript
• Duration: 00:36:55

Overview

This video serves as an introduction to the "Sliding Window" and "2 Pointers" algorithmic techniques, presented as part of the "Strivers A to Z DSA" course. The speaker explains that these are not traditional algorithms but rather patterns that require understanding a concept and then applying it to solve specific problems based on the problem statement. The video outlines four distinct patterns within this topic, with a focus on how to approach and solve problems using these techniques, particularly in the context of technical interviews.

Key takeaways

• The video introduces the "Sliding Window" and "2 Pointers" patterns as fundamental algorithmic tools.
• It categorizes problems into four main patterns: fixed-size window, longest/shortest subarray/substring with a condition, counting subarrays with a specific condition, and finding the shortest window with a condition.
• The "fixed-size window" pattern involves using two pointers (L and R) to maintain a window of a constant size, calculating a sum, and sliding the window by updating L and R.
• The "longest subarray/substring with a condition" pattern is identified as the most common, using a sliding window where the window expands (R moves) and contracts (L moves) to satisfy a given condition (e.g., sum less than or equal to k).
• The video touches upon optimizing solutions from O(n^2) to O(n) for certain problems by carefully managing the sliding window and its conditions.
• It also briefly mentions patterns for counting subarrays with a specific condition and finding the shortest window, noting that these can be more complex and sometimes require breaking down the problem.

Here are the notes for the video:

Introduction to Sliding Window & 2 Pointers

• Purpose: Introduce Sliding Window and 2 Pointers patterns for DSA problems, especially for interviews.

• Nature of Pattern: Not a rigid algorithm, but a concept to be adapted to problem statements.

• Key Techniques:

  • 2 Pointers: Often involves a Left (L) and Right (R) pointer.
  • Sliding Window: A dynamic sub-array or sub-string defined by L and R.

• Four Main Patterns Discussed:

  1. Fixed-Size Window:

     • Example: Finding the maximum sum of a sub-array of a fixed size (e.g., size 4).
     • Approach:
       • Initialize L=0, R=k-1.
       • Calculate the initial sum of the first window.
       • Iterate: Slide the window by incrementing R (add new element) and incrementing L (subtract old element).
       • Keep track of the maximum/minimum sum found.
     • Time Complexity: Typically O(n).

  2. Longest/Shortest Subarray/Substring with a Condition:

     • Most common pattern.
     • Example: Find the longest subarray whose sum is less than or equal to K.
     • Approach:
       • Use L and R pointers.
       • Initialize sum = 0, max_length = 0.
       • Expansion: Move R forward, adding arr[R] to the sum.
       • Contraction: If sum > K (or condition violated), move L forward, subtracting arr[L] from the sum, until the condition is met again.
       • Update Answer: If the current window (R - L + 1) is valid (meets the condition) and is longer than max_length, update max_length.
     • Optimization: Can sometimes improve from O(n^2) (brute force) to O(n).
     • Handling Sub-array vs. Substring: Concept is similar, applied to arrays or strings.

  3. Counting Subarrays with a Specific Condition:

     • Example: Count subarrays whose sum equals K.
     • Approach: Often involves a trick. The solution for "sum equals K" is derived from "sum less than or equal to K" minus "sum less than or equal to K-1".
     • This pattern is generally harder to solve directly with a simple sliding window expansion/contraction.

  4. Shortest Window/Subarray with a Condition:

     • Example: Find the shortest subarray whose sum is greater than or equal to K.
     • Approach:
       • Similar to pattern 2, but you aim to minimize the window length.
       • Expansion: Move R forward, updating sum.
       • Contraction: If the condition sum >= K is met, try to shrink the window from the left (move L forward) while the condition still holds.
       • Update Answer: If the window is valid, update min_length = min(min_length, R - L + 1).
     • Key Difference: After finding a valid window, the goal is to shrink it as much as possible from the left while maintaining validity.

• General Template for Sliding Window (Pattern 2/4):

  • Initialize L=0, sum=0, result (max_len/min_len) = appropriate initial value.
  • Loop with R from 0 to n-1:
    • Add arr[R] to sum.
    • While the condition is violated (e.g., sum > K):
      • Subtract arr[L] from sum.
      • Increment L.
    • If the condition is met:
      • Update the result (e.g., max_length = max(max_length, R - L + 1)).
  • Return result.

• Time/Space Complexity:

  • Most sliding window problems aim for O(n) time complexity.
  • Space complexity is often O(1) unless a hash map or other data structure is needed based on the specific problem's constraints.

Here are the notes for the video, including pseudocode for the common sliding window patterns:

Introduction to Sliding Window & 2 Pointers

• Purpose: Introduce Sliding Window and 2 Pointers patterns for DSA problems, especially for interviews.

• Nature of Pattern: Not a rigid algorithm, but a concept to be adapted to problem statements.

• Key Techniques:

  • 2 Pointers: Often involves a Left (L) and Right (R) pointer.
  • Sliding Window: A dynamic sub-array or sub-string defined by L and R.

• Four Main Patterns Discussed:

  1. Fixed-Size Window:

     • Example: Finding the maximum sum of a sub-array of a fixed size (e.g., size k).
     • Approach:
       • Initialize L=0, R=k-1.
       • Calculate the initial sum of the first window.
       • Iterate: Slide the window by incrementing R (add new element) and incrementing L (subtract old element).
       • Keep track of the maximum/minimum sum found.
     • Time Complexity: O(n).
     • Pseudocode Example (Max Sum of Fixed Size k):

       def max_sum_fixed_window(arr, k):
           n = len(arr)
           if n < k:
               return 0 # Or handle error
       
           current_sum = sum(arr[:k])
           max_sum = current_sum
       
           for i in range(k, n):
               current_sum += arr[i] - arr[i-k] # Slide window: add new, remove old
               max_sum = max(max_sum, current_sum)
       
           return max_sum
       

  2. Longest/Shortest Subarray/Substring with a Condition:

     • Most common pattern.
     • Example: Find the longest subarray whose sum is less than or equal to K.
     • Approach:
       • Use L and R pointers.
       • Initialize sum = 0, max_length = 0.
       • Expansion: Move R forward, adding arr[R] to the sum.
       • Contraction: If sum > K (or condition violated), move L forward, subtracting arr[L] from the sum, until the condition is met again.
       • Update Answer: If the current window (R - L + 1) is valid (meets the condition) and is longer than max_length, update max_length.
     • Optimization: Can often improve from O(n^2) (brute force) to O(n).
     • Handling Sub-array vs. Substring: Concept is similar, applied to arrays or strings.
     • Pseudocode Example (Longest Subarray Sum <= K):

       def longest_subarray_sum_le_k(arr, k):
           n = len(arr)
           l = 0
           current_sum = 0
           max_length = 0
       
           for r in range(n):
               current_sum += arr[r] # Expand window
       
               # Contract window if condition is violated
               while current_sum > k:
                   current_sum -= arr[l]
                   l += 1
       
               # If condition is met, update max_length
               # The window arr[l...r] is now valid
               max_length = max(max_length, r - l + 1)
       
           return max_length
       

     • Pseudocode Example (Shortest Subarray Sum >= K):

       import sys
       def shortest_subarray_sum_ge_k(arr, k):
           n = len(arr)
           l = 0
           current_sum = 0
           min_length = sys.maxsize # Initialize with a very large value
       
           for r in range(n):
               current_sum += arr[r] # Expand window
       
               # Contract window WHILE condition is met AND trying to find shortest
               while current_sum >= k:
                   min_length = min(min_length, r - l + 1)
                   current_sum -= arr[l]
                   l += 1
       
           return min_length if min_length != sys.maxsize else 0 # Handle case where no such subarray exists
       

  3. Counting Subarrays with a Specific Condition:

     • Example: Count subarrays whose sum equals K.
     • Approach: Often involves a trick. The solution for "sum equals K" is derived from "sum less than or equal to K" minus "sum less than or equal to K-1".
     • This pattern is generally harder to solve directly with a simple sliding window expansion/contraction in O(n). Prefix sums with a hash map are common here.

  4. Shortest Window/Subarray with a Condition:

     • Covered by the "Shortest Subarray Sum >= K" pseudocode above.
     • Key Idea: Expand until valid, then shrink as much as possible while maintaining validity, updating the minimum length.

• General Template for Sliding Window (Pattern 2/4):

  # For problems looking for MAX length / count of valid windows
  def sliding_window_max(arr, k_condition): # k_condition represents the constraint
      n = len(arr)
      l = 0
      current_metric = 0 # e.g., sum, count of distinct chars
      result = 0 # e.g., max_length, count of windows
  
      for r in range(n):
          # Expand window: update current_metric with arr[r]
          current_metric += arr[r] # Example: sum
  
          # Contract window if condition is violated
          while not is_valid(current_metric, k_condition): # is_valid checks the condition
              current_metric -= arr[l]
              l += 1
  
          # If condition is met, process the current valid window
          # Example: For max length
          result = max(result, r - l + 1)
          # Example: For counting valid windows
          # result += (r - l + 1) # If ALL sub-windows ending at r are valid
  
      return result
  
  # For problems looking for MIN length
  def sliding_window_min(arr, k_condition):
      n = len(arr)
      l = 0
      current_metric = 0
      result = sys.maxsize # Initialize with infinity
  
      for r in range(n):
          # Expand window
          current_metric += arr[r]
  
          # Contract window WHILE condition is met and we are seeking minimum
          while is_valid(current_metric, k_condition): # is_valid checks the condition
              result = min(result, r - l + 1)
              current_metric -= arr[l]
              l += 1
  
      return result if result != sys.maxsize else 0 # Handle no valid window case
  

• Time/Space Complexity:

  • Most sliding window problems aim for O(n) time complexity because each element is visited by L and R pointers at most a constant number of times.
  • Space complexity is often O(1) unless a hash map or other data structure is needed based on the specific problem's constraints (e.g., pattern 3 might use a hash map).

About this video

• Video Title: L1. Introduction to Sliding Window and 2 Pointers | Templates | Patterns
• Channel: take U forward
• Speakers: Not specified in the transcript
• Duration: 00:36:55

Overview

This video serves as an introduction to the "Sliding Window" and "2 Pointers" algorithmic techniques, presented as part of the "Strivers A to Z DSA" course. The speaker explains that these are not traditional algorithms but rather patterns that require understanding a concept and then applying it to solve specific problems based on the problem statement. The video outlines four distinct patterns within this topic, with a focus on how to approach and solve problems using these techniques, particularly in the context of technical interviews.

Key takeaways

• The video introduces the "Sliding Window" and "2 Pointers" patterns as fundamental algorithmic tools.
• It categorizes problems into four main patterns: fixed-size window, longest/shortest subarray/substring with a condition, counting subarrays with a specific condition, and finding the shortest window with a condition.
• The "fixed-size window" pattern involves using two pointers (L and R) to maintain a window of a constant size, calculating a sum, and sliding the window by updating L and R.
• The "longest subarray/substring with a condition" pattern is identified as the most common, using a sliding window where the window expands (R moves) and contracts (L moves) to satisfy a given condition (e.g., sum less than or equal to k).
• The video touches upon optimizing solutions from O(n^2) to O(n) for certain problems by carefully managing the sliding window and its conditions.
• It also briefly mentions patterns for counting subarrays with a specific condition and finding the shortest window, noting that these can be more complex and sometimes require breaking down the problem.

Ask me anything about this video

1. What are the four main patterns of problems discussed in the video related to sliding window and two pointers?
2. How does the "fixed-size window" pattern typically work, and what are the roles of the L and R pointers?
3. In the context of finding the "longest subarray with a condition," what happens when the current window violates the condition?
4. What is the general approach to solving problems that ask for the count of subarrays meeting a specific condition?
5. Give me topics and tags to explore this video in detail.

import java.util.HashMap;
import java.util.Map;
import java.lang.Math;

class Solution {

    // Pattern 4: Shortest Window/Subarray with a Condition
    // Example: Find the shortest subarray whose sum is >= k
    public int shortestSubarraySumGeqK(int[] arr, int k) {
        int n = arr.length;
        int l = 0;
        long currentSum = 0; // Use long to prevent overflow
        int minLength = Integer.MAX_VALUE;

        for (int r = 0; r < n; r++) {
            currentSum += arr[r]; // Expand window

            // Contract window WHILE condition is met and we are seeking minimum
            // Note: The condition here is currentSum >= k
            while (currentSum >= k) {
                minLength = Math.min(minLength, r - l + 1);
                currentSum -= arr[l];
                l++;
            }
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength; // Return 0 if no such subarray exists
    }

    // Example for Pattern 2: Longest Subarray Sum <= K
    public int longestSubarraySumLeqK(int[] arr, int k) {
        int n = arr.length;
        int l = 0;
        long currentSum = 0;
        int maxLength = 0;

        for (int r = 0; r < n; r++) {
            currentSum += arr[r]; // Expand window

            // Contract window if condition is violated
            // The condition here is currentSum > k
            while (currentSum > k) {
                currentSum -= arr[l];
                l++;
            }

            // If condition is met (currentSum <= k), update maxLength
            maxLength = Math.max(maxLength, r - l + 1);
        }
        return maxLength;
    }
}