LeetCode 57. Insert Interval

November 12, 2024

This took me a long time to cover all cases.

Solution

1class Solution:
2    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
3        start, end = newInterval
4        inserted = False
5        res = []
6        for item in intervals:
7            if end < item[0]:
8                if not inserted:
9                    res.append([start, end])
10                    inserted = True
11                res.append(item)
12            elif end >= item[0] and end <= item[1]:
13                start = item[0] if item[0] < start else start
14                end = item[1]
15            elif start >= item[0] and end <= item[1]:
16                start, end = item
17                res.append([start, end])
18                inserted = True
19            elif start >= item[0] and start <= item[1] and end > item[1]:
20                start = item[0]
21            elif start > item[1]:
22                res.append(item)
23
24        if not inserted:
25            res.append([start, end])
26        return res

O(n) = n since we iterate over all elements once.

Improvements

This solution has the same complexity, but it is simpler thereby being more maintanable.

1class Solution:
2    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
3        res = []
4        n = len(intervals)
5
6        i = 0
7        while i < n and intervals[i][1] < newInterval[0]:
8            res.append(intervals[i])
9            i += 1
10
11        while i < n and newInterval[1] >= intervals[i][0]:
12            newInterval[0] = min(intervals[i][0], newInterval[0])
13            newInterval[1] = max(intervals[i][1], newInterval[1])
14            i += 1
15        
16        res.append(newInterval)
17        res.extend(intervals[i:])
18
19        return res

LeetCode 56. Merge Intervals

LeetCode 150. Evaluate Reverse Polish Notation