Solving Popular Algorithms: Average Salary
I’ve had a hectic week moving into a new place (fourth and last time this year!) and during the chaos my algorithm practice has fallen to the wayside. So, in order to get back into the swing of things, I decided this week that we’d take a look at an easy beginner problem: Average Salary Excluding the Minimum and Maximum.
If you’re just starting out solving algorithms or like me have taken a bit of a break and need to get back on the wagon, then I’d definitely say this problem is a great place to start!
The Goal
The goal of this problem is, given an array of salaries, calculate the average salary minus the maximum salary and the minimum salary.
For example, if our initial salary array (s) is
s = [4000,3000,1000,2000]Then, our resulting average would be 2,500 as that would be 3,000 + 2,000/2, since 4,000 is the max and 1,000 is the min and both would thus be excluded for our average calculation.
The Solution: An Overview
This problem is honestly quite straightforward. To calculate an average, we add all the salaries together and divide by number of salaries. Personally, I’d say the most difficult part of this problem is not even finding the maximum and minimum values (that’s also quite simple), but figuring out how to remove them from our salaries array.
To do this, we will make use of a super, super helpful, built-in JS method called splice.
Splice allows us to add or remove values from an array. Unlike other JS methods like pop or shift, however, splice allows to add or remove elements from anywhere in the array. So, keep this method in mind as we get into solving this problem!
The Solution: Finding the max and min
The first step in this problem is twofold: finding both the maximum and minimum values in our array.
To do this, we will start by creating values called max and min and assinging them values:
let max = 0
let min = Number.MAX_SAFE_INTEGERSince, we are working with salaries, we can safely assume that we will never have a salary below zero, thus our initial max can be assigned to 0. We don’t, however, know how large our largest salary may be, thus we will assign min to Number.MAX_SAFE_INTEGER, a constant number that represents the maximum safe integer in JavaScript*.
*Although we don’t know how large the largest value in our array will be, since again our array is full of salaries, we can assume that it won’t fall into BigInt territory!
Now that we have created of max and min variables, we can use them to help us find the maximum and minimum values in our array.
For both max and min, we will iterate through our array and if a number is greater/smaller than max/min, we will reassign them value of max/min to said number. As our function iterates, it will reassign max and min appropriately until it has determined the true max and min values in our array.
for (let i = 0; i < s.length; i++) {
if (s[i] > max) {
max = s[i]
} if (s[i] < min) {
min = s[i]
}
}
Once we have determined the max and min values in our array, we can move on to the next step in our solution: removing the maximum and minimum values from our salaries array.
The Solution: Using Splice
With our max and min values found, we can now work on how to remove these values from our initial array. To do so, we will think back to the method I mentioned earlier: splice.
While I imagine there are multiple ways to successfully remove the max and min values from our array, I find splice to be the easiest to use and the most straightforward.
//removes the max value
for (let j = 0; j < s.length; j++) {
if (s[j] === max) {
s.splice(j, 1)
}}//removes the min value
for (let y = 0; y < s.length; y++) {
if (s[y] === min) {
s.splice(y, 1)
}
}
To work, splice needs at least two arguments. The first argument (here, it is signified by both j and y) is the index at which splice should start adding or removing elements. The second argument is the number of elements to be removed, in this case one for each max and min.
You may be wondering why I separated these functions into two separate functions (aka why can’t we just iterate through this function once) and the answer lies in the fact that splice is a destructive function that mutates our original array.
For example, if the first value in our array is either the max or min, then our function will remove it and then j (or y or whatever variable we are using) will increment and we will move onto the next value in our array. This would honestly work most of the time, unless, of course the second value in our array is also a max/min as once our first value is spliced, this second will become the first value in our array. Since j has incremented, our function will not look again at index 0 and thus our max/min value will not removed. By separating these two functions, we avoid this problem.
Now that our we successfully removed our max and min values from our array, we can move on to the final stage of this problem and calculate the average salary!
The Solution: Finding the Average
To calculate the average we will need another variable that I called total. Total will start with a value of 0. Then, each remaining salary in our array will be added to total. Finally, we will return total divided by the remaining number of salaries in our array.
let total = 0for (let x = 0; x < s.length; x++) {
total += s[x]
}return total/s.length
With that final step done, here is our completed solution:
avSal = (s) => {
let max = 0
let min = Number.MAX_SAFE_INTEGER let total = 0
//finds the max and min values
for (let i = 0; i < s.length; i++) {
if (s[i] > max) {
max = s[i]
} if (s[i] < min) {
min = s[i]
}
} //removes the max value
for (let j = 0; j < s.length; j++) {
if (s[j] === max) {
s.splice(j, 1)
} } //removes the min value
for (let y = 0; y < s.length; y++) {
if (s[y] === min) {
s.splice(y, 1)
}
} //calculates the average
for (let x = 0; x < s.length; x++) {
total += s[x]
} return total/s.length
}
A few notes on this solution
You might be wondering about the runtime complexity of this solution as it has a fair number of for loops. However, since none of these for loops are nested, this solution actually has a fairly good runtime of O(n) and in fact, according to leetcode, runs faster than 77% of all JS solutions!
Check out my blog on Big O if you’d like to know a bit more on how that works!
Like I said at the beginning of this blog, this is honestly a great practice problem for beginners. So if you are just starting out on your coding/algorithm journey, I’d definitely recommend giving the problem a go on your own!
Good luck and happy coding!
