LeetCode Entry
57. Insert Interval
Insert interval into a sorted intervals array
57. Insert Interval medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/541
Problem TLDR
Insert interval into a sorted intervals array #medium
Intuition
There are several ways to attack the problem:
- use single pointer and iterate once
- count prefix and suffix and the middle part
- same as previous, but use the Binary Search
The shortes code is prefix-suffix solution. But you will need to execute some examples to handle indices correctly. In the interview situation, it is better to start without the BinarySearch part.
Approach
To shorted the code let’s use some APIs:
- Kotlin:
asList,run,binarySearchBy - Rust:
binary_search_by_key,unwrap_or,take,chain,once
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\) for the result
Code
fun insert(intervals: Array<IntArray>, newInterval: IntArray) =
intervals.asList().run {
var l = binarySearchBy(newInterval[0]) { it[1] }; if (l < 0) l = -l - 1
var r = binarySearchBy(newInterval[1] + 1) { it[0] }; if (r < 0) r = -r - 1
val min = min(newInterval[0], (getOrNull(l) ?: newInterval)[0])
val max = max(newInterval[1], (getOrNull(r - 1) ?: newInterval)[1])
(take(l) + listOf(intArrayOf(min, max)) + drop(r)).toTypedArray()
}
pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
let l = match intervals.binary_search_by_key(&new_interval[0], |x| x[1]) {
Ok(pos) => pos, Err(pos) => pos };
let r = match intervals.binary_search_by_key(&(new_interval[1] + 1), |x| x[0]) {
Ok(pos) => pos, Err(pos) => pos };
let min_start = new_interval[0].min(intervals.get(l).unwrap_or(&new_interval)[0]);
let max_end = new_interval[1].max(intervals.get(r - 1).unwrap_or(&new_interval)[1]);
intervals.iter().take(l).cloned()
.chain(std::iter::once(vec![min_start, max_end]))
.chain(intervals.iter().skip(r).cloned()).collect()
}