Problem 57

Abstract / Summary

Given a list of non overlapping intervals and a new interval insert the new interval so the list remains sorted and non overlapping

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0057.py

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []

        pos = 0
        # outside, left => copy
        while pos < len(intervals) and intervals[pos][1] < newInterval[0]:
            result.append(intervals[pos])
            pos += 1

        # overlapping, left => merge
        while pos < len(intervals) and intervals[pos][0] < newInterval[0]:
            newInterval[0] = min(newInterval[0], intervals[pos][0])
            newInterval[1] = max(newInterval[1], intervals[pos][1])
            pos += 1

        # overlapping, right => merge
        while pos < len(intervals) and intervals[pos][0] <= newInterval[1]:
            newInterval[1] = max(newInterval[1], intervals[pos][1])
            pos += 1

        result.append(newInterval)

        # outside, right => copy
        while pos < len(intervals):
            result.append(intervals[pos])
            pos += 1

        return result
29 lines | 1011 bytes | submitted August 28, 2023 | GitHub   21% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 46% (4+ million submissions).

Typical patterns to solve this problem:
  • Array
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation provides a method to insert a new interval into a sorted list of non-overlapping intervals while preserving order and merging any overlaps. It proceeds in a single linear scan, building the result list incrementally. The algorithm respects the sorted nature of the input, handling intervals that lie completely to the left, those that intersect on the left side, those that intersect on the right side, and those that lie completely to the right of the new interval.

Initialization

The method begins by creating an empty list that will hold the final merged intervals. A position index is set to zero to track the current location in the original list.

result = []
pos = 0

Copying intervals that end before the new interval starts

The first loop advances through intervals whose end point is strictly less than the start of the new interval. Because these intervals cannot overlap with the new interval, they are copied directly to the result list.

while pos < len(intervals) and intervals[pos][1] < newInterval[0]:
    result.append(intervals[pos])
    pos += 1

Merging intervals that overlap on the left side

When an interval starts before the new interval but may extend into it, the algorithm merges by expanding the start of the new interval to the smallest start seen and the end to the largest end encountered so far. This loop stops as soon as an interval begins at or after the new interval’s start.

while pos < len(intervals) and intervals[pos][0] < newInterval[0]:
    newInterval[0] = min(newInterval[0], intervals[pos][0])
    newInterval[1] = max(newInterval[1], intervals[pos][1])
    pos += 1

Merging intervals that overlap on the right side

After the left-side merge, any interval whose start lies within the current merged range (including the case where the start equals the merged end) is merged by extending the end of the new interval as needed. The condition uses <= to capture intervals that touch the merged interval at its right boundary.

while pos < len(intervals) and intervals[pos][0] <= newInterval[1]:
    newInterval[1] = max(newInterval[1], intervals[pos][1])
    pos += 1

Inserting the merged interval

Once all overlapping intervals have been consumed, the merged interval-now representing the union of the original new interval and any intersecting intervals-is appended to the result list.

result.append(newInterval)

Copying the remaining intervals

The final loop copies any intervals that start after the merged interval’s end. These intervals are guaranteed not to overlap because the input list is sorted and all possible overlaps have already been merged.

while pos < len(intervals):
    result.append(intervals[pos])
    pos += 1

Edge-case handling

The code gracefully handles an empty input list; the initial loops are bypassed and the new interval is simply appended. When the new interval lies entirely before the first existing interval, the first loop copies nothing, the merge loops are skipped, and the new interval is placed at the front. Conversely, if the new interval lies after all existing intervals, the first three loops copy everything to the result, and the final loop adds the new interval at the end.

Fully overlapping scenarios, where the new interval completely covers one or more existing intervals, are collapsed into a single merged interval by the left-side and right-side merge loops. Adjacent intervals-where the end of one interval equals the start of another-are treated as overlapping on the right side because the condition intervals[pos][0] <= newInterval[1] includes equality, ensuring they are merged into a continuous block.

Performance optimizations

The algorithm achieves its work with a single pass over the input list, using a mutable index to avoid repeated slicing or indexing overhead. By updating the newInterval in place, it eliminates the need for auxiliary structures to track intermediate bounds. The result list is built incrementally, which avoids costly insertions in the middle of a list. Each interval is examined at most once, and the early exit from each loop as soon as its condition fails prevents unnecessary comparisons. This design leverages the pre-sorted property of the input to keep the runtime linear with respect to the number of intervals while maintaining a low constant factor.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long row of building blocks lined up on the floor. Each block covers a small space, like a piece of track that goes from one number to another. Now, you have one brand new, special block that needs to fit into that row.

First, you look at all the blocks that are already sitting to the left of where your new block goes. Since these blocks are safely away from your new one, you just pick them up and place them into your new pile one by one.

Next, you find the blocks that touch or overlap with your new block. Instead of leaving them separate, you join them together. You make your new block bigger so it stretches far enough to cover all the space that those overlapping blocks used to take up. You keep checking the next block to see if it touches your new, growing block until you find one that is too far away to connect.

Once your new block is as big as it needs to be, you place it into your pile.

Finally, you look at all the blocks that were sitting to the right of your new creation. Since they are all perfectly fine on their own, you just pick those up and add them to the end of your pile to finish the job. Everything is now neat and tidy in a single row.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.54 | σ = 1.08

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java C# Rust Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
fartem Ruby
fengvyi C++
fsq C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fartem Ruby
fengvyi C++
fsq C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
56 links | 40 authors | 11 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Insert Interval - Leetcode 57 - Python'
NeetCode 12 mins
Insert Interval - Leetcode 57 - Python
YouTube video 'insert interval | insert interval leetcode | leetcode 57 | array'
Naresh Gupta 10 mins
insert interval | insert interval leetcode | leetcode 57 | array
YouTube video 'Insert Interval | LeetCode 57 | C++, Java, Python'
Knowledge Center 20 mins
Insert Interval | LeetCode 57 | C++, Java, Python
YouTube video 'INSERT INTERVAL | LeetCode 57 | Hindi'
Pepcoding 49 mins
INSERT INTERVAL | LeetCode 57 | Hindi
YouTube video 'Insert Interval (LeetCode 57) } Full solution with different scenarios'
Nikhil Lohia 21 mins
Insert Interval (LeetCode 57) } Full solution with different scenarios
YouTube video '[Java] Leetcode 57. Insert Interval [Intervals #2]'
Eric Programming 12 mins
[Java] Leetcode 57. Insert Interval [Intervals #2]
YouTube video '57. Insert Interval | 56. Merge Intervals | 2 Approaches'
Aryan Mittal 28 mins
57. Insert Interval | 56. Merge Intervals | 2 Approaches
YouTube video 'LeetCode 57. Insert Interval Explanation and Solution'
happygirlzt 6 mins
LeetCode 57. Insert Interval Explanation and Solution
YouTube video 'LeetCode 57: Insert Interval | Coding Interview'
Algo Engine 6 mins
LeetCode 57: Insert Interval | Coding Interview
YouTube video 'INSERT INTERVAL | LEETCODE 57 | PYTHON SOLUTION'
Cracking FAANG 17 mins
INSERT INTERVAL | LEETCODE 57 | PYTHON SOLUTION
YouTube video 'Q7. Insert Interval | Leetcode 57 | Array questions for Frontend Interview | DSA in JS'
JsCafe 16 mins
Q7. Insert Interval | Leetcode 57 | Array questions for Frontend Interview | DSA in JS
YouTube video 'Insert Interval - LeetCode 57 - Python #blind75 #leetcode'
Deepti Talesra 12 mins
Insert Interval - LeetCode 57 - Python #blind75 #leetcode
YouTube video '57. Insert Interval | LEETCODE MEDIUM | TOP INTERVIEW PROBLEM'
code Explainer 9 mins
57. Insert Interval | LEETCODE MEDIUM | TOP INTERVIEW PROBLEM
YouTube video 'LeetCode 57. Insert Interval - Interview Prep Ep 132'
Fisher Coder 12 mins
LeetCode 57. Insert Interval - Interview Prep Ep 132
YouTube video '57. Insert Interval | JavaScript | Simple Solution | O(n) Time Complexity | LeetCode Daily Challenge'
LeetCodeWithMonu 22 mins
57. Insert Interval | JavaScript | Simple Solution | O(n) Time Complexity | LeetCode Daily Challenge
YouTube video 'Daily Leetcode #1021: Jan 16, 2023 - 57. Insert Interval'
Programming Live with Larry 19 mins
Daily Leetcode #1021: Jan 16, 2023 - 57. Insert Interval
YouTube video '57. Insert Interval | March | Java | C++'
Mayur Programming Club 19 mins
57. Insert Interval | March | Java | C++
YouTube video '57 || Insert Interval || Leetcode Daily Challenge'
CodeFreaks 11 mins
57 || Insert Interval || Leetcode Daily Challenge
YouTube video 'LeetCode Problem 57: Insert Interval in Java - FAANG Coding Interview Questions - Blind 75'
KeyStrokes 22 mins
LeetCode Problem 57: Insert Interval in Java - FAANG Coding Interview Questions - Blind 75
YouTube video 'Daily Leetcode #1447: Mar 17, 2024 - 57. Insert Interval'
Programming Live with Larry 31 mins
Daily Leetcode #1447: Mar 17, 2024 - 57. Insert Interval
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

1 easy 1 medium
3 solutions   August 28, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality