Source: https://www.educative.io/courses/grokking-the-coding-interview
Notes & Reflections
Patterns
Sliding Window
- Staple problem to solve: find the average of every contiguous subarray of size K in a given array
- brute force would get us to loop through each element, for each sum and get the average after each inner-iteration— no bueno time complexity wise (O(N * K) where N = elements in the array, K = size of subarray being computed
- Instead we can take __advantage __ of the contiguity fact. In other words, let’s leverage the common elements and just compute the next element (end + 1) while taking away the first element (start + 1).
- Hence it’s like having two fixed indices on the array (window) that synchronously iterate through the array (that slides) and performs some running computation