Last Stone Weight

you are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [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 the last stone.

var lastStoneWeight = function (stones) {
  const stonesQueue = new MaxPriorityQueue();
  for (let i = 0; i < stones.length; i++) {
    stonesQueue.enqueue(stones[i]);
  }

  while (stonesQueue.size() > 1) {
    let y = stonesQueue.dequeue().element;
    let x = stonesQueue.dequeue().element;
    y = y - x;

    stonesQueue.enqueue(y);
  }

  return stonesQueue.dequeue().element;
};

// time: O(nlogn)
// space: O(n)

// Solution 2

/**
 * @param {number[]} stones
 * @return {number}
 */

class MaxHeap {
  constructor(values) {
    this.values = [null, ...values];
    this.heapify();
  }

  heapify() {
    for (let i = Math.floor(this.values.length / 2); i > 0; i--) {
      this.heapifyDown(i);
    }
  }

  addToHeap(val) {
    this.values.push(val);
    this.heapifyUp(this.values.length - 1);
  }

  heapifyUp(index) {
    let parentIndex = Math.floor(index / 2);
    while (this.values[parentIndex] !== null) {
      if (this.values[index] > this.values[parentIndex]) {
        let temp = this.values[index];
        this.values[index] = this.values[parentIndex];
        this.values[parentIndex] = temp;
      }
      index = parentIndex;
      parentIndex = Math.floor(index / 2);
    }
  }

  heapifyDown(index) {
    let leftChildIndex = 2 * index;
    let rightChildIndex = 2 * index + 1;
    let largerIndex;
    while (
      leftChildIndex < this.values.length ||
      rightChildIndex < this.values.length
    ) {
      if (leftChildIndex >= this.values.length) {
        largerIndex = rightChildIndex;
      } else if (rightChildIndex >= this.values.length) {
        largerIndex = leftChildIndex;
      } else {
        if (this.values[leftChildIndex] >= this.values[rightChildIndex]) {
          largerIndex = leftChildIndex;
        } else {
          largerIndex = rightChildIndex;
        }
      }
      if (this.values[index] < this.values[largerIndex]) {
        let temp = this.values[index];
        this.values[index] = this.values[largerIndex];
        this.values[largerIndex] = temp;
        index = largerIndex;
        leftChildIndex = 2 * index;
        rightChildIndex = 2 * index + 1;
      } else {
        break;
      }
    }
  }

  extractMaxValue() {
    let tempValue = this.values[1];
    this.values[1] = this.values[this.values.length - 1];
    this.values[this.values.length - 1] = tempValue;
    let maxValue = this.values.pop();
    this.heapifyDown(1);
    return maxValue;
  }
}

var lastStoneWeight = function (stones) {
  let maxHeap = new MaxHeap(stones);
  while (maxHeap.values.length > 2) {
    let max1 = maxHeap.extractMaxValue();
    let max2 = maxHeap.extractMaxValue();
    let absoluteDiff = Math.abs(max1 - max2);
    if (absoluteDiff) {
      maxHeap.addToHeap(absoluteDiff);
    }
  }
  if (maxHeap.values.length === 1) {
    return 0;
  }
  return maxHeap.values[1];
};

Blog

ZeeshanAli-0704

Join Our Newsletter. No Spam, Only the good stuff.

Related