Jobs

Interviews

Discussions

Merge Intervals

Medium

Roblox

0 views

Topics:

ArraysSorting

Given an array of intervals where intervals[i] = [start_i, end_i], 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.

Constraints:

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Merge Intervals

Medium

Roblox

0 views

Topics:

ArraysSorting

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 <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the start and end points of the intervals?
Can the input array `intervals` be empty or null?
If intervals overlap resulting in a single interval, should I represent that single interval or combine it with any subsequent overlapping intervals?
What should be returned if the input `intervals` array is already non-overlapping?
Is the input array sorted in any way, or is it unsorted? If unsorted, can I sort it?

Brute Force Solution

Approach

The brute force approach to merging intervals means comparing each interval with every other interval to see if they overlap. If any intervals overlap, we merge them, and then repeat the whole process from the start. This ensures that all possible merges are considered, eventually leaving us with a list of non-overlapping, merged intervals.

Here's how the algorithm would work step-by-step:

Take the first interval from your list.
Compare it to every other interval in the list.
If the first interval overlaps with any other interval, combine them into a single, bigger interval.
After checking the first interval with all other intervals, do the same thing with the second interval, then the third, and so on.
Keep repeating this process, comparing each interval to every other interval, until you go through the entire list and no more intervals can be merged.
Since merging intervals can create new overlaps, restart the entire process from the beginning after each merge.
Once you make a complete pass through the list without merging any intervals, you're done. The remaining intervals are the merged intervals.

Code Implementation

def merge_intervals_brute_force(intervals):
    merged = True
    while merged:
        merged = False
        interval_index = 0
        while interval_index < len(intervals):
            other_interval_index = interval_index + 1
            while other_interval_index < len(intervals):
                # Check for overlap, merge if found
                if (intervals[interval_index][1] >= intervals[other_interval_index][0] and
                        intervals[other_interval_index][1] >= intervals[interval_index][0]):

                    # Need to merge since intervals overlap
                    intervals[interval_index] = [
                        min(intervals[interval_index][0],
                            intervals[other_interval_index][0]),
                        max(intervals[interval_index][1],
                            intervals[other_interval_index][1])
                    ]

                    del intervals[other_interval_index]
                    merged = True
                    # Break to restart from the beginning of inner loop
                    break
                other_interval_index += 1
            # Break out of outer loop to restart entire process if merged
            if merged:
                break
            interval_index += 1
    return intervals

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through the list of n intervals, comparing each interval with every other interval. If an overlap is found, intervals are merged. Crucially, after each merge, the entire process restarts from the beginning to account for potential new overlaps. This means in the worst-case, where multiple merges are needed, the nested loops (for comparing each interval) run multiple times. This results in O(n * n) operations for the comparisons and merging in a single pass and, in the worst case, this is repeated n times leading to O(n * n * n) or O(n³) time complexity.

Space Complexity

O(1) – The provided brute force algorithm operates primarily in-place. While intervals might be modified, no additional data structures of significant size are allocated to store intermediate results or keep track of visited intervals. The comparisons and merges are done directly within the existing interval list. Therefore, the auxiliary space used remains constant, irrespective of the number of intervals (N).

Optimal Solution

Approach

The trick to solving this problem efficiently is to first arrange the intervals based on their start times. Then, we can go through them in order and merge them when they overlap, creating a new consolidated interval.

Here's how the algorithm would work step-by-step:

First, put all the intervals in order, from the one that starts earliest to the one that starts latest.
Begin with an empty list to hold our final, merged intervals.
Take the first interval from the sorted list and add it to our merged list.
Now, go through the remaining intervals one by one.
For each interval, check if it overlaps with the last interval we added to the merged list.
If they do overlap, combine them to create a bigger interval that covers both.
If they don't overlap, just add the new interval to the end of the merged list.
Keep doing this until you've gone through all the intervals. The merged list will then contain the final, non-overlapping intervals.

Code Implementation

def merge_intervals(intervals):
    # Sort intervals based on start times.
    intervals.sort(key=lambda interval: interval[0])

    merged_intervals = []

    # Add the first interval to the merged list.
    if intervals:
        merged_intervals.append(intervals[0])

    for interval in intervals[1:]:
        # Check for overlap with the last merged interval.
        if merged_intervals[-1][1] >= interval[0]:

            # Merge the intervals.
            merged_intervals[-1] = [merged_intervals[-1][0], max(merged_intervals[-1][1], interval[1])]

        else:
            # No overlap, add the interval to the merged list.
            merged_intervals.append(interval)

    return merged_intervals

Big(O) Analysis

Time Complexity

O(n log n) – The dominant cost comes from sorting the input intervals based on their start times, which takes O(n log n) time. The subsequent merging process iterates through the sorted intervals once. The merging process iterates through the sorted intervals once, comparing each interval to the last merged interval which takes O(n) time. Therefore, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The primary driver of space complexity is the 'merged list' that stores the resulting non-overlapping intervals. In the worst-case scenario, where none of the input intervals overlap, the merged list will contain all N input intervals. Thus, the auxiliary space used grows linearly with the number of input intervals, represented by N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input intervals array	Return an empty array since there are no intervals to merge.
Null input intervals array	Throw an IllegalArgumentException or return null after checking for null input.
Single interval in the input array	Return the input array as is, since there's nothing to merge.
Intervals with overlapping start and end values (e.g., [1, 1])	The algorithm should correctly merge or include these intervals without errors.
Intervals with negative start and end values	The algorithm should handle negative values correctly, assuming the comparison logic accounts for them.
Intervals already sorted in ascending order	The algorithm should still function correctly, potentially with improved performance if sorting is skipped or optimized.
Intervals sorted in descending order	The algorithm needs to correctly sort the intervals in ascending order to ensure proper merging.
Large range of interval values causing potential integer overflow	Use appropriate data types (e.g., long) to store interval boundaries to prevent potential integer overflows during calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the start and end points of the intervals?
Can the input array `intervals` be empty or null?
If intervals overlap resulting in a single interval, should I represent that single interval or combine it with any subsequent overlapping intervals?
What should be returned if the input `intervals` array is already non-overlapping?
Is the input array sorted in any way, or is it unsorted? If unsorted, can I sort it?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first interval from your list.
Compare it to every other interval in the list.
If the first interval overlaps with any other interval, combine them into a single, bigger interval.
After checking the first interval with all other intervals, do the same thing with the second interval, then the third, and so on.
Keep repeating this process, comparing each interval to every other interval, until you go through the entire list and no more intervals can be merged.
Since merging intervals can create new overlaps, restart the entire process from the beginning after each merge.
Once you make a complete pass through the list without merging any intervals, you're done. The remaining intervals are the merged intervals.

Code Implementation

def merge_intervals_brute_force(intervals):
    merged = True
    while merged:
        merged = False
        interval_index = 0
        while interval_index < len(intervals):
            other_interval_index = interval_index + 1
            while other_interval_index < len(intervals):
                # Check for overlap, merge if found
                if (intervals[interval_index][1] >= intervals[other_interval_index][0] and
                        intervals[other_interval_index][1] >= intervals[interval_index][0]):

                    # Need to merge since intervals overlap
                    intervals[interval_index] = [
                        min(intervals[interval_index][0],
                            intervals[other_interval_index][0]),
                        max(intervals[interval_index][1],
                            intervals[other_interval_index][1])
                    ]

                    del intervals[other_interval_index]
                    merged = True
                    # Break to restart from the beginning of inner loop
                    break
                other_interval_index += 1
            # Break out of outer loop to restart entire process if merged
            if merged:
                break
            interval_index += 1
    return intervals

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, put all the intervals in order, from the one that starts earliest to the one that starts latest.
Begin with an empty list to hold our final, merged intervals.
Take the first interval from the sorted list and add it to our merged list.
Now, go through the remaining intervals one by one.
For each interval, check if it overlaps with the last interval we added to the merged list.
If they do overlap, combine them to create a bigger interval that covers both.
If they don't overlap, just add the new interval to the end of the merged list.
Keep doing this until you've gone through all the intervals. The merged list will then contain the final, non-overlapping intervals.

Code Implementation

def merge_intervals(intervals):
    # Sort intervals based on start times.
    intervals.sort(key=lambda interval: interval[0])

    merged_intervals = []

    # Add the first interval to the merged list.
    if intervals:
        merged_intervals.append(intervals[0])

    for interval in intervals[1:]:
        # Check for overlap with the last merged interval.
        if merged_intervals[-1][1] >= interval[0]:

            # Merge the intervals.
            merged_intervals[-1] = [merged_intervals[-1][0], max(merged_intervals[-1][1], interval[1])]

        else:
            # No overlap, add the interval to the merged list.
            merged_intervals.append(interval)

    return merged_intervals

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input intervals array	Return an empty array since there are no intervals to merge.
Null input intervals array	Throw an IllegalArgumentException or return null after checking for null input.
Single interval in the input array	Return the input array as is, since there's nothing to merge.
Intervals with overlapping start and end values (e.g., [1, 1])	The algorithm should correctly merge or include these intervals without errors.
Intervals with negative start and end values	The algorithm should handle negative values correctly, assuming the comparison logic accounts for them.
Intervals already sorted in ascending order	The algorithm should still function correctly, potentially with improved performance if sorting is skipped or optimized.
Intervals sorted in descending order	The algorithm needs to correctly sort the intervals in ascending order to ensure proper merging.
Large range of interval values causing potential integer overflow	Use appropriate data types (e.g., long) to store interval boundaries to prevent potential integer overflows during calculations.