terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function(nums1, nums2, k) {
    let result = [];
    let minHeap = [];

    // 하나의 노드가 [합, num1 인덱스, num2 인덱스]를 담고 있고
    // 합을 비교하면서 Min Heap으로 Heapify를 한 뒤,
    // k번까지의 원소 중 인덱스를 활용하여 원소 pair를 반환하면 됨.
    for(let i = 0; i < nums1.length; i++){
        for(let j = 0; j < nums2.length; j++){
            minHeap.push([nums1[i] + nums2[j], [nums1[i], nums2[j]]]);
        }
    }

    heapify(minHeap)

    for(let i = 0; i < k; i++){
        if(minHeap.length < 1){
            break;
        }

        result.push(minHeap[0][1]);
        minHeap[0] = minHeap[minHeap.length - 1];
        minHeap.pop();
        bubbleDown(minHeap, 0);

    }

    return result;
};

function heapify(arr){
    for(let i = Math.floor((arr.length - 2) / 2); i >= 0; i--){
        bubbleDown(arr, i);
    }
}

function bubbleDown(arr, index){
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let lesserIndex = index;

    // 자식 노드가 없으면 연산하지 않아야한다.
    if(!arr[leftChildIndex] || !arr[rightChildIndex]){
        return;
    }

    // 왼쪽 자식 노드가 더 작은 경우
    if(arr[lesserIndex][0] > arr[leftChildIndex][0]){
        lesserIndex = leftChildIndex;
    }

    // 오른쪽 자식 노드가 더 작은 경우
    if(arr[lesserIndex][0] > arr[rightChildIndex][0]){
        lesserIndex = rightChildIndex;
    }

    if(lesserIndex !== index){
        swap(arr, index, lesserIndex);

        bubbleDown(arr, lesserIndex);
    }

}

function swap(arr, parentIdx, childIdx){
    [arr[childIdx], arr[parentIdx]] = [arr[parentIdx], arr[childIdx]];
}

Min Heap을 사용하는 방법으로 문제를 해결하고자 했다.
우선 가능한 상황에 대해서 원소의 합을 구하고, 그 때 사용된 값들을 배열로 만들어 저장한다.
Heap에서는 원소의 합을 사용해서 Heapify를 진행하며, 항상 최소값이 root가 되도록 한다.
그 후에는 root를 빼내고, 다시 Heapify를 하며 k번만큼 최소값을 제거한다.

그러나 이 방법은 테스트 케이스를 2/3 정도 통과하고 런타임 에러를 발생시켰다.
해당 에러에 대해서 찾아보니 힙 메모리가 오버되었을 때 발생한다고 하므로,
자주 생성되는 값들을 어떻게 하면 효율적으로 사용할지 고민할 필요가 있다.

solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function(nums1, nums2, k) {
  const result = [];

  if (nums1.length === 0 || nums2.length === 0) {
    return result;
  }

  const heap = new Heap();

  for (let i = 0; i < Math.min(nums1.length, k); i++) {
    heap.push([nums1[i] + nums2[0], i, 0]);
  }

  while (k > 0 && !heap.isEmpty()) {
    const [sum, i, j] = heap.pop();
    result.push([nums1[i], nums2[j]]);

    if (j + 1 < nums2.length) {
      heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
    }

    k--;
  }

  return result;
};

class Heap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.isEmpty()) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return root;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  bubbleUp(index) {
    const parentIdx = Math.floor((index - 1) / 2);

    if (parentIdx >= 0 && this.heap[index][0] < this.heap[parentIdx][0]) {
      [this.heap[index], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[index]];
      this.bubbleUp(parentIdx);
    }
  }

  bubbleDown(index) {
    const leftChildIdx = 2 * index + 1;
    const rightChildIdx = 2 * index + 2;
    let minIdx = index;

    if (leftChildIdx < this.heap.length && this.heap[leftChildIdx][0] < this.heap[minIdx][0]) {
      minIdx = leftChildIdx;
    }

    if (rightChildIdx < this.heap.length && this.heap[rightChildIdx][0] < this.heap[minIdx][0]) {
      minIdx = rightChildIdx;
    }

    if (minIdx !== index) {
      [this.heap[index], this.heap[minIdx]] = [this.heap[minIdx], this.heap[index]];
      this.bubbleDown(minIdx);
    }
  }
}

이번에는 class를 사용해서 모든 연산을 Heap과 관련되어 진행될 수 있게 수정했다.
처음에는 기본 연산을 통해서 배열을 만들고, 그 배열을 Min Heap으로 만드는 과정을 거쳤는데,
이번에는 push()를 통해 처음부터 Heap을 만들어서 사용하는 방법으로 변경했다.

이전 풀이와 가장 다른 점은 우선 순위를 어떻게 정하고, 사용하느냐이다.

for (let i = 0; i < Math.min(nums1.length, k); i++) {
  heap.push([nums1[i] + nums2[0], i, 0]);
}

이 코드를 보면 알 수 있듯이, nums2는 0번 인덱스로 고정한채로 nums1을 순회한다.
주어진 배열들은 오름차순 정렬된 것이기 때문에 nums1[0] + nums2[0]이 가장 작다는 것을 활용한 것이다.
이제 여기서 구해진 두 원소의 합을 기준으로 우선 순위를 나누게 된다.
그게 바로 아래 코드이다.

while (k > 0 && !heap.isEmpty()) {
  const [sum, i, j] = heap.pop();
  result.push([nums1[i], nums2[j]]);

  if (j + 1 < nums2.length) {
    heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
  }

  k--;
}

앞서 말했듯, 0,0 인덱스끼리의 합은 그 어떤 합보다 작기 때문에 바로 result에 넣어주고 시작한다.
그 후, 0번 인덱스에 멈춰있는 nums2를 증가시키면서 Heap에 넣어준다.
push() 또한 Heapify가 진행되므로 Min Heap을 구성하게 된다.
이 과정을 반복하면 결국 k번만큼 최소값을 추출하게 되어 정답을 얻을 수 있다.

Min Heap을 구성하는 기본적인 코드를 사용하여 class를 생성했기 때문에,
다른 분들도 같은 방법을 사용하셨다.