I'm trying to solve some 'hackerrank.com' coding challenges. I'm stuck on this one:
You will be given an array of integers arr and a single integer k. You must create an array arr' of length k from elements of arr such that its unfairness is minimized.
Unfairness is defined as max(arr') - min(arr')
The function should return the minimum possible unfairness
My code works fine for the majority of test cases. However, in three of those test cases - the ones where the size of arr and k is particularly huge - fail due to an excession of the given time limit.
How can I optimize the performance of my code? Thanks in advance
function maxMin(k, arr) {
// create array to push unfairness values to
var unfairnesses = [];
// sort given array in ascending order
arr.sort(function(a, b) {
return a - b;
});
// loop over sorted array
for(var i = 0; i < arr.length - k + 1; i++) {
// get array with the length of k at position i
var tempArr = arr.slice(i, i + k);
// determine Max and Min of the sliced array
var tempArrMax = Math.max(...tempArr);
var tempArrMin = Math.min(...tempArr);
// get unfairness of the sliced array
var thisUnfairness = tempArrMax - tempArrMin;
// push sliced-array-unfairness to unfairnesses array
unfairnesses.push(thisUnfairness);
}
// return minimal value of unfairnesses array
return Math.min(...unfairnesses);
}
The two first steps could be:
Math.max and Math.min - the first element of a slice is the smallest, the last is the largest.Math.max and Math.min calls, you can remove Array.prototype.slice call. Then you're left with a sort and a single pass over the array.To sort the array you're already looping one time over the whole thing. Then you're looping another time to figure out which one is max and which one is the minimum.
You're looping twice as you can only loop once if you do:
function minMax(array) {
const safeArray = array ?? []
// No max or min as array is empty
if(safeArray.length === 0)
return [undefined, undefined]
let max: number = Number.MIN_SAFE_INTEGER
let min: number = Number.MAX_SAFE_INTEGER
for(let item of safeArray) {
max = Math.max(item, max)
min = Math.min(item, min)
}
return [max, min]
}