1046. Last Stone Weight

Description

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks 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 1:

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.

 

Note:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

//this is just a really simple library of data structures that aren't implemented natively in JavaScript

//no frills MinHeap class for numbers
//might make a more generic version for any datatype if there's a need to
class MaxHeap {
  constructor(arr) {
    this.heap = [];
    if (arr) {
      for (let el of arr) {
        this.insert(el);
      }
    }
  }

  insert(value) {
    //add to end of array
    this.heap.push(value);

    //update structure by bubbling the value up
    let i = this.heap.length - 1;
    while (i > 0) {
      let currentValue = this.heap[i];
      let parentIndex = Math.floor((i - 1) / 2);
      let parentValue = this.heap[parentIndex];

      if (parentValue >= currentValue) {
        break;
      }
      //swap the two values
      this.heap[i] = parentValue;
      this.heap[parentIndex] = currentValue;
      //move to parent
      i = parentIndex;
    }
  }

  remove() {
    //remove final element and replace first element with it
    let max = this.heap[0];
    if (this.heap.length === 1) {
      this.heap[0] = null;
      return max;
    }
    this.heap[0] = this.heap.pop();

    let i = 0;
    while (i <= this.heap.length - 1) {
      let leftChildIndex = 2 * i + 1;
      let rightChildIndex = 2 * i + 2;
      let currentMaxIndex = i;

      //reminder: we check the child indicies to determine if we're a leaf node or not
      if (
        leftChildIndex <= this.heap.length &&
        this.heap[leftChildIndex] > this.heap[currentMaxIndex]
      ) {
        currentMaxIndex = leftChildIndex;
      }

      if (
        rightChildIndex <= this.heap.length &&
        this.heap[rightChildIndex] > this.heap[currentMaxIndex]
      ) {
        currentMaxIndex = rightChildIndex;
      }

      if (this.heap[i] >= this.heap[currentMaxIndex]) {
        break;
      }

      //swap the values
      if (currentMaxIndex !== i) {
        let temp = this.heap[currentMaxIndex];
        this.heap[currentMaxIndex] = this.heap[i];
        this.heap[i] = temp;

        //jump to whatever the larger child node was
        i = currentMaxIndex;
      }
    }

    return max;
  }

  //return max
  peek() {
    return this.heap[0];
  }
}

/**
 * @param {number[]} stones
 * @return {number}
 */
let lastStoneWeight = function(stones) {
  let heap = new MaxHeap(stones);
  let stone1 = heap.remove();
  let stone2 = heap.remove();

  while (stone1 && stone2) {
    //stone2 will always be smaller than stone1 because it's a heap
    //only have to check for equality
    if (stone1 !== stone2) {
      heap.insert(stone1 - stone2);
    }

    stone1 = heap.remove();
    stone2 = heap.remove();
  }

  return stone1;
};

Analysis

There was a hint to use a heap so that's what I used. I implemented a max heap and after that the problem became trivial. All we do is repeatedly remove the first two elements and insert their difference.

Let n be the number of elements passed in. Converting the array into a heap can is done in linear time but I'm not going to reiterate why because I remember the proof is long and and I don't feel like typing it up in LaTeX. It's a really nice proof though. I definitely did not appreciate it while I was still taking Data Structure in college. I didn't really get it until I took a few upper level math classes.

So anyway, to build the heap from the given input is O(n). Then for every two elements we remove, we add insert another into the heap. An upper bound for the number of insertions would be n-1 and an upper bound for the number of removals would be 2n-1. Each removal and insertion takes O(logn) time so the running time for this is O(nlog).