2 Approaches | | Brute Force O(n^2) | | Optimal O(n) | | C++ | | Java | | Python3 | | Kotlin✅✅🔥🔥🔥
\n\n# Intuition\nTo solve this problem, we can utilize the fact that the intervals are sorted and non-overlapping. We can iterate through the intervals and comp
\n![image.png](https://assets.leetcode.com/users/images/761b2087-e7a0-4a50-8a00-d44b63f718fc_1710644525.1542768.png)\n# Intuition\nTo solve this problem, we can utilize the fact that the intervals are sorted and non-overlapping. We can iterate through the intervals and compare them with the new interval to determine the correct position for insertion. If there is an overlap, we merge the intervals. \n\n# Approach\n## Approach 1 :\nIn this approach, we iterate through each interval in the given vector and compare it with the new interval. We handle three cases: \n1. If the current interval ends before the new interval starts, we continue iterating.\n2. If the current interval starts after the new interval ends, we insert the new interval at the current position.\n3. If there is an overlap between the current interval and the new interval, we merge them and update the new interval accordingly. \n\n## Approach 2:\nIn this approach, we also iterate through each interval, but instead of modifying the original vector, we maintain a separate vector to store the merged intervals. We handle the same three cases as in Approach 1. After iterating through all intervals, we append the remaining intervals from the original vector to the result vector.\n\n# Complexity\n**- Time complexity:**\n  - Approach 1: O(n^2)\n  - Approach 2: O(n)\n**- Space complexity:**\n  - Both approaches: O(n)\n\n# Code\n\n**Approach 1**\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        int i = 0;\n        \n        while(i < intervals.size()) {\n            if(intervals[i][1] < newInterval[0])\n                i++;\n            else if (intervals[i][0] > newInterval[1]){\n                intervals.insert(intervals.begin() + i, newInterval);\n                return intervals;\n            } else {\n                //Overlap : merge them\n                newInterval[0] = min(newInterval[0], intervals[i][0]);\n                newInterval[1] = max(newInterval[1], intervals[i][1]);\n                intervals.erase(intervals.begin()+i);\n            }\n        }\n        \n        intervals.push_back(newInterval);\n        return intervals;\n    }\n};\n```\n\n\n**Approach 2**\n```C++ []\n// Approach 2\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        int i = 0;\n        vector<vector<int>> result;\n        \n        while(i < intervals.size()) {\n            if(intervals[i][1] < newInterval[0]) {\n                result.push_back(intervals[i]);\n            } else if (intervals[i][0] > newInterval[1]) {\n                break;\n            } else {\n                //Overlap : merge them\n                newInterval[0] = min(newInterval[0], intervals[i][0]);\n                newInterval[1] = max(newInterval[1], intervals[i][1]);\n            }\n            i++;\n        }\n        \n        result.push_back(newInterval);\n        while(i < intervals.size()) {\n            result.push_back(intervals[i]);\n            i++;\n        }\n        return result;\n    }\n};\n```\n```Java []\n\n\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        int i = 0;\n        int n = intervals.length;\n        List<int[]> result = new ArrayList<>();\n        \n        while (i < intervals.length) {\n            if (intervals[i][1] < newInterval[0])\n                result.add(intervals[i]);\n            else if (intervals[i][0] > newInterval[1]){\n                break;\n            } else {\n                //Overlap : merge them\n                newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n                newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n            }\n            i++;\n        }\n        \n        result.add(newInterval);\n        while (i < n){\n            result.add(intervals[i++]);\n        }\n        \n        return result.toArray(new int[result.size()][2]);\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        i = 0\n        n = len(intervals)\n        result = []\n        \n        while i < len(intervals):\n            if intervals[i][1] < newInterval[0]:\n                result.append(intervals[i])\n            elif intervals[i][0] > newInterval[1]:\n                break\n            else:\n                #Overlap : merge them\n                newInterval[0] = min(newInterval[0], intervals[i][0])\n                newInterval[1] = max(newInterval[1], intervals[i][1])\n            i += 1\n        \n        result.append(newInterval)\n        while i < n:\n            result.append(intervals[i])\n            i += 1\n        \n        return result\n\n```\n```Kotlin []\nclass Solution {\n    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {\n        var i = 0\n        val n = intervals.size\n        val result = mutableListOf<IntArray>()\n        \n        while (i < intervals.size) {\n            if (intervals[i][1] < newInterval[0])\n                result.add(intervals[i])\n            else if (intervals[i][0] > newInterval[1]){\n                break\n            } else {\n                //Overlap : merge them\n                newInterval[0] = minOf(newInterval[0], intervals[i][0])\n                newInterval[1] = maxOf(newInterval[1], intervals[i][1])\n            }\n            i++\n        }\n        \n        result.add(newInterval)\n        while (i < n){\n            result.add(intervals[i++])\n        }\n        \n        return result.toTypedArray()\n    }\n}\n\n```\n```Javascript []\nvar insert = function(intervals, newInterval) {\n    let i = 0;\n    let n = intervals.length;\n    let result = [];\n    \n    while (i < intervals.length) {\n        if (intervals[i][1] < newInterval[0])\n            result.push(intervals[i]);\n        else if (intervals[i][0] > newInterval[1]){\n            break;\n        } else {\n            //Overlap : merge them\n            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n        }\n        i++;\n    }\n    \n    result.push(newInterval);\n    while (i < n){\n        result.push(intervals[i++]);\n    }\n    \n    return result;\n};\n\n```\n\n**Dry Run :**\n\n```plaintext\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [4,8]\n```\n\n### Approach 1 :\n\n1. Initialize `i = 0`.\n2. Check `intervals[0] = [1,2]`, `intervals[0][1] < newInterval[0]`, so continue.\n3. Increment `i`, `i = 1`.\n4. Check `intervals[1] = [3,5]`, `intervals[1][0] <= newInterval[1]`, so merge them (newInterval = [3,8]).\n5. Increment `i`, `i = 2`.\n6. Check `intervals[2] = [6,7]`, `intervals[2][0] > newInterval[1]`, so push newInterval to intervals and break.\n7. Insert newInterval at index 2, resulting in intervals = [[1,2],[3,8],[6,7],[8,10],[12,16]].\n\nThe approach continues until all intervals are processed.\n\n### Approach 2:\n\n1. Initialize `i = 0` and an empty `result` vector.\n2. Check `intervals[0] = [1,2]`, `intervals[0][1] < newInterval[0]`, so push `intervals[0]` to `result`.\n3. Increment `i`, `i = 1`.\n4. Check `intervals[1] = [3,5]`, `intervals[1][0] <= newInterval[1]`, so merge them (newInterval = [3,8]).\n5. Increment `i`, `i = 2`.\n6. Check `intervals[2] = [6,7]`, `intervals[2][0] > newInterval[1]`, so push newInterval to result and break.\n7. Append remaining intervals to result.\n8. Return `[[1,2],[3,8],[6,7],[8,10],[12,16]]`.\n\nBoth approaches will give the same correct output `[[1,2],[3,8],[6,7],[8,10],[12,16]]` for the given input. However, Approach 1 might take more time due to the repeated insertions and deletions in the original vector, while Approach 2 maintains a separate result vector, leading to better performance.\n\n\n# Note :\n**Key Point to Convert Brute Force to Optimal:**\nIn the brute force approach, we iterated through each interval and checked for overlaps with the new interval. This resulted in an O(n^2) time complexity as for each interval, we potentially traversed the entire list of intervals.\n\nIn the optimal approach, we utilized the fact that the intervals are sorted. We iterated through the list once and efficiently merged intervals that overlap with the new interval. This approach results in linear time complexity (O(n)). Additionally, we maintained a separate result vector to store the merged intervals, eliminating the need for repeated insertions and deletions in the original vector.\n\n
['Array', 'C++', 'Java', 'Python3', 'Kotlin', 'JavaScript']