Merge arrays with overlapping values

Question

Im using Node.js. (...and underscore.js)

Consider this data structure

var numbers = [
  [10, 20]
  [30, 40]
  [40, 50]
  [45, 70]
  ... //Possibly more arrays (always contains two numbers)
]

numbers contain arrays that always contain number pairs. Think of these number pairs as "start" and "end". I want a function that takes numbers as argument, and loop trough its content, and if the "start" number of a pair overlap the "end" number of previous pair, these arrays is merged into one. For example this:

var numbers = [
  [10, 20]
  [19, 40]
  [40, 60]
  [70, 80]
]

Becomes this:

var numbers = [
  [10, 60] // First, second and third array is merged because of overlapping . 
  [70, 80]
]

Actually, I already have written a function for this that works fine, but feels a bit clunky.

I'm curious if some javascript wizard can dazzle me with a super elegant solution =).

You could instead show your own implementation and we could then show you how to improve it. In such a case, [Code Review](http://codereview.stackexchange.com/) would be a better place to post this. — Brett, Oct 15 '14 at 20:20
Aah... I did not know about Code Review. Thanks for telling me! — Anders Östman, Oct 15 '14 at 21:10
About posting my own solution... Actually, what I want – as a pretty fresh programmer – is evidence that show it's ok to solve code problems in different ways. Many times I found myself thinking about the ABSOLUTE solution, even though I somehow also believe that there are a myriad of ways that are equally good. By not posting my own solution, I might be presented to several different good solutions unbiased of my own. — Anders Östman, Oct 16 '14 at 08:47
Performance test of all the answer here: http://jsperf.com/merge-arrays-with-overlapping-values — Endless, Oct 29 '15 at 18:53

georg · Accepted Answer · 2017-11-19T18:51:54.480

18

Create an empty "result" array. Loop over the ranges array and either change the last item of the result or add the current range to it.

function merge(ranges) {
    var result = [], last;

    ranges.forEach(function (r) {
        if (!last || r[0] > last[1])
            result.push(last = r);
        else if (r[1] > last[1])
            last[1] = r[1];
    });

    return result;
}

r = [[10, 20], [19, 40], [40, 60], [70, 80]];
document.write(JSON.stringify(merge(r)));

This assumes that the source array is sorted, if it's not always the case, sort it before merging:

ranges.sort(function(a, b) { return a[0]-b[0] || a[1]-b[1] });

edited Nov 19 '17 at 18:51

answered Oct 15 '14 at 20:43

georg

211,518
52
313
390

This solution is very similar to my own. The only difference is that you mananged to reduce my two `if`s to only one. I had one outer `if` for checking `!result.length`. Your soultion helped me save four rows and some indentation =D. – Anders Östman Oct 16 '14 at 08:37
1

your solution doesnt work. try: [10,20],[11,12],[25,30] – YardenST Nov 19 '17 at 12:54
1

This method is dangerous because it changes the original array in the 8th line `last[1] = r[1];` – Alex Nov 22 '21 at 13:35
@georg result is an array, what's type of ```last` `` ? – Nishith Kant Chaturvedi Feb 09 '22 at 17:22

score 6 · Answer 2 · answered Oct 15 '14 at 20:30

I created a function which does what you want:

function merge(arr) {
    // copy and sort the array
    var result = arr.slice().sort(function(a, b) {
            return a[0] > b[0];
        }),
        i = 0;

    while(i < result.length - 1) {
        var current = result[i],
            next = result[i+1];

        // check if there is an overlapping
        if(current[1] >= next[0]) {
            current[1] = Math.max(current[1], next[1]);
            // remove next
            result.splice(i+1, 1);
        } else {
            // move to next
            i++;
        }
    }
    return result;
};

This function can be used this way:

var mergedNumbers = merge(numbers);

DEMO

This is great, because it works without forEach and without reduce, so I can use it in ExtendScript. Thanks! +1 — mdomino, Aug 16 '16 at 01:30
This method is dangerous because it changes the original array. What is clearly seen in "DEMO" — Alex, Nov 22 '21 at 09:43

Mike S · Answer 3 · 2014-10-15T21:15:05.823

As @Brett said, this might be a better fit for Code Review (just be sure to include your current implementation). If you post there, put a reference to it here somewhere and I'll move my answer.

Assuming that your numbers array is already sorted correctly, this function should do what you want:

function combine(numbers) {
    return numbers.reduce(function(combined, next) {
        if (!combined.length || combined[combined.length-1][1] < next[0]) combined.push(next);
        else {
            var prev = combined.pop();
            combined.push([prev[0], Math.max(prev[1], next[1])]);
        }
     return combined;
    }, []);
}  

var n = [[10, 20], [19, 40], [40, 60], [70, 80], [75, 76]];
var r = combine(n);
document.write('<pre>' + JSON.stringify(r) + '</pre>');

This "reduces" the original array to the new one using the following logic in the reduce function:

If this is the first pass or the last item does not overlap the current item, push the current item on to the combined array.
Otherwise:
1. pop the last item off the combined array.
2. push the combination of the last item and the current item on to the combined array.

score 1 · Answer 4 · answered Mar 28 '21 at 16:22

Simple concise JavaScript solution:

Algo

Sort the intervals by the start index in ascending order.
If the current interval overlap with the previous one, update the previous interval accordingly.
Otherwise, if the current start value > the previous end value), we put the interval in the result.

Implement code

var merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    let prev = merged[merged.length - 1];
    if (prev[1] >= start) {
      prev[1] = Math.max(prev[1], end);
    } else merged.push(intervals[i]);
  }
  return merged;
};

console.log(merge([[10, 20], [19, 40], [40, 60], [70, 80]]));

score 1 · Answer 5 · answered Nov 16 '21 at 10:06

let arr = [
  [1, 3],
  [2, 6],
  [5, 10],
  [15, 18],
  [18, 6],
];

const mergeoverlapping = (arr) => {
  if (arr.length < 2) return intervals;
  arr.sort((a, b) => a[0] - b[0]);
  let top = 0;
  let down = arr.length - 1;
  let left = 0;
  let temp = [];
  let right = arr[0].length - 1;
  let result = [];
  while (top + 1 <= down) {
    if (arr[top][right] >= arr[top + 1][left]) {
      arr[top + 1][left] = arr[top][left];
      temp = [arr[top + 1][left], arr[top + 1][right]];
    } else {
      result.push(temp);
      temp = arr[top + 1];
    }
    top++;
  }
  result.push(temp);
  console.log(result);
};

console.log(mergeoverlapping(arr));

As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). — Community, Nov 16 '21 at 11:23

score 0 · Answer 6 · answered Dec 15 '22 at 21:21

Expanding on accepted solution to provide more readability and a common use-case which is working with sets of integers where we want [[0,21],[22,42]] => [[0,42]]`:

const arr = [[21,21],[-21,1],[21,42],[5,10],[11,21]].sort((a, b) => a[0] - b[0]);
print(merge(arr));
print(merge(arr, true));

function merge(ranges, integers) { // range must be sorted by 1st element
  let prev = ranges[0];
  const result = [prev];

  for (let i = 1; i < ranges.length; i++) {
    const next = ranges[i];
    if (next[0] > prev[1] + (integers ? 1 : 0)) {
      result.push((prev = next));
      continue;
    }
    if (next[1] > prev[1]) prev[1] = next[1];
  }

  return result;
}

function print(value) {
  console.info(JSON.stringify(value))
}

Previous solutions are for closed intervals/ranges (where boundaries are included). This would be the approach for open intervals/ranges (boundaries not included):

const arr = [[21,21],[-21,1],[21,42],[5,10],[11,21]].filter(([a,b]) => a !== b).sort((a, b) => a[0] - b[0]); // 21 is not included
print(merge(arr));

function merge(ranges) { // range must be sorted by 1st element
  let prev = ranges[0];
  const result = [prev];

  for (let i = 1; i < ranges.length; i++) {
    const next = ranges[i];
    if (next[0] >= prev[1]) { // >= instead of >
      result.push((prev = next));
      continue;
    }
    if (next[1] > prev[1]) prev[1] = next[1];
  }

  return result;
}

function print(value) {
  console.info(JSON.stringify(value))
}

Merge arrays with overlapping values

6 Answers6

Linked