Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Introduction to Sliding Window Pattern

In many problems dealing with an array (or a LinkedList), we are asked to find or calculate something among all the subarrays (or sublists) of a given size. For example, take a look at this problem:

Given an array, find the average of each subarray of ‘K’ contiguous elements in it.

Let's understand this problem with an example:

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

Here, we are asked to find the average of all subarrays of '5' contiguous elements in the given array. Let's solve this:

  1. For the first 5 numbers (subarray from index 0-4), the average is: $(1+3+2+6-1)/5 => 2

.....

.....

.....

Like the course? Get enrolled and start learning!
A

aj

· 4 years ago

How is the complexity of brute force O(N*K)? N is the number of elements in input array - which in the example is 9. But the outer loop doesn't run 9 times does it? It will only run from 0 to arr.length - K i.e 4 times.

Show 2 replies
J

Jake Bartles

· 4 years ago

is it possible to download this course for offline access?

Show 1 reply
D

Daniel Lim

· 4 years ago

What is the difference between these two ranges of for loops:

for i in range(len(arr)-K+1)

and

for i in range(K)

Show 1 reply
O

ornella

· 4 years ago

Why windowSum is a float?

Show 1 reply
S

srilu

· 4 years ago

In the Brute Force Python Solution why is "for i in range(len(arr)-K+1) " used instead of just " for i in range(K)" ? Aren't these two conditions the same thing?

Show 3 replies
A

Adam Woolhether

· 4 years ago

I'll be writing my solutions in Go, anyone interested in reviewing with me?

J

joe

· 4 years ago

sum in the O(n * k) element JS solution wasn't initialized properly as 'let sum'

O

ornella

· 4 years ago

WindowStart is not in the for statement, so it shouldn't iterate, so how it is moving across the array?

Show 1 reply
Priyanka Bhosale

Priyanka Bhosale

· 2 years ago

Is this course still available for me to access after my monthly subscription expires?