LeetCode - Last Stone Weight

https://leetcode.com/problems/last-stone-weight/

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

Solution

Brute force solution

There is a solution with O(N^2*LogN) time complexity. Which is you try to sort the array, pick two largest and do the math. You will need to repeat this process until you get array with 0 or 1 element.

Better solution

For the brute force solution, the most time-consuming part is sorting the array to get two largest elements. We may to optimize this by using heap.

The idea of heap (in this case, we will use binary heap) is that heap is a completed binary tree and all node will have value larger than its children nodes value.

So with heap, we can transform the given input array into a heap. We try to pop 2 value out from the heap each time, do the math and insert new stone into the heap if necessary. We will repeat this process until heap has only 0 or 1 element.

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
func lastStoneWeight(stones []int) int {
h := newHeap()
for _, stone := range stones {
h.Push(stone)
}
for h.Size() > 1 {
stone1 := h.Pop()
stone2 := h.Pop()
if stone1 == stone2 {
continue
}
newStone := abs(stone1 - stone2)
h.Push(newStone)
}
if h.Size() == 0 {
return 0
}
return h.Pop()
}

func abs(v int) int {
if v < 0 {
return v*-1
}
return v
}

type heap struct {
number []int
}

func newHeap() *heap {
return &heap {
number: make([]int, 0),
}
}

func (h *heap) Upheap(idx int) {
if idx == 0 {
return
}
parent := (idx - 1)/2
if h.number[parent] < h.number[idx] {
swap(&h.number[parent], &h.number[idx])
h.Upheap(parent)
}
}

func (h *heap) Downheap(idx int) {
if idx > h.Size() - 1 {
return
}
leftChild := idx*2 + 1
rightChild := idx*2 + 2
largestIdx := idx
if (leftChild < h.Size() && h.number[leftChild] > h.number[largestIdx]) {
largestIdx = leftChild
}
if (rightChild < h.Size() && h.number[rightChild] > h.number[largestIdx]) {
largestIdx = rightChild
}
if (largestIdx != idx) {
swap(&h.number[idx], &h.number[largestIdx])
h.Downheap(largestIdx)
}
}

// Heap must not be empty
func (h *heap) Pop() int {
curLen := h.Size()
res := h.number[0]
h.number[0] = h.number[curLen-1]
h.number = h.number[:curLen-1]
h.Downheap(0)
return res
}

func (h *heap) Push(val int) {
h.number = append(h.number, val)
h.Upheap(len(h.number) - 1)
}

func (h *heap) Size() int {
return len(h.number)
}

func swap(a *int, b *int) {
*a, *b = *b, *a
}

After self-implementing heap, i figured out that golang support heap. But without generic support, i found the syntax is really weird…

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
import (
"container/heap"
)

func lastStoneWeight(stones []int) int {
h := &IntHeap{}
heap.Init(h)
for _, stone := range stones {
heap.Push(h, stone)
}
for h.Len() > 1 {
stone1 := heap.Pop(h).(int)
stone2 := heap.Pop(h).(int)
if stone1 == stone2 {
continue
}
newStone := abs(stone1 - stone2)
heap.Push(h, newStone)
}
if h.Len() == 0 {
return 0
}
return heap.Pop(h).(int)
}

func abs(v int) int {
if v < 0 {
return v*-1
}
return v
}



// An IntHeap is a max-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

The time complexity of this solution is O(N * LogN) since heap.Push and heap.Pop is O(LogN)


Support me via: https://ko-fi.com/iamquang95