Merge Intervals Leetcode Problem 56 [Python Solution]

The Merge Intervals LeetCode problem, In this LeetCode challenge, we’re given an array of intervals, where each interval is represented as [start, end].

Our goal is to merge all overlapping intervals and return an array containing the non-overlapping intervals that cover the entire input.

Let’s dive into the details and explore a Python solution to this problem.

Problem Overview

Imagine you have a list of intervals, and each interval represents a time period, a class schedule, a meeting, or any scenario with a start and end time.

When these intervals overlap, it makes sense to merge them into a single interval for clarity and efficiency.

Here’s an example to illustrate the problem:

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, we can merge them into [1,6].

The remaining two intervals [8,10] and [15,18] are non-overlapping, so they remain as they are.

Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping, and they are merged into a single interval [1,5].

Understanding the Constraints

Before we delve into the solution, let’s understand the constraints of this problem:

• 1 <= intervals.length <= 10^4: This tells us that the number of intervals can be quite large.
• intervals[i].length == 2: Each interval is represented as a pair [start, end].
• 0 <= starti <= endi <= 10^4: The start and end values of the intervals are within a reasonable range.

Now that we’ve established the problem’s context and constraints, let’s explore a Python solution.

Merge Intervals LeetCode Problem Solution

1. Bruteforce Approach

One way to solve this problem is by using a straightforward brute-force approach.

We can start with an empty list for the output and iterate through each interval in the input list.

For each interval, we check if it overlaps with any of the previously added intervals in the output list.

If it does, we merge the overlapping intervals.

Otherwise, we add the interval to the output list.

Here’s a Python implementation of this approach:

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    # Sort intervals by their start values
    intervals.sort(key=lambda pair: pair[0])
    output = [intervals[0]]  # Initialize the output with the first interval

    for start, end in intervals[1:]:
        lastEnd = output[-1][1]  # Get the end value of the last interval in the output

        if start <= lastEnd:
            # Merge the intervals
            output[-1][1] = max(lastEnd, end)
        else:
            output.append([start, end])  # Add the non-overlapping interval to the output

    return output

This solution first sorts the input list of intervals based on their start values.

Then, it iterates through the sorted intervals, either merging overlapping intervals or adding non-overlapping ones to the output list.

2. An Efficient Approach with Python

While the brute-force approach is effective, it can be optimized for efficiency.

The key insight here is that by sorting the intervals by their start values, we can simplify the merging process.

This approach has a time complexity of O(n log n), where n is the number of intervals.

Let’s implement this optimized approach in Python:

def merge(self, intervals: List[List[int]]) -> List[List[int]:
    # Sort intervals by their start values
    intervals.sort(key=lambda pair: pair[0])
    output = [intervals[0]]  # Initialize the output with the first interval

    for start, end in intervals[1:]:
        lastEnd = output[-1][1]  # Get the end value of the last interval in the output

        if start <= lastEnd:
            # Merge the intervals
            output[-1][1] = max(lastEnd, end)
        else:
            output.append([start, end])  # Add the non-overlapping interval to the output

    return output

This efficient approach ensures that the intervals are sorted by their start values, making it easier to detect and merge overlapping intervals.

Time and Space Complexity

Before we wrap up, let’s briefly discuss the time and space complexity of our solution.

Time Complexity: Sorting the input list of intervals takes O(n log n) time, where n is the number of intervals.

After sorting, iterating through the sorted intervals requires O(n) time.

Therefore, the overall time complexity is O(n log n).

Space Complexity: We use additional space to store the output, which can have up to n intervals.

So, the space complexity is O(n).

Reasoning Behind Our Approach

The key to solving the Merge Intervals problem efficiently is to sort the intervals by their start values.

This allows us to easily identify and merge overlapping intervals while iterating through the sorted list.

The reasoning behind this approach lies in the fact that if we have overlapping intervals, their start values will be close to each other in the sorted list.

By continuously comparing the end value of the most recently added interval in the output with the start value of the current interval, we can determine if they overlap.

If they do, we merge them by extending the end value to cover both intervals.

If they don’t overlap, we add the current interval to the output.

Sorting the intervals is a crucial step in this process.

Once sorted, we can traverse the list linearly, avoiding the need for nested loops and complex data structures.

This results in an efficient and elegant solution to the problem.

Related Interview Questions By Company:

• Non Overlapping Intervals LeetCode
• Number Of Longest Increasing Subsequence LeetCode
• Permutations II LeetCode

Related Interview Questions By Difficulty:

• Minimum Interval To Include Each Query LeetCode
• Meeting Rooms LeetCode
• Insert Interval LeetCode

Related Interview Questions By Category:

• Reverse Linked List II LeetCode
• Find Median From Data Stream LeetCode
• Spiral Matrix LeetCode

Conclusion

In this blog post, we’ve explored the Merge Intervals problem, provided an efficient Python solution, and discussed the reasoning behind our approach.

We hope this guide has been helpful for beginners looking to solve this problem on LeetCode.

If you found this content useful, please consider leaving a like and subscribing to our our platform.

Your support helps us create more educational content.

If you have any questions, suggestions, or would like to share your own solution, please feel free to comment below.

Sharing knowledge and learning together is what makes the programming community thrive.

Question Link

Happy coding!