Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Sliding Window Pattern

You are given an array and a number K. Find the average of every block of K neighbouring elements.

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

The direct approach is to take each starting index, add up the next five numbers, and divide. That is K additions for every one of the N starting points, so about O(N * K) work.

Now compare two neighbouring blocks. The block starting at index 0 holds 1, 3, 2, 6, -1. The block starting at index 1 holds 3, 2, 6, -1, 4. Four of the five numbers are the same. The direct approach adds those four again for no reason.

.....

.....

.....

Like the course? Get enrolled and start learning!
Priyanka Bhosale

Priyanka Bhosale

· 2 years ago

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

J

Jake Bartles

· 4 years ago

is it possible to download this course for offline access?

Show 1 reply
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
A

Adam Woolhether

· 4 years ago

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

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
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
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
O

ornella

· 4 years ago

Why windowSum is a float?

Show 1 reply

Reading Progress

0%