What is the time complexity of Insert Interval?

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

What data structures are used to solve Insert Interval?

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

What are the key insights for solving Insert Interval?

Insight 1: Since the intervals are sorted, we can iterate through them to find the correct position for the new interval and merge any overlapping intervals efficiently. Insight 2: The key is to identify the intervals that come completely before the new interval, the intervals that overlap with the new interval (and need merging), and the intervals that come completely after the new interval.

Which companies ask LeetCode 57. Insert Interval in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Google and 10 more companies.

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

Insert Interval - LeetCode 57 Solution

Insert Interval - Complete Solution Guide

Insert Interval is LeetCode problem 57, 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

You are given an array of non-overlapping intervals intervals where intervals[i] = [start i , end i ] represent the start and the end of the i th interval and intervals is sorted in ascending order by start i . You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start i and intervals still does not have any overlapping intervals (merge overlappi

Detailed Explanation

The problem requires inserting a new interval into a sorted list of non-overlapping intervals. The goal is to maintain the sorted order and ensure that no intervals overlap. If the new interval overlaps with existing intervals, they need to be merged to form a single, non-overlapping interval. The input is a list of intervals, where each interval is a list of two integers representing the start and end points, and a new interval to be inserted. The output is the modified list of intervals after the insertion and merging process.

Solution Approach

The solution uses a single pass through the existing sorted intervals list. It identifies and adds intervals that come before the new interval without overlapping. It then merges all overlapping intervals with the new interval, updating the new interval's start and end points accordingly. Finally, it adds the merged new interval and the remaining intervals that come after the merged interval.

Step-by-Step Algorithm

Step 1: Initialize an empty result list to store the final intervals.
Step 2: Iterate through the input `intervals` list until we find an interval that either overlaps with `newInterval` or starts after `newInterval` ends.
Step 3: For each interval encountered before overlapping, add it directly to the `result` list.
Step 4: Once overlapping intervals are found, merge them by updating the `newInterval` start and end values. The start becomes the minimum of the current `newInterval` start and overlapping interval start. The end becomes the maximum of current `newInterval` end and overlapping interval end.
Step 5: After merging all overlapping intervals, add the updated `newInterval` to the `result` list.
Step 6: Add the remaining intervals (those after the merged section) to the `result` list.
Step 7: Return the `result` list containing the merged intervals.

Key Insights

Insight 1: Since the intervals are sorted, we can iterate through them to find the correct position for the new interval and merge any overlapping intervals efficiently.
Insight 2: The key is to identify the intervals that come completely before the new interval, the intervals that overlap with the new interval (and need merging), and the intervals that come completely after the new interval.
Insight 3: We can achieve this in a single pass through the sorted list of intervals.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Google, LinkedIn, Meta, Microsoft, MongoDB, Oracle, PhonePe, Tesco, TikTok, Uber, Yahoo.

Insert Interval | LeetCode 57

Medium

Array

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

Solution Code

Available in:

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

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i += 1;
        }

        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i += 1;
        }
        
        result.add(newInterval);

        while (i < n) {
            result.add(intervals[i]);
            i += 1;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 57: Insert Interval - Detailed explanation and solution approaches.

Topics

Array

Companies

AdobeAmazonAppleBloombergGoogleLinkedInMetaMicrosoft

Stats

Difficulty:Medium

Languages:4

Companies:15

Problem #:57

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: Initialize an empty result list to store the final intervals.
2
Step 2: Iterate through the input `intervals` list until we find an interval that either overlaps with `newInterval` or starts after `newInterval` ends.
3
Step 3: For each interval encountered before overlapping, add it directly to the `result` list.
4
Step 4: Once overlapping intervals are found, merge them by updating the `newInterval` start and end values. The start becomes the minimum of the current `newInterval` start and overlapping interval start. The end becomes the maximum of current `newInterval` end and overlapping interval end.
5
Step 5: After merging all overlapping intervals, add the updated `newInterval` to the `result` list.
6
Step 6: Add the remaining intervals (those after the merged section) to the `result` list.
7
Step 7: Return the `result` list containing the merged intervals.

💡

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)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the single pass through the intervals list. The space complexity comes from creating a new list to hold the merged intervals, which can grow to be the size of the original list plus one element.

📖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

Binary Search

Using binary search to find the insertion point of the new interval. Then, merge intervals around the insertion point. This might be considered if insertion point is much smaller than intervals length.

Time: O(log n + k), where n is the number of intervals, and k is the number of intervals that need to be mergedSpace: O(n)

Trade-offs: Binary search could be faster if the number of overlapping intervals is significantly smaller than the total number of intervals. However, the overhead of binary search and subsequent merging might make it less efficient than the linear scan in many cases. Also more complex to implement.

✨

Key Insights

1Insight 1: Since the intervals are sorted, we can iterate through them to find the correct position for the new interval and merge any overlapping intervals efficiently.
2Insight 2: The key is to identify the intervals that come completely before the new interval, the intervals that overlap with the new interval (and need merging), and the intervals that come completely after the new interval.
3Insight 3: We can achieve this in a single pass through the sorted list of intervals.

📚

Key Terms Explained

For Students

Array

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

Edge Cases

Edge case 1: `intervals` is empty. The code handles this gracefully by immediately adding `newInterval` to the result.
Edge case 2: `newInterval` is completely before all other intervals. The code correctly places `newInterval` at the beginning of the result.
Edge case 3: `newInterval` is completely after all other intervals. The code correctly places `newInterval` at the end of the result.
Edge case 4: `newInterval` overlaps with all other intervals. The merging process ensures a single interval covers the range of all original intervals and `newInterval`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where `newInterval` needs to be placed at the beginning or the end of the list.

✗Common mistake 2: Incorrectly merging overlapping intervals. It's crucial to take the minimum of the start times and the maximum of the end times.

✗Common mistake 3: Forgetting to add the remaining intervals after the merging is complete.

✗Common mistake 4: In languages like C, failing to properly allocate and deallocate memory for the result and its components.

✅

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 systems. This algorithm can be used to insert a new meeting into a calendar and merge it with any existing meetings that overlap.

🏦Real-world scenario 2: Resource allocation. When allocating resources (e.g., time slots, memory), this algorithm can be used to insert a new allocation request and merge it with any existing allocations that overlap to avoid conflicts.

💡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

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ 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 28, 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

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

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Insert Interval"?

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 standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?