8
\$\begingroup\$

This code works, and solves the problem, but doesn't satisfy some time requirements, especially when the 'nums' array can have a length of over 1000. How can this be optimized?

Just reference: This function does x number of operations on any element in the nums array so that the sum of all elements in the final array is always as small as possible. As a result, you have to perform the operation on the elements with the highest values first.

function minSum(nums, x) {
    if (nums.length === 0) {
        return false;
    }
    function operation(max) { 
        let redcuedMax = Math.floor(max / 10);
        return redcuedMax
    }
    let ops = x;
    while (ops > 0) {
        let max = Math.max(...nums);
        const ofNumber = (element) => element >= max ;
        let maxIndex = nums.findIndex(ofNumber)
        let operated = operation(max);
        nums[maxIndex] = operated;
        ops--
    }
    return nums.reduce((prev,next) => prev + next, 0)
}

minSum([400,209,77], 4) //out: 31
minSum([5000,5000,5000,5000,5000,], 4) //out: 7000
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

First let me point out a few details.

Use const intead of let unless you are going to modify the value after initialization. You use it for the ofNumber variable, but there are more that deserve it.

But actually there's often no need to define a variable at all if it is used only once. Similarily, storing a return value to a variable and immediately returning that variable is redundant, just return the value returned by the function directly.

function operation(max) {
    return Math.floor(max / 10);
}

But you could also stay consistent with the ofNumber callback like this:

const operation = (max) => Math.floor(max / 10);

Another thing is that we usualy use for loop in theese cases.

for (let ops = x; ops > 0; --ops) {...}

Now, let's analyse the big-O time complexity of your algorithm. Adding a comment above each statement in your code. n=nums.length.

function minSum(nums, x) {
    // O(1)
    if (nums.length === 0) {
        return false;
    }
    function operation(max) {
        // O(1)
        let redcuedMax = Math.floor(max / 10);
        return redcuedMax
    }
    let ops = x;
    // O(x * inner)
    while (ops > 0) {
        // O(n)
        let max = Math.max(...nums);
        // O(1)
        const ofNumber = (element) => element >= max ;
        // O(n)
        let maxIndex = nums.findIndex(ofNumber)
        // O(1)
        let operated = operation(max);
        // O(1)
        nums[maxIndex] = operated;
        // O(1)
        ops--
    }
    // O(n)
    return nums.reduce((prev,next) => prev + next, 0)
}

That makes for O(x * n) in time. O(1) in space of course, because you are never making any copies of the array.

How can we optimize this?

Well first thing i see is that there are 2 O(n) operations in the loop body. Maybe we can find the maximum's element index in O(n).And if we do, we can access the maximum element in O(1). This optimization will be less efective if the input is sorted or almost sorted in descendant order, because the second O(n) operation is basically O(1) for such sorted input.

Another thing is that after the loop, there is another O(n) operation. Maybe we can keep track of the sum (updating it in O(1) time) ever since the first time we needed to scan the entire array. Although, this optimization is x times less significant, for small x it may help.

Of course, the most significant improvement can only arise from changing the entire algorithm's big-O complexity from O(x * n) to something with slower rate of change. Even if it costs us increased memory complexity to say O(n).

To do that we have to leave the code for now and let's think about the problem itself.

You wrote:

As a result, you have to perform the operation on the elements with the highest values first.

Good. But is there more? How many of the highest elements will you actually need?

At most x, right? Either the highest element divided by 10 remains the highest element, in which case you continue with that one, or the next highest element will become the current highest. So maybe we dont want to track just 1 highest element, but x of them. This may raise our memory complexity to O(min(x,n)), but that would be still a good tradeoff.

Well, and I think I will break off at this point. I don't wanna write it for you. I hope I gave you enough hints to come up with a faster solution on your own. Just one more thing to say, don't be afraid to use your own specialized loops in such optimizations even if it means your code will grow. It's always trade-offs. Time, space, readability/code size, ... you improve one, you loose on the other... well sometimes not if you got it very wrong on the first shot :D (not saying this is the case:)).

EDIT: I found this article (https://www.google.com/amp/s/www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/amp/) which shows several ways to find the x largest elements of an array, some of them seem to be faster then actually sorting the entire array in O(n * log(n)).

\$\endgroup\$
5
\$\begingroup\$
  • You can simplify the code (and maybe accelarate it) by not assigning variables for values that are used once.
  • spreading the nums array is slow (Math.max), see also. Math.max with spreading or the faster alternative (Math.max.apply) for a larger array (somewhere between 120.000 - 130.000 elements) will throw a Range Error, so use a loop for it.
  • reduce is (a lot) slower than a regular loop, so use a loop to determine the sum
  • Math.floor can be replaced by a bitwise operator (it's slightly faster)
  • Side note: alway use semicolons

The first snippet shows the aforementioned optimizations

const testLongerArray = [...Array(2000)].map((v, i) => i && i*10 || 1);
const testVeryLongArray = [...Array(200000)].map((v, i) => i && i*10 || 1);
console.log(minSum(testLongerArray, 600)); // out 10812701
console.log(minSum(testVeryLongArray, 1600)); // out 197130527201
console.log(minSum([209,400,77], 4)); //out: 31
console.log(minSum([5000,5000,5000,5000,5000,], 4)); //out: 7000

function maxValue(arr) {
  let max = 0;
  let i = arr.length;
  while (i--) {
    max = arr[i] > max && arr[i] || max;
  }
  return max;
};

function minSum(nums, x) {
    if (nums.length === 0) {
        return false;
    }
    const start = performance.now();
    
    while (x--) {
        // Note: a loop for max is the fastest
        // and for very large arrays spreading and Math.max.apply
        // will throw, so using the loop here
        const max = maxValue(nums);
        const maxIndex = nums.indexOf(max);
        //               ^ use indexOf
        nums[maxIndex] = (max / 10) | 0;
        //               ^ Math.floor replacement
    }
    
    // replace reduce with a loop
    let len = nums.length;
    let sum = 0;
    
    while (len--) {
      sum += nums[len];
    }

    return `sum: ${sum}, time: ${(performance.now() - start).toFixed(2)} ms`;
}

Now you don't have to iterate through the whole array. If you sort the input array descending, you can take a subset of the first [x length] elements of the sorted input array and perform the operation on the elements of that subset. Adding up the subset elements and the elements of the original sorted array minus its first x elements should give the desired result.

That's worked out in the second snippet. In both snippets the performance is timed, so you can compare both snippets (especially for the longer arrays).

const testLongerArray = [...Array(2000)].map((v, i) => i && i * 10 || 1);
const testVeryLongArray = [...Array(200000)].map((v, i) => i && i * 10 || 1);
console.log(minSum(testLongerArray, 600)); // out 10812701
console.log(minSum(testVeryLongArray, 1600)); // out 197130527201
console.log(minSum([209, 400, 77], 4)); //out: 31
console.log(minSum([5000, 5000, 5000, 5000, 5000, ], 4)); //out: 7000

function minSum(nums, x) {
  if (nums.length === 0) {
    return false;
  }
  const start = performance.now();
  const operation = v => (v / 10) | 0;
  nums.sort((a, b) => b - a);
  let subset = nums.slice(0, x);
  let sum = 0;
  nums = nums.slice(x);

  while (x--) {
    const maxVal = maxValue(subset);
    subset[subset.indexOf(maxVal)] = operation(maxVal);
  }
  nums = nums.concat(subset);
  x = nums.length;
  
  while (x--) {
    sum += nums[x];
  }

  return `sum: ${sum}, time: ${(performance.now() - start).toFixed(2)} ms`;
}

function maxValue(arr) {
  let max = 0;
  let i = arr.length;
  while (i--) {
    max = arr[i] > max && arr[i] || max;
  }
  return max;
}

\$\endgroup\$
5
  • \$\begingroup\$ Hey that's not very fair. I was trying to show the OP how to analyse And improve time complexity of his code without actually writing down the code for him. And you take it And write that code into your own answer? \$\endgroup\$
    – slepic
    Jun 21, 2020 at 3:35
  • \$\begingroup\$ Before we get into argument. I realize that you could have made that insight on your own without reading my answer first. But from the timeline we can see that it Is possible that you stole it from my answer, because you edited your answer to include that only after my answer was posted. Although I cannot prove you stole And you cannot prove you did not. And im actually not angry if you stole the idea. What i dont like Is that you spoil the Fun for OP to figure it out on his own using those hints because I believe that showing the thoughts Is gonna teach more then showing the optimized code. \$\endgroup\$
    – slepic
    Jun 21, 2020 at 4:06
  • \$\begingroup\$ I can't prove it either (and why should I have to?), but the second optimization was not based on your answer. It lasted a while because I was testing several ways to work it out in vscode. The benefit of wheter including worked out code in the answer or not is a matter of opinion (imho, pun intended). \$\endgroup\$
    – KooiInc
    Jun 21, 2020 at 7:47
  • \$\begingroup\$ It would be strange to ask you to prove it and at the same time say that it cannot be proven :) I'm just saying that it's rather unfortunate that I tried to make OP implement the theory, I layed out, himself. And you spoil it by providing a possible implementation. Unlike here on stack exchange, in practice a code review hardly ever includes new code, it usualy just points to places that deserve improvement. \$\endgroup\$
    – slepic
    Jun 21, 2020 at 8:14
  • \$\begingroup\$ Anyway, I'm not asking you to remove that snippet, nor attribute it to be baesd on my answer, nor anything like that. But if you could place a reference to my answer before continue reading that part of your answer, it would be nice :) \$\endgroup\$
    – slepic
    Jun 21, 2020 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.