Data Structures & Algorithms in Java – Intervals – Merge Intervals


Given an array of intervals , merge overlapping intervals and return the non overlapping array of intervals.

For example,

Given the array:


The output should be


Try out the solution here:


First sort the array , this makes it easier to merge overlapping intervals.

Once sorted , compare two successive intervals starting from the first. If they overlap merge them.


STEP 1: Sort the array of intervals based on the start value

STEP 2: Create an output array

STEP 3: Iterate through the array and for each interval , check if the start of the interval overlaps with the end of the previous interval, if so merge the two else add the new interval to the output (to merge , take the maximum of the end values of the two intervals and use that as the end value of the merged interval , start value remains the same as that of the previous interval).

For the first interval there wont be any previous interval so add it to the output.

STEP 4: Return the output array


class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(first,second) ->[0],second[0]));
        var output = new LinkedList<int[]>();
      for(int[] i:intervals){
           if(output.isEmpty() || output.getLast()[1] < i[0]){
                output.getLast()[1] = Math.max(output.getLast()[1],i[1]);
        return output.toArray(new int[output.size()][2]);

Time complexity is O(nlogn) since you do sorting first it takes O(nlogn) and then again you do a pass through the input array which takes O(n). Total time complexity can be considered as O(nlogn).

Space complexity is O(n) for the output array.

That’s it!



, ,



Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading