Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Merge Intervals | Leetcode 56 | Brute Force and Optimal
    Data Structures & Algorithms

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    codeanddebugBy codeanddebug7 July 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question to merge intervals on leetcode
    Share
    Facebook Twitter LinkedIn Pinterest Email

    If you want to master array problems, “Merge Intervals” is a must-know question! In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with comments, dry runs, and clear explanations.

    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.

    Here’s the [Problem Link] to begin with.

    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.

    Constraints:

    • 1 <= intervals.length <= 104
    • intervals[i].length == 2
    • 0 <= starti <= endi <= 104
    Contents:
    • Brute Force Solution
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Optimal Solution
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Final Thoughts

    Brute Force Solution

    Intuition and Approach

    Let’s solve the problem step by step in the simplest way:

    1. Sort the Intervals:
      Sorting helps us line up all intervals so that overlapping intervals are next to each other.
    2. Check Each Interval:
      For every interval, try to merge it with all future intervals that overlap with it.
    3. Skip Already Merged Intervals:
      If an interval is already covered by a previous merge, skip it.
    4. Why does this work?
      We check every possible overlap and merge accordingly. This ensures all intervals are merged correctly, but it’s not the most efficient.

    Code Implementation

    from typing import List
    
    class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            n = len(intervals)
            intervals.sort()                         # sort intervals by start time
            ans = []
            for i in range(n):
                start, end = intervals[i][0], intervals[i][1]   # current interval
    
                # skip if current interval is already merged
                if len(ans) != 0 and end <= ans[-1][1]:
                    continue
    
                # try to merge with future overlapping intervals
                for j in range(i + 1, n):
                    if intervals[j][0] <= end:                # overlap found
                        end = max(end, intervals[j][1])       # extend end to the farthest overlap
                    else:
                        break                                 # stop if no overlap
                ans.append([start, end])                      # add merged interval to answer
            return ans
    Python

    Code Explanation

    • First, we sort the intervals to make overlapping intervals adjacent.
    • For each interval, we check if it’s already merged; if so, we skip it.
    • Then, we look ahead to merge all intervals that overlap with the current one.
    • We add the merged interval to our answer list.

    Dry Run

    Input:
    intervals = [[1],,,]

    • After sorting: [[1],,,]
    • Start with . overlaps, so merge to .
    • does not overlap, so add .
    • does not overlap, so add .
    • Final output: [[1],,]

    Time and Space Complexity

    • Time Complexity: O(N^2)
      For each interval, we may check all future intervals.
    • Space Complexity: O(N)
      For the answer list.

    Conclusion

    The brute force approach is easy to understand but slow for large lists. It’s good for learning the basics of the problem.


    Optimal Solution

    Intuition and Approach

    We can solve this problem much faster by merging intervals as we go:

    1. Sort the Intervals:
      Sorting puts overlapping intervals next to each other.
    2. Merge on the Go:
      As we go through each interval, check if it overlaps with the last interval in our answer list. If it does, merge them. If not, add it as a new interval.
    3. Why does this work?
      After sorting, all overlaps are adjacent, so we only need to look at the last merged interval.

    Code Implementation

    from typing import List
    
    class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            n = len(intervals)
            intervals.sort()                              # sort intervals by start time
            ans = []
            for i in range(n):
                # if ans is empty or no overlap, add interval
                if len(ans) == 0 or intervals[i][0] > ans[-1][1]:
                    ans.append(intervals[i])
                else:
                    # merge with the last interval in ans
                    ans[-1][1] = max(ans[-1][1], intervals[i][1])
            return ans
    Python

    Code Explanation

    • We sort the intervals.
    • For each interval, if it doesn’t overlap with the last interval in the answer, we add it.
    • If it does overlap, we merge it with the last interval by updating the end value.

    Dry Run

    Input:
    intervals = [[1],,,]

    • After sorting: [[1],,,]
    • : add to answer → [[1]]
    • : overlaps with , merge to  → [[1]]
    • : no overlap, add → [[1],]
    • : no overlap, add → [[1],,]

    Time and Space Complexity

    • Time Complexity: O(N log N)
      Sorting dominates; merging is O(N).
    • Space Complexity: O(N)
      For the answer list.

    Conclusion

    The optimal solution is efficient and elegant. It’s the best approach for interviews and large datasets.

    Final Thoughts

    The “Merge Intervals” problem is a great example of how sorting and merging can simplify complex problems. Start with brute force to understand the basics, then use the optimal solution for best performance.

    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Array Hard
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleLargest Subarray with 0 Sum – GeeksforGeeks Solution Explained
    Next Article Merge Without Extra Space – GeeksforGeeks Solution Explained
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025
    Data Structures & Algorithms

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (99)
      • Beginner (44)
      • Expert (28)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    7 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.