loading...

Sliding Window Technique

jjb profile image JB Updated on ・2 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources:

  1. Video explanation
  2. Leetcode problem

Takeaways:

  • The sliding window technique is where we use two pointers on a collection. We say that one pointer represents the start of the window and the other the end of the window. The space/elements between the two pointers is the window size.
  • A sliding window can be of fixed length or it can be variable length (meaning the window expands/contracts dynamically).
    • Fixed length is often easier to grasp/think about. Both pointers, say i and j, in a loop are incremented by the same number each time our max window size is reached.
    • Variable length is where i or j change at a different pace to each other. Often questions requiring this technique don't provide a window size, but ask for the largest/smallest possible window given some constraints.
  • Here are some questions we can use the sliding window technique on:
    • In an array of n integers, find a contiguous k length subarray that has the largest value when it's elements are summed.
      • We can use two pointers here and our window would be of size k.
    • What is the size of the minimum subarray that when summed will equal a target sum?
      • We can use two pointers here, but because we want the minimum length subarray (i.e the question is asking how big/small the window is) the window can't be of fixed length.
    • What is the largest subarray of k distinct characters?
      • We can use two pointers here. This will again be a variable length window, as we are being asked what the size of the window is (largest subarray). We will also need to use an auxiliary data structure to keep track of how many distinct characters are in a given subarray.
  • A less obvious question where sliding window would come in handy:
    • Given two strings inputA & inputB, determine if any permutation of inputA is a substring of inputB.
      • Here we can use two pointers and the window will be of fixed size/won't ever grow larger than the length of inputA.

Below are solutions to all the problems mentioned. I have annotated the source code with time & space complexities for each solution:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Feb 11 by:

Discussion

markdown guide