6
\$\begingroup\$

This is a task taken from Leetcode -

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

/** Explanation: Since intervals `[1,3]` and `[2,6]` overlap, merge them into `[1,6]`. */

Example 2:

Input: [[1,4],[4,5]]

Output: [[1,5]]

/** Explanation: Intervals `[1,4]` and `[4,5]` are considered overlapping. */

My imperative solution -

 /**
   * @param {number[][]} intervals
   * @return {number[][]}
   */
  var merge = function(intervals) {  
    const sortedIntervals = intervals.sort((a,b) => a[0] - b[0]);
    const newIntervals = [];

    for (let i = 0; i < intervals.length; i++) {
      if (!newIntervals.length || newIntervals[newIntervals.length - 1][1] < sortedIntervals[i][0]) {
        newIntervals.push(sortedIntervals[i]);
      } else {
        newIntervals[newIntervals.length - 1][1] = Math.max(newIntervals[newIntervals.length - 1][1], sortedIntervals[i][1]);
      }
    }
    return newIntervals;
  };

My functional solution -

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
function merge(intervals) {
  const mergeInterval = (ac, x) => (!ac.length || ac[ac.length - 1][1] < x[0]
    ? ac.push(x)
    : ac[ac.length - 1][1] = Math.max(ac[ac.length - 1][1], x[1]), ac);

  return intervals
    .sort((a,b) => a[0] - b[0])
    .reduce(mergeInterval, []);
};
\$\endgroup\$
  • \$\begingroup\$ While sorting intervals on first value suggests itself, I'm wondering if discarding/merging intervals during sort make a notable difference, and in what direction. (Obviously, it doesn't change a thing if no intervals get merged.) \$\endgroup\$ – greybeard Oct 1 at 18:07
4
\$\begingroup\$

The code is mostly readable and clear:

  • the variable names are descriptive (for the most part - x is a little unclear)
  • there is good use of const and let instead of var

Some of the lines are a little lengthy - the longest line appears to be 117 characters long (excluding indentation):

newIntervals[newIntervals.length - 1][1] = Math.max(newIntervals[newIntervals.length - 1][1], sortedIntervals[i][1]);

I considered suggesting that a for...of loop be used to replace the for loop in the imperative solution after seeing the suggestion to use arr.entries() in this answer which would allow the use of a variable like interval instead of sortedIntervals[i], though when comparing in FF and chrome with this jsPerf test it seems that would be slower and thus less optimal, perhaps because each iteration would have an added function call.

When intervals.sort() is called the array is sorted in-place so intervals could be used instead of sortedIntervals, however it does seem that using sortedIntervals. That would reduce the storage by \$O(n)\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.