ZeeshanAli-0704

Posted on

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);
}
}

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) {