Understand that this is written in the way I think and is very informal!
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 105 will be accepted.
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Constraints:
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104
Given an array of numbers and a number, which means how many elements in a row to compare, find the largest average value of that length in the array (and return that average).
eg: nums: 1,2,3,4,5,6,7,8; subarray length: 3; -> biggest will be: [6,7,8]/3 -> 7.00
I can clearly see that the subarray length will not change so I can first get the highest subarray values then find the average of that because the divisor is always going to be the same so the numerator just needs to be the largest. Really I mean if I have [1,2,3] and [6,7,8] (from an array of 1-8, with 3 subarray length) I know that (1+2+3)/3 is less than (6+7+8)/3 and that means the average will always just be the largest of three and then I can divide it later at the end.
Loop through the array, from start to length - X (divisor).
Keep hold of set of X numbers' sum
Return sum / X (average)
After writing this out I can tell there are optimizations available that I don't know how to get to immediately. For instance, I can understand that I can shortcut some of the loops if I know that the new 'window' has a smaller number at the front/back than the previous 'window'. I mean if the last 'window' was: [2,3,2] and the next is: [3,2,1] I can tell that the first element that was replaced with the next element is smaller and cannot add up to a larger sum (replacing a 2 with a 1). I don't know how to hold onto the elements in a way that would make sense to me right away so I've put that off for now.
My first iteration of the code was using a For loop and a variable holding the 'largest sum'. I got the structure of that done but then had to figure out the way to get the next X elements.
Creating a function outline:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = 0D;
for (int i = 0; i < nums.Length - windowSize; i++)
{
//need to get next windowSize number of elements
}
return largestSum / windowSize;
}
I decided another For loop from 0 to windowSize would do that and tried to implement that. I quickly realized that I didn't have a way to actually store the values of the elements to sum them up. I created an list<int> of length windowSize to do that. I used Sum() on the list and if it was larger than the previous largestSum I kept it and went to the next iteration until it was done.
Iteration 1:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = 0D;
for (int i = 0; i < nums.Length - windowSize; i++)
{
List<int> elements = new List<int>(windowSize);
for (int x = 0; x < windowSize; x++)
{
elements.Add(x);
}
if (elements.Sum() > largestSum)
{
largestSum = elements.Sum();
}
}
return largestSum / windowSize;
}
I realized pretty fast when I tested that I forgot to actually get the elements and was adding the inner loop counter! After that embarassing mistake I grabbed the element from the array.
Iteration 2:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = 0D;
for (int i = 0; i < nums.Length - windowSize; i++)
{
List<int> elements = new List<int>(windowSize);
for (int x = 0; x < windowSize; x++)
{
elements.Add(nums[i+x]); //get outer loop to inner loop; 0+0, 0+1, etc 1+0, 1+1, etc
}
if (elements.Sum() > largestSum)
{
largestSum = elements.Sum();
}
}
return largestSum / windowSize;
}
This iteration saw that the first test case was right but the second returned zero instead of 5.00. I changed the first loop to be "<=" instead of "<" because I thought that maybe the "array.Length() - windowSize" was returning zero elements (no loop) if the size was one and maybe I could just try that to see if it was the case.
Iteration 3:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = 0D;
for (int i = 0; i <= nums.Length - windowSize; i++) // <----- changed from "<" to "<="
{
List<int> elements = new List<int>(windowSize);
for (int x = 0; x < windowSize; x++)
{
elements.Add(nums[i+x]); //get outer loop to inner loop; 0+0, 0+1, etc 1+0, 1+1, etc
}
if (elements.Sum() > largestSum)
{
largestSum = elements.Sum();
}
}
return largestSum / windowSize;
}
The results lined up with the two test cases given so I made a couple of test cases for myself to verify.
For reference this is how I called my function:
Console.WriteLine(MaxAve(new int[] { 1, 12, -5, -6, 50, 3 }, 4)); //12.75
Console.WriteLine(MaxAve(new int[] { 5 }, 1)); //5.00
Console.WriteLine(MaxAve(new int[] { 1, 2, 3, 4 , 3 }, 2)); //3.5
Console.WriteLine(MaxAve(new int[] { 1, 10 ,3 , 3, 5, 6 }, 2)); //6.5
It might not be simple or elegant or whatever but it works. The test cases also did return what I expected. I submitted the code to see if it passed the test cases I couldn't see.
The results were that the test case ([-1], 1) returned 0 instead of -1, meaning it failed.
I noticed right away that this is probably because I set the default largestSum to zero and that would make it 'larger' when testing if it was the 'new largest sum'. I found that the default value was also zero. I set the initial value to the first element, thinking that if there are no elements it's going to fail AND maybe there is a case where the first element is larger than the sum of the window. I tried it anyways since I didn't have a test case that would fail that currently. I submitted that code and got the wrong answer again. The test case made it easy to see why! The first element was a large number and the expected average was a negative number.
My next iteration I set the largestSum to a nullable double and changed my conditions to make sure it gets set if it's null or the sum is larger. This didn't work because I couldn't get the double to be null to start (so that it's not a zero), meaning I couldn't just check if the value was set (yet) to set the first sum. I eventually figured out I didn't need a nullable double at all! I set the initial value to double.NaN and check if it's equal to that (first sum) OR if the new sum is larger than it. My test cases all passed so I submitted this code.
Iteration 4:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = double.NaN;
for (int i = 0; i <= nums.Length - windowSize; i++)
{
List<int> elements = new List<int>(windowSize);
for (int x = 0; x < windowSize; x++)
{
elements.Add(nums[i+x]); //get outer loop to inner loop; 0+0, 0+1, etc 1+0, 1+1, etc
}
if (largestSum.Equals(double.NaN) || elements.Sum() >= largestSum)
{
largestSum = elements.Sum();
}
}
return largestSum / windowSize;
}
if (largestSum.Equals(double.NaN) || elements.Sum() >= largestSum)
{
largestSum = elements.Sum();
}
}
return largestSum / windowSize;
}
This time the results were: "time limit exceeded" on two test cases. The first I just ran again and it got past it, but the second was ~1750 windowSize and I couldn't get past this. This is obviously because I'm using a loop in a loop but I don't have a way to write this without that. My code runs in my environment but since I'm unable to refactor to be better I cannot finish this one on my own.
I then had an idea. What if I just Take from the current index to the desired windowSize (get a range of values). I found that I could get the range if I converted the array to a list<int> and then used LINQ to GetRange(index, windowSize) and then did Sum() on that. This would mean I didn't have to write the inner loop because LINQ is doing that work, right?
Iteration 5:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = double.NaN;
List<int> tmpnums = nums.ToList();
for (int i = 0; i <= nums.Length - windowSize; i++)
{
if (largestSum.Equals(double.NaN) || tmpnums.GetRange(i, windowSize).Sum() > largestSum)
{
largestSum = tmpnums.GetRange(i, windowSize).Sum();
}
}
return largestSum / windowSize;
}
Unfortunately this still exceeded the time limit. This is where I had to go to the comments and hope that somebody explained their code. If there was none then I'd look at a solution and see if I could figure it out. Unfortunately none of the writeups that I saw were in C#, they were Python but I don't know that well enough to see it. I looked at the most viewed solution under C# code and found out where I went wrong.
The code (https://leetcode.com/problems/maximum-average-subarray-i/solutions/3601128/beats-100-in-time/?envType=study-plan-v2&envId=leetcode-75) is:
public double FindMaxAverage(int[] nums, int k) {
double sum = 0, avg = 0;
for(int i = 0; i < k; i++) sum += nums[i];
avg = sum / k;
for(int i = k; i < nums.Length; i++)
{
sum = sum + nums[i] - nums [i - k];
if(avg < sum / k) avg = sum / k;
}
return avg;
}
I have converted my code to this as follows:
static public double MaxAve(int[] nums, int windowSize)
{
double largestSum = 0;
double tmpSum = 0;
//the default window is from start to windowSize
for (int i = 0; i < windowSize; i++)
{
largestSum += nums[i];
}
tmpSum = largestSum; //set the tmpSum to the current largest
//starting at the next window, no longer need to loop through the first windowSize elements!
for (int x = windowSize; x < nums.Length; x++)
{
//move over one, drop first element, add next element, if that new window's sum is larger, set the variable
tmpSum = tmpSum + nums[x] - nums[x - windowSize];
if (tmpSum > largestSum)
{
largestSum = tmpSum;
}
}
return largestSum / windowSize;
}
Where I went wrong is that the first loop will sum up the first window of elements. For 0-windowSize, sum it all up. That is the default sum. Then from the windowSize element onward check if the sum will be larger or smaller based on subtracting the element that dropped off and adding the next element. Basically checking if the next element will add or detract from the tmpSum when removing the first element. I didn't explain that well but instead of looping and grabbing EVERYTHING we just need to see if the one that dropped off and the one that was added improve the largestSum, which improves the average (when we return it). This code (obviously) was able to run and complete without timing out. It does leave me wondering if my code was accurate, but slow. At least with all the test cases that I timed out on (but worked in my environment), the results were the same!
I know I had the idea in the general direction but I do think I don't know enough of the basics (or not so basics?) of math to have figured it out. I think I never would have stumbled into the solution on my own even though I do know simple addition, I likely never would have tried a separate loop and kept a rolling (is that the right word for a window?) sum as I did a second loop.
If you've made it this far I do have to apologize for the formatting in the code. It looks much better when it's properly indented and all that but I am not taking the effort to do all that when it isn't that big of a deal.
Related Posts:
Previous:
Are You Still There?