Find K Pairs with Smallest Sums LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} nums1
3
 * @param {number[]} nums2
4
 * @param {number} k
5
 * @return {number[][]}
6
 */
7

8
var kSmallestPairs = function (nums1, nums2, k) {
9
  const h = new MinHeap();
10
  h.sortKey = "id";
11
  for (i = 0; i < nums1.length; i++)
12
    h.push({ id: nums1[i] + nums2[0], i: i, j: 0 });
13
  let res = [];
14
  while (k--) {
15
    const t = h.pop();
16
    if (!t) return res;
17
    let { i, j } = t;
18
    res.push([nums1[i], nums2[j]]);
19
    if (j < nums2.length - 1)
20
      h.push({ id: nums1[i] + nums2[j + 1], i, j: j + 1 });
21
  }
22
  return res;
23
};
24

25
/*
26
This is a heap class that I wrote it myself,
27
neat? IDK
28
bad? IDK
29
bug? IDK (tested a few times for both min and max heaps)
30
so use it at your own risk :)
31
*/
32
class Heap {
33
  constructor(arr = [], sortKey = null) {
34
    this.heap = [];
35
    this.sortKey = sortKey;
36
    if (arr && arr.length) this.buildHeap(arr);
37
  }
38

39
  push(val) {
40
    this.heap.push(val);
41
    this.heapUp(this.heap.length - 1);
42
  }
43

44
  pop() {
45
    if (!this.heap.length) return null;
46
    if (this.heap.length == 1) return this.heap.pop();
47
    const res = this.heap[0];
48
    this.heap[0] = this.heap.pop();
49
    this.heapDown(0);
50
    return res;
51
  }
52

53
  id(i) {
54
    if (this.sortKey !== null) return this.heap[i][this.sortKey];
55
    return this.heap[i];
56
  }
57

58
  swap(i, j) {
59
    const t = this.heap[i];
60
    this.heap[i] = this.heap[j];
61
    this.heap[j] = t;
62
  }
63
  /*for child class to implement*/
64
  heapUp(i) {
65
    //heap up
66
  }
67

68
  heapDown(i) {
69
    //heap down
70
  }
71

72
  buildHeap(list) {
73
    //build heap
74
    for (let i of list) this.push(i);
75
  }
76

77
  toString() {
78
    return this.heap;
79
  }
80
}
81

82
class MinHeap extends Heap {
83
  heapUp(i) {
84
    const pI = (i - 1) >> 1;
85
    if (pI < 0) return;
86
    if (this.id(i) < this.id(pI)) {
87
      this.swap(i, pI);
88
      return this.heapUp(pI);
89
    }
90
  }
91

92
  heapDown(i) {
93
    const lI = i * 2 + 1;
94
    const rI = i * 2 + 2;
95
    if (lI >= this.heap.length) return;
96
    const v = Math.min(
97
      this.id(i),
98
      this.id(lI),
99
      rI >= this.heap.length ? Number.MAX_VALUE : this.id(rI)
100
    );
101
    if (v == this.id(i)) return;
102
    if (v == this.id(lI)) {
103
      this.swap(i, lI);
104
      return this.heapDown(lI);
105
    }
106
    this.swap(i, rI);
107
    this.heapDown(rI);
108
  }
109
}
110

111
class MaxHeap extends Heap {
112
  heapUp(i) {
113
    const pI = (i - 1) >> 1;
114
    if (pI < 0) return;
115
    if (this.id(i) > this.id(pI)) {
116
      this.swap(i, pI);
117
      return this.heapUp(pI);
118
    }
119
  }
120

121
  heapDown(i) {
122
    const lI = i * 2 + 1;
123
    const rI = i * 2 + 2;
124
    if (lI >= this.heap.length) return;
125
    const v = Math.max(
126
      this.id(i),
127
      this.id(lI),
128
      rI >= this.heap.length ? Number.MIN_VALUE : this.id(rI)
129
    );
130
    if (v == this.id(i)) return;
131
    if (v == this.id(lI)) {
132
      this.swap(i, lI);
133
      return this.heapDown(lI);
134
    }
135
    this.swap(i, rI);
136
    this.heapDown(rI);
137
  }
138
}