🧑‍🏫 Java | 99th percentile | One pass explained [Article]
\n\n\n# Intuition\nWe are given a non-overlapping, sorted intervals array. These properties are essential because we can utilize them to solve the problem in on
![image.png](https://assets.leetcode.com/users/images/79f9f39a-f625-4707-9c7b-dcbb13533e2b_1673854957.9331577.png)\n\n\n# Intuition\nWe are given a non-overlapping, sorted intervals array. These properties are essential because we can utilize them to solve the problem in one pass.\n\nLet\'s visualize a few possibilities that we may have. Imagine these given intervals:\n```\n    [     ] [ ] [  ]\n```\nImagine them on an x-axis line.\n\nWe may need to insert the following intervals:\n```\n    [     ] [ ] [  ]\n |           |   \n\n | |\n                         | |\n\n```\n\nThese are three situations where we may need to insert a new interval.\n\nThe first one overlaps multiple given intervals, the second one doesn\'t overlap and should be inserted in the beginning, and the last is non-overlapping and should be inserted in the end.\n\nWe either need to *merge* the interval with one of the given intervals (or multiple), or insert it.\n\n*If we merge an interval, we don\'t impact the intervals previously added*, because they are sorted. `nextIntervalEnd > previousStart`, which is always true because of non-overlapping sorted property.\n\nTherefore we need to merge intervals *until* we find an interval that started after the merged interval.\n\nIf the given interval doesn\'t overlap with the merged interval, we simply add it to the result array.\n\n# Complexity\n- Time complexity:\n`O(n)`\n\n- Space complexity:\n`O(n)`\n\n# Code\n```\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> mergedIntervals = new ArrayList<>();\n        int[] merged = new int[] {newInterval[0], newInterval[1]};\n        boolean isInserted = false;\n\n        for (int[] interval : intervals) {\n            if(interval[0] > merged[1]) {\n                if(!isInserted) {\n                    mergedIntervals.add(merged);\n                    isInserted = true;\n                }\n                mergedIntervals.add(interval);\n                \n            } else {\n                // does intersect\n                if(doesIntersect(merged, interval)) {\n                    merged[0] = Math.min(merged[0], interval[0]);\n                    merged[1] = Math.max(merged[1], interval[1]);\n                } else {\n                    // not intersecting\n                    mergedIntervals.add(interval);\n                }\n                \n                \n            }\n        }\n\n        // new interval is at the end\n        if(!isInserted) {\n            mergedIntervals.add(merged);\n            isInserted = true;\n        }\n\n        // Java specific to copy to arr[][]...\n        int[][] res = new int[mergedIntervals.size()][2];\n        for(int i = 0; i < mergedIntervals.size(); i++) {\n            res[i] = mergedIntervals.get(i);\n        }\n        return res;\n\n    }\n\n    private boolean doesIntersect(int[] intervalA, int[] intervalB) {\n        return intervalA[0] <= intervalB[1] && intervalB[0] <= intervalA[1];\n    }\n}\n```
['Java']