MediumNo. 0057
Insert Interval — LeetCode 57 Python Solution
- Topics
- Array
- On study lists
- Blind 75, NeetCode 150, Grind 75 and Top Interview 150
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Example
- Input
- intervals = [[1,3],[6,9]], newInterval = [2,5]
- Output
- [[1,5],[6,9]]
Python solution
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
def merge(intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
ans = [intervals[0]]
for s, e in intervals[1:]:
if ans[-1][1] < s:
ans.append([s, e])
else:
ans[-1][1] = max(ans[-1][1], e)
return ans
intervals.append(newInterval)
return merge(intervals)Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
| 0717 | 1-bit and 2-bit Characters | Easy |
Frequently asked questions
- How hard is LeetCode 57. Insert Interval?
LeetCode 57. Insert Interval is rated Medium on LeetCode.
- What is the time complexity of LeetCode 57. Insert Interval?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 57. Insert Interval?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 57. Insert Interval cover?
LeetCode 57. Insert Interval is tagged Array on LeetCode.