LeetCode Entry

57. Insert Interval

16.01.2023 medium 2023 kotlin

fun insert(intervals: Array, newInterval: IntArray): Array {

57. Insert Interval medium

https://t.me/leetcode_daily_unstoppable/87

blog post

    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val res = mutableListOf<IntArray>()
        var added = false
        fun add() {
            if (!added) {
                added = true
                if (res.isNotEmpty() && res.last()[1] >= newInterval[0]) {
                    res.last()[1] = maxOf(res.last()[1], newInterval[1])
                } else res += newInterval
            }
        }
        intervals.forEach { interval ->
            if (newInterval[0] <= interval[0]) add()

            if (res.isNotEmpty() && res.last()[1] >= interval[0]) {
                res.last()[1] = maxOf(res.last()[1], interval[1])
            } else  res += interval
        }
        add()

        return res.toTypedArray()
    }

There is no magic, just be careful with corner cases.

Make another list, and iterate interval, merging them and adding at the same time.

• don’t forget to add newInterval if it is not added after iteration.

Space: O(N), Time: O(N)