O(n) time and O(1) space JavaScript solution, beats 80% solutions


  • 0
    J
    var insert = function(intervals, newInterval) {
        let n = intervals.length;
        if (n < 1) {
            return [newInterval];
        }
        // two pointers
        let start = n;
        let end = -1;
    
        // try to find positions where the newInterval should start and end
        for (let i = 0; i < n; i++) {
            if(start < n && end >= 0) break;
            if (start === n && intervals[i].end >= newInterval.start) {
                start = i;
            }
            if (end < 0 && intervals[n-i-1].start <= newInterval.end) {
                end = n-i-1;
            }
        }
    
        // merge newInterval with overlapping intervals
        let newStart = start < n ? Math.min(intervals[start].start, newInterval.start) : newInterval.start;
        let newEnd = end >= 0 ? Math.max(intervals[end].end, newInterval.end) : newInterval.end;
        let mergedInterval = new Interval(newStart, newEnd);
    
        // insert newInterval at position start and replace overlapped ones
        intervals.splice(start, end-start+1, mergedInterval);
        return intervals;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.