I have been working this leet code questions
https://leetcode.com/problems/maximum-average-subarray-i/description/
I have been able to create a solution after understanding the sliding window algorithm. I was wondering with my code where my logic is going wrong, I do think my my issue seems to be in this section section of the code, but I am unable to pinpoint why.
while temp > k:
temp -= nums[left]
left += 1
ans = temp / (curr - left + 1)
While I do appreciate other solutions and ways solving this problem, I want to understand and get solution working first before I start looking at different ways of doing the problem, this way i get a better understanding of the algorithm.
Full code reference
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
left = 0
ans = 0
temp = 0
for curr in range(len(nums)):
temp += nums[curr]
curr += 1
while temp > k:
temp -= nums[left]
left += 1
ans = temp / (curr - left + 1)
return ans
temp
is the sum of the subarray, while k
is the number of elements in it - you shouldn't be comparing the two, they're two totally different things.
To implement a sliding window, I'd sum the first k
elements of nums
, and then run over it where in each iteration I drop the first element and add the last and then check if the sum has increased or not. Once you find the maximum sum, you can find the average by dividing it by k
.
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
currSum = sum(nums[:k])
maxSum = currSum
for i in range(k, len(nums)):
currSum = currSum - nums[i - k] + nums[i]
maxSum = max(maxSum, currSum)
return maxSum / k