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
Difficulty
and has an acceptance rate of about 46% (4+ million submissions).
Typical patterns to solve this problem:
- Array
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 56: Merge Intervals
- problem 2655: Find Maximal Uncovered Ranges
Solved On The Same Day
Extra
- 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