Heaviest Stone algorithm time complexity

Question

I implemented the heaviest stone algorithm, but I am not sure about its time complexity. I'm doing sort which is O(nlogn), but it' inside a while loop.

Problem:

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

My solution:

var lastStoneWeight = function(stones) {
    if(!stones || stones.length === 0)  return 0;
    if(stones.length === 1) return stones[0];
    
    stones.sort((a,b) => b-a);
    
    while(stones.length > 1) {
        const x = stones[0];
        const y = stones[1];
        stones.splice(0, 2);
        if(x !== y) {
            stones.push(x-y);
            if(stones.length === 1) return stones[0];
            stones.sort((a,b) => b-a);
        } 
    }
    
    return stones.length > 0 ? stones[0] : 0;
};

By the way, is there a way to have a better performance? Maybe not sorting?

Thanks

Answer 1

Issue(s)

1. You sort descending, but then take and assign the heaviest stone to x and the second heaviest stone to y whereas in your problem you state "...stones have weights x and y with x <= y".
2. Code isn't as DRY (Don't Repeat Yourself) as it could be.

Suggestions

1. Provide stones a default/initial empty array value.
2. Sort descending and assign const y = stones[0]; and const x = stones[1]; and push new value stones.push(y - x); to match problem. (Or normal sort ascending and take from array end, more on this later)
3. Use array destructuring to assign to x and y since array::splice returns an array of spliced out values.
4. Sort once at the beginning of each iteration.
5. Remove extraneous array length checks, let the while-loop condition handle it.

Code

const lastStoneWeight = (stones = []) => {
  if (!stones || !stones.length) return 0;

  while (stones.length > 1) {
    stones.sort((a, b) => a - b);
    const [x, y] = stones.splice(-2);
    if (x !== y) stones.push(y - x);
  }
  return stones[0] || 0;
};

If you can use Optional Chaining and Nullish Coalescing

const lastStoneWeight = (stones = []) => {
  if (!stones?.length) return 0;

  while (stones.length > 1) {
    stones.sort((a, b) => a - b);
    const [x, y] = stones.splice(-2);
    if (x !== y) stones.push(y - x);
  }
  return stones[0] ?? 0;
};

Here I use the default sort (ascending) and splice off the last two elements, removes need to shift entire forward 2 indices.

Using a Heap Data Structure

Since you ask about improved performance and the going suggestion is to use a heap/priority queue. This is a very similar implementation.

const lastStoneWeightHeap = (stones = []) => {
  if (!stones?.length) return 0;

  const heap = new PriorityQueue(); // <-- uses equivalent comparator as array::sort
  stones.forEach((stone) => heap.enq(stone)); // <-- populate heap

  while (heap.size() > 1) {
    const y = heap.deq();
    const x = heap.deq();
    if (x !== y) heap.enq(y - x);
  }
  return heap.size() ? heap.deq() : 0;
};

t1 is regular algorithm t2 is version using heap/priority queue data structure

10 iterations x 10000 runs
    # Elements  t0 avg      t1 avg 
1   8           0.00363     0.00106 
2   16          0.01036     0.00157 
3   32          0.01781     0.00224 
4   64          0.09148     0.00432 
5   128         0.22560     0.00944 
6   256         0.56833     0.01618 
7   512         2.37584     0.06091 
8   1024        8.78741     0.12614 
9   2048        34.29092    0.29697 
10  4096        130.50169   0.63872 

Notes:

• Time is in milliseconds

https://www.npmjs.com/package/priorityqueuejs

Conclusion

Using a heap data structure is orders of magnitude an improvement. With the naive implementation it is clearly at least an \$O(n^2)\$ complexity as each time the dataset size doubles (2x) the runtime roughly quadruples (~4x) whereas the implementation using a heap roughly only doubles (~2x) the runtime with each doubling of the dataset.

Performance Benchmarking

performanceBenchmark.js

const measurePerf = (fn, data, runs = 1e3) =>
  [...Array(runs).keys()]
    .map(() => {
      const start = performance.now();
      fn([...data]);
      const end = performance.now();
      return end - start;
    })
    .reduce((total, current) => total + current) / runs;

const toFixed = (val, fixed) =>
  Number.isFinite(val) ? Number(val).toFixed(fixed) : val;

export const benchmark = async ({
  functions = [],
  createRunData,
  iterations = 5,
  runs = 1e3,
  logIntermediateResults
}) => {
  logIntermediateResults && console.log(`${iterations} x ${runs}`);

  const results = [];

  logIntermediateResults &&
    console.log(
      `\t# Elements\t${functions.map((_, i) => `t${i} avg`).join("\t")}`
    );

  for (let i = 0; i < iterations; i++) {
    const data = createRunData(i);

    const res = await Promise.all(
      functions.map((fn) => measurePerf(fn, data, runs))
    );

    results.push(res);

    logIntermediateResults &&
      console.log(
        `${i + 1}\t${data.length}\t${res
          .map((t) => `${toFixed(t, 5)}`)
          .join("\t")}`
      );
  }

  return results;
};

Setup & benchmark

const ITERATIONS = 10;
const RUNS = 1e4;
const SEED = 8;

const functions = [
  lastStoneWeight,
  lastStoneWeightHeap,
];

const createRunData = (i) => {
  const dataLength = SEED << i;
  const stones = [...Array(dataLength).keys()].map(() =>
    Math.floor(Math.random() * dataLength)
  );
  return stones;
};

benchmark({
  functions,
  createRunData,
  iterations: ITERATIONS,
  runs: RUNS,
  logIntermediateResults: true
});

Extended heap implementation benchmark

15 x 10000 
    # Elements  t0 avg 
1   8           0.00100 
2   16          0.00171 
3   32          0.00242 
4   64          0.00434 
5   128         0.00933 
6   256         0.01825 
7   512         0.05681 
8   1024        0.13715 
9   2048        0.27621 
10  4096        0.59631 
11  8192        1.24577 
12  16384       4.75092 
13  32768       6.09799 
14  65536       13.07677 
15  131072      28.88058