skyline-pigeon.js

Object.defineProperty(Array.prototype, "first", {
  get: function() {
    return this[0];
  }
});

Object.defineProperty(Array.prototype, "last", {
  get: function() {
    return this[this.length - 1];
  }
});

const getSkyline = buildings => {
  return helper(buildings, 0, buildings.length - 1);
};

const helper = (buildings, lo, hi) => {
  if (lo > hi) {
    return [];
  }

  if (lo === hi) {
    return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]];
  }

  const mid = lo + Math.floor((hi - lo) / 2);
  const left = helper(buildings, lo, mid);
  const right = helper(buildings, mid + 1, hi);

  let h1 = 0;
  let h2 = 0;

  const result = [];

  while (left.length && right.length) {
    let x, h;

    if (left.first[0] < right.first[0]) {
      [x, h1] = left.shift();
    } else if (left.first[0] > right.first[0]) {
      [x, h2] = right.shift();
    } else {
      [x, h1] = left.shift();
      [x, h2] = right.shift();
    }

    h = Math.max(h1, h2);

    if (result.length === 0 || result.last[1] != h) {
      result.push([x, h]);
    }
  }

  while (left.length) {
    result.push(left.shift());
  }

  while (right.length) {
    result.push(right.shift());
  }

  return result;
};

const testCases = [
  [[], []],
  [[[0, 2, 3], [2, 5, 3]], [[0, 3], [5, 0]]],
  [[[1, 2, 1], [1, 2, 2], [1, 2, 3]], [[1, 3], [2, 0]]],
  [
    [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]],
    [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
  ]
];

testCases.forEach(([buildings, expected], index) => {
  getSkyline(buildings);
});