LeetCode 56: Merge Intervals Explained | Java Code + Easy Walkthrough

Struggling with LeetCode 56: Merge Intervals? This guide walks you through an optimal solution using sorting and linear traversal to efficiently merge overlapping intervals. Whether you’re prepping for interviews or strengthening your algorithmic skills, this step-by-step breakdown will help you master the problem with confidence.

🚧 Problem Summary

You’re given an array of intervals intervals[i] = [start_i, end_i]. Your task is to merge all overlapping intervals and return an array of the resulting non-overlapping intervals.

Example:
Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Why? Intervals [1,3] and [2,6] overlap and get merged into [1,6].

💡 Core Idea: Sort and Merge

The most efficient approach is to:

1. Sort intervals by their start times.
2. Traverse the sorted list and merge overlapping intervals.
3. Build the merged list by checking overlap and updating the end time as needed.

🧠 Step-by-Step Example

Take input: [[1,3], [2,6], [8,10], [15,18]]

1. Sort Intervals → Already sorted by start time.
2. Initialize → Start with [1,3] in your merged list.
3. Compare [2,6] with [1,3] → They overlap → merge into [1,6].
4. Next, [8,10] doesn’t overlap with [1,6] → add to list.
5. [15,18] also doesn’t overlap → add to list.

✅ Final result: [[1,6], [8,10], [15,18]]

🧑‍💻 Java Code (Efficient & Clean)

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        // Step 1: Sort by start times
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        
        // Step 2: Traverse and merge
        for (int[] interval : intervals) {
            // If no overlap, add interval
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Overlap: merge by updating the end time
                merged.get(merged.size() - 1)[1] = 
                    Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        
        // Convert list to array
        return merged.toArray(new int[merged.size()][]);
    }
}

⚙️ Time & Space Complexity

• Time: O(n log n) – due to sorting.
• Space: O(n) – for the output list of merged intervals.

📌 Edge Cases to Consider

1. Nested Intervals: [[1,4], [2,3]] → merged into [[1,4]]
2. Single Interval: Return as-is.
3. Non-overlapping Intervals: Keep them separate.

🚀 Optimization Insight

• Sorting is Critical: Without it, you’d need to check every pair → O(n²) time.
• Greedy Merge: By always merging into the last interval, we avoid extra passes.

🔍 Visual Representation

Input:     [1,3] [2,6] [8,10] [15,18]
Step 1:    [1,6]          (merged [1,3] and [2,6])
Final:     [1,6] [8,10] [15,18]

🏁 Conclusion

The Merge Intervals problem is a great example of using sorting and greedy logic to streamline complex interval logic. Mastering this pattern prepares you for similar challenges like:

• Insert Interval (LeetCode 57)
• Meeting Rooms (LeetCode 252)
• Interval List Intersections (LeetCode 986)

Challenge: Try solving the next one – Interval List Intersections!

Keywords: merge intervals leetcode, leetcode 56 solution, overlapping intervals, java merge intervals, interval merging algorithm, greedy approach, sort intervals, interval problems, coding interview question, array merging logic

Keep practicing and you’ll crush any interval-based problem! 🔥 Happy coding!