What is the time complexity of Merge Intervals?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Merge Intervals?

This problem uses Array, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Merge Intervals?

Insight 1: Sorting the intervals by their start times is crucial for efficiently identifying and merging overlapping intervals. Insight 2: Iterating through the sorted intervals and comparing each interval with the last merged interval allows us to determine if an overlap exists.

Which companies ask LeetCode 56. Merge Intervals in interviews?

This problem is frequently asked at AMD, Accenture, Adobe, Agoda, Airbnb and 82 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Merge Intervals - LeetCode 56 Solution

Merge Intervals - Complete Solution Guide

Merge Intervals is LeetCode problem 56, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Exampl

Detailed Explanation

The problem asks us to take a list of intervals, where each interval is defined by a start and end point, and merge any overlapping intervals. The goal is to return a new list containing only the non-overlapping intervals that cover the same range as the original list. For example, if we have intervals [[1,3],[2,6],[8,10],[15,18]], the intervals [1,3] and [2,6] overlap, so they should be merged into [1,6]. The final result would be [[1,6],[8,10],[15,18]].

Solution Approach

The solution involves sorting the input intervals based on their starting points. After sorting, we iterate through the intervals, maintaining a 'merged' list. For each interval, we check if it overlaps with the last interval added to the 'merged' list. If they overlap, we extend the end of the last merged interval to cover the current interval. If they don't overlap, we add the current interval to the 'merged' list.

Step-by-Step Algorithm

Step 1: Sort the input `intervals` array in ascending order based on the start time of each interval.
Step 2: Initialize an empty list called `merged` to store the merged intervals.
Step 3: Iterate through the sorted `intervals` array.
Step 4: For each `interval`, check if the `merged` list is empty or if the current `interval`'s start time is greater than the end time of the last interval in the `merged` list (meaning no overlap).
Step 5: If there's no overlap, append the current `interval` to the `merged` list.
Step 6: If there is an overlap, update the end time of the last interval in the `merged` list to be the maximum of the current end time and the existing end time of the last merged interval.
Step 7: After iterating through all intervals, return the `merged` list.

Key Insights

Insight 1: Sorting the intervals by their start times is crucial for efficiently identifying and merging overlapping intervals.
Insight 2: Iterating through the sorted intervals and comparing each interval with the last merged interval allows us to determine if an overlap exists.
Insight 3: When merging, we only need to update the end point of the last merged interval to encompass the current interval's end point if it's greater.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Sorting.

Companies

Asked at: AMD, Accenture, Adobe, Agoda, Airbnb, Amazon, Anduril, Apple, Applied Intuition, Atlassian, Bloomberg, ByteDance, CARS24, Cadence, Capital One, Cisco, Citadel, ConsultAdd, CrowdStrike, Cruise, DE Shaw, Databricks, Deloitte, Disney, Docusign, Dropbox, EPAM Systems, Expedia, Flipkart, Goldman Sachs, Grammarly, Grubhub, Hubspot, IBM, IXL, Infosys, Instacart, J.P. Morgan, LinkedIn, MakeMyTrip, Media.net, Meta, Microsoft, Morgan Stanley, Moveworks, Netflix, Netskope, Nextdoor, Nielsen, Nutanix, Nvidia, Okta, Oracle, Ozon, Palantir Technologies, PayPal, PhonePe, Qualcomm, Ripple, Rivian, Roblox, Salesforce, Samsung, ServiceNow, Siemens, Snap, Snowflake, Synopsys, Tencent, Tesco, Tesla, TikTok, Turing, Uber, Visa, Walmart Labs, Wix, Workday, X, Yahoo, Yandex, Yelp, Zalando, Zepto, Zoho, athenahealth, razorpay.

Merge Intervals | LeetCode 56

Medium

Array Sorting

Time: O(n log n)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        
        // Sort intervals based on the start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            // If the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, simply append it.
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Otherwise, there is an overlap, so we merge the current and previous
                // intervals by updating the end of the previous interval.
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        
        return merged.toArray(new int[merged.size()][]);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 56: Merge Intervals - Detailed explanation and solution approaches.

Topics

Array Sorting

Companies

AMDAccentureAdobeAgodaAirbnbAmazonAndurilApple

Stats

Difficulty:Medium

Languages:4

Companies:87

Problem #:56

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Sort the input `intervals` array in ascending order based on the start time of each interval.
2
Step 2: Initialize an empty list called `merged` to store the merged intervals.
3
Step 3: Iterate through the sorted `intervals` array.
4
Step 4: For each `interval`, check if the `merged` list is empty or if the current `interval`'s start time is greater than the end time of the last interval in the `merged` list (meaning no overlap).
5
Step 5: If there's no overlap, append the current `interval` to the `merged` list.
6
Step 6: If there is an overlap, update the end time of the last interval in the `merged` list to be the maximum of the current end time and the existing end time of the last merged interval.
7
Step 7: After iterating through all intervals, return the `merged` list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the sorting algorithm, which typically has a time complexity of O(n log n). The space complexity is determined by the extra space used by the `merged` list, which, in the worst case, stores all the input intervals.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

No sorting (potentially slower)

Without sorting, you'd need to iterate through all possible pairs of intervals to check for overlaps. This would be less efficient.

Time: O(n^2)Space: O(n)

Trade-offs: This approach is only viable for small inputs. Sorting is essential for better performance with larger inputs.

✨

Key Insights

1Insight 1: Sorting the intervals by their start times is crucial for efficiently identifying and merging overlapping intervals.
2Insight 2: Iterating through the sorted intervals and comparing each interval with the last merged interval allows us to determine if an overlap exists.
3Insight 3: When merging, we only need to update the end point of the last merged interval to encompass the current interval's end point if it's greater.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty input list. The solution should return an empty list, which is handled by checking `if not intervals:` (or equivalent in other languages).
Edge case 2: Input list with only one interval. The solution will correctly return the list containing only that interval since there's nothing to merge.
Edge case 3: Overlapping intervals at the boundaries (e.g., [[1,4],[4,5]]). The condition `merged[-1][1] < interval[0]` ensures that these are considered overlapping, and the end is updated correctly.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the intervals before merging. This leads to incorrect results because the algorithm relies on the sorted order to identify overlaps correctly.

✗Common mistake 2: Incorrectly handling the overlap condition. It's important to ensure that the overlap check considers intervals that touch at the boundary, not just those that have a strict overlap.

✗Common mistake 3: Modifying intervals in place without creating a deep copy, which might lead to unintended side effects if the original input list is needed later.

✗Common mistake 4: Failing to allocate memory correctly in C. Memory management is crucial to avoid leaks and ensure proper program execution. Remember to free the allocated memory when it is no longer needed.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Calendar scheduling. This algorithm can be used to merge overlapping appointments and determine available time slots.

🏦Real-world scenario 2: Resource allocation. It can be used to merge overlapping resource requests to efficiently allocate resources.

🎮Real-world scenario 3: Data analysis. Merging overlapping intervals can be useful in analyzing time-series data or genomic data.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 27, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Merge Intervals"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether sorting techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?