643. Maximum Average Subarray I with JS

Hi! Long time no see.

I've been so busy looking for a job, working, studying English, and learning new tech stacks... T_T

But algorithms are one of the most important things when preparing for a job, so I'm back! Hahaha.

Anyway, today I solved a problem about arrays.

 

First, this is my own code. It was too long and unfortunately, it caused a time limit exceeded (TLE) error... 😭

Why did I write my code like this?

Because I needed to find the largest average.

So, first, I created an array and stored the subarrays.
Then, in the second for loop, I calculated the sum and stored it in another array.
Finally, in the third for loop, I computed the averages and returned the maximum value using the Math.max() method.

 

 

/**

* @param {number[]} nums

* @param {number} k

* @return {number}

*/

var findMaxAverage = function(nums, k) {

let sub =[]

let x = []

let idx = 0

let n = k

for(let i = 0; i < nums.length; i++){

sub.push(nums.slice(i,k + i))

if(sub[i].length < k){

break

}

}

console.log(sub)

for(let i = 0; i < sub.length; i++ ){

let a = 0

if(sub[i].length === k){

a = sub[i].reduce((ac, cu) => ac + cu)

}

x.push(a)

}

let y = []

for(let i = 0; i < x.length; i++){

y.push(x[i] / k)

}

return Math.max(...y)

};

 

 

Here’s the simple code from GPT.

He? She? (Not sure 🤔) said that some parts of my code were duplicated, and I created a new array using the slice method, which increased the time complexity.

Also, I made three arrays, which affected memory usage...

My code was horrible... 😭

So, GPT suggested using the sliding window approach?

It was my first time learning about sliding window...

 

 

/**

* @param {number[]} nums

* @param {number} k

* @return {number}

*/

var findMaxAverage = function(nums, k) {

let sum = 0

for(let i = 0; i < k; i++){

sum += nums[i]

}

let maxSum = sum

for(let i = k; i < nums.length; i++){

sum = sum - nums[i - k] + nums[i]

maxSum = Math.max(maxSum, sum)

}

return maxSum / k

};

 

 

So the key part is:

sum = sum - nums[i - k] + nums[i]; maxSum = Math.max(maxSum, sum);

For example, let's take [10, 12, -5, -6, 50, 3] with k = 4.

1. First sum:
   10 + 12 - 5 - 6 = 11 This is the sum of the first k elements.
2. Second sum (Sliding the window):
   11 - nums[0] + nums[4] = 11 - 10 + 50 = 51

Did you get it?

Each time, the window moves to the next element while keeping the size fixed.

Why do we subtract nums[0]?

Because there's a fixed range limitation (k elements).

So, we subtract the first element from the previous window and then add the next element to get the new sum.