leetcode day 29: insert interval big fail

I chose completely the wrong way to solve this problem.

Instead of eliminating all the elements that could not contain the inserted interval, I attempted to simultaneously inspect each interval while retaining the only interval and composing a new one. This led to deeply nested conditionals, and numerous flags attempting to track if I’d finished composing a new interval, had I inserted it, and so on.

This problem is really about figuring out the elements that cannot contribute to the merged interval, and skipping over them as fast as possible. So we have two assertions:

• The element strictly occurs before the new interval (end of the interval is < start of new interval)
• The element strictly occurs after the new interval (beginning of the interval is > end of the new interval)

With those in mind, the only thing we really have to do is collapse any intervals that start on or after the start of the new interval and end before or at the end of it. To collapse those intervals with the new interval, we simply have to keep taking the minimum of the start of the old or new interval as the start of the inserted interval, and the max of the end of the old or new interval as the end of the new one to stretch the new interval lower and higher as needed to fit.

Once the new stretched interval is computed (remember, because we continue collapsing until the next interval (if there is one) is strictly after the new interval, which is will always be if the end of the stretched interval is < the start of the next one), we can simply insert the stretched interval!

The finish appends the rest of the remaining items to the output, and then returns it.

func insert(intervals [][]int, newInterval []int) [][]int {
    // Interval belongs somewhere in the list.
    // Look for insert point for new interval
    output := [][]int{}
    
    // Assertion: if interval[i][1] < newInterval[0], this interval 
    //            occurs before the new interval.
    // I is NOT in the for so its value hangs around after the loop ends.
    i := 0
    for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
        output = append(output, intervals[i])
    }

    // At this point, the last interval in output is before or at the 
    // start of newinterval. collapse intervals until we find one that 
    // starts before thend of newinterval. i still points to the last
    // interval shifted.
    for ; i < len(intervals) && intervals[i][0] <= newInterval[1]; i++ {
        // adjust the start of the new interval to the earliest point
        if intervals[i][0] < newInterval[0] {
            newInterval[0] = intervals[i][0]
        }
        if newInterval[1] < intervals[i][1] {
            newInterval[1] = intervals[i][1]
        }
    }

    // add the stretched interval
    output = append(output, newInterval)

    // Copy anything left.
    for ; i  < len(intervals); i++ {
        output = append(output, intervals[i])
    }
    return output
}

I checked the solutions and found that there’s a function in the sort package named sort.Search that lets you construct an anonymous boolean function that is run over a sorted array to find the first item that meets the criterion specified by the function. So we can eliminate all of the explicit loops and write it like this:

func insert(intervals [][]int, newInterval []int) [][]int {
    n := len(intervals)

    // Find first interval starting strictly before the new one
    // so we can extract it with a slice. i-1 will be the first one
    // that starts at a value <= the start of the new interval,
    i := sort.Search(n, func(i int) bool {
       return intervals[i][0] > newInterval[0] 
    })

    // Find all intervals ending strictly after this one, same thing.
    // j will be the first one definitely ending after the end of the
    // new interval.
    j := sort.Search(n, func(j int) bool {
       return intervals[j][1] > newInterval[1]
    })

    // Collapse intervals. If we're inside the array, and
    // the LAST interval with a start <= the start of the
    // new interval has a start that is <= the end of that
    // interval, they overlap. Stretch the bottom of the new
    // interval down and delete the overlapped interval.
    if i-1 >= 0 && newInterval[0] <= intervals[i-1][1] {
        newInterval[0] = intervals[i-1][0]
        i--
    }

    // If we're inside the array, and the FIRST interval with
    // an end AFTER the end of the new interval has a start <=
    // the end of the new interval, then they overlap. Stretch the
    // top of the new interval up and discard the overlapped interval.
    if j < n && newInterval[1] >= intervals[j][0] {
        newInterval[1] = intervals[j][1]
        j++
    }

    return append(
        // the slice up to the last interval strictly ending before
        // the start of the new interval
        intervals[:i],            
        append(
            // the new, possibly stretched interval
            [][]int{newInterval}, 
            // the slice from the first interval strictly starting
            // after the end of the new interval
            intervals[j:]...)...)
}

Internally, sort.Search does a binary search for the criterion function, so it’s very efficient. (And I should go back to the binary search questions and see if I can solve them more easily with sort.Search!) However, thinking through the conditions is a bit of a beast. Unless you have very large arrays to work on, the triple for loop may be easier to code on the spot and get right. Given the major improvement in speed, it’s worth practicing with!

The sort.Search solution is very good: 94th percentile on speed, 92nd percentile on memory. Not surprising, as we’ve swapped the linear iteration over the intervals to a binary search, and we only compose the output array at the end with two appends.

Interestingly, the linear recomposition three-loop version is quite fast too! 95th percentile, though the memory usage is only about the 50th percentile. I’d say stick with that solution unless there’s a definite case for the harder-to-code one.

Lessons for me on this first “medium” problem, that I didn’t finish at all quickly? Spend more time thinking about how to eliminate data from the process. What is the fastest way to do that?

My “sort it into place and track everything” solution was too complicated by far. If the logic to iterate over an array starts getting deeply nested, you are doing it wrong.