57. Insert Interval

Math

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Step 1: add all intervals that's before new interfal
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Step 2: combine all intervals overlap with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval); // add results

        // Step 3: add intervals after new 
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        // transform to array
        return result.toArray(new int[result.size()][]);
    }
}

Remarks:

1. TC: $O(n)$, SC: $O(n)$ (for the new list).
2. Premise: intervals are sorted.