Merge Intervals LeetCode Solution

Last updated on January 13th, 2025 at 09:51 pm

Here, we see a Merge Intervals LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Sort

Companies

Bloomberg, Facebook, Google, Linkedin, Microsoft, Twitter, Yelp

Level of Question

Medium

Merge Intervals LeetCode Solution

Merge Intervals LeetCode Solution

1. Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[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: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Merge Intervals”. This pattern is commonly used to solve problems where overlapping intervals need to be merged into a single interval or processed in a way that considers their overlaps.

3. Code Implementation in Different Languages

3.1 Merge Intervals C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<=1) return intervals;
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> output;
        output.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++) {
            if(output.back()[1] >= intervals[i][0]) output.back()[1] = max(output.back()[1] , intervals[i][1]);
            else output.push_back(intervals[i]); 
        }
        return output;        
    }
};

3.2 Merge Intervals Java

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0)
            return intervals;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> mergedIntervals = new LinkedList<>();
        for(int[] curr : intervals) {
            if(mergedIntervals.isEmpty() || mergedIntervals.getLast()[1] < curr[0])
                mergedIntervals.add(curr);
            else 
                mergedIntervals.getLast()[1] = Math.max(mergedIntervals.getLast()[1], curr[1]);
        }
        return mergedIntervals.toArray(new int[0][]);        
    }
}

3.3 Merge Intervals JavaScript

var merge = function(intervals) {
    if(!intervals.length) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    
    const result = [intervals[0]];
    
    for(let [start, end] of intervals) {
        const endPrev = result.at(-1)[1]
        if(start <= endPrev) result.at(-1)[1] = Math.max(end, endPrev);
        else result.push([start, end]);
    }
    return result; 
};

3.4 Merge Intervals Python

class Solution(object):
    def merge(self, intervals):
        START, END = 0, 1
        result = []
        intervals.sort( key = lambda x: (x[START], x[END] ) ) 
        for interval in intervals:
            if not result or ( result[-1][END] < interval[START] ):
                result.append( interval )
            else:
                result[-1][END] = max(result[-1][END], interval[END])
        return result

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n log n)O(n)
JavaO(n log n)O(n)
JavaScriptO(n log n)O(n)
PythonO(n log n)O(n)
  • The logic is identical across all four languages, with minor syntactic differences.
  • The use of sorting ensures that intervals are processed in the correct order, which is crucial for the merging logic.
  • The merging process is efficient, as it only requires a single pass through the sorted intervals.

Scroll to Top