✔️ 98.87% Beats ✔️ Easy Explanation ✔️ C++ ✔️ Java ✔️ Python
\n\n\n# Intuition\nTo solve this problem, we can iterate through the given intervals and compare them with the newInterval to determine their relationship. We n
![dark_98.PNG](https://assets.leetcode.com/users/images/f2b7f1af-8bd6-4fa2-9429-3b4d385d18b4_1710636903.121015.png)\n\n\n# Intuition\nTo solve this problem, we can iterate through the given intervals and compare them with the newInterval to determine their relationship. We need to consider three cases:\n\n1. The current interval ends before the newInterval starts.\n2. The current interval overlaps with the newInterval.\n3. The current interval starts after the newInterval ends.\n\n# Approach\nWe initialize an empty list **result** to store the merged intervals. We iterate through the given intervals, adding non-overlapping intervals before the newInterval to **result**. Then, we merge overlapping intervals with the newInterval. After that, we add the merged newInterval to **result**. Finally, we add the remaining non-overlapping intervals after the newInterval to **result**. We return **result** as the final result.\n\n# Complexity\n- Time complexity: O(n), where n is the number of intervals. We iterate through all the intervals once.\n\n- Space complexity: O(n), the space used by the **result** list to store the merged intervals.\n\n# Code\n``` cpp []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        vector<vector<int>> result;\n        \n        // Iterate through intervals and add non-overlapping intervals before newInterval\n        int i = 0;\n        while (i < intervals.size() && intervals[i][1] < newInterval[0]) {\n            result.push_back(intervals[i]);\n            i++;\n        }\n        \n        // Merge overlapping intervals\n        while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = std::min(newInterval[0], intervals[i][0]);\n            newInterval[1] = std::max(newInterval[1], intervals[i][1]);\n            i++;\n        }\n        \n        // Add merged newInterval\n        result.push_back(newInterval);\n        \n        // Add non-overlapping intervals after newInterval\n        while (i < intervals.size()) {\n            result.push_back(intervals[i]);\n            i++;\n        }\n        \n        return result;\n    }\n};\n```\n```java []\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> result = new ArrayList<>();\n        \n        // Iterate through intervals and add non-overlapping intervals before newInterval\n        int i = 0;\n        while (i < intervals.length && intervals[i][1] < newInterval[0]) {\n            result.add(intervals[i]);\n            i++;\n        }\n        \n        // Merge overlapping intervals\n        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n            i++;\n        }\n        \n        // Add merged newInterval\n        result.add(newInterval);\n        \n        // Add non-overlapping intervals after newInterval\n        while (i < intervals.length) {\n            result.add(intervals[i]);\n            i++;\n        }\n        \n        return result.toArray(new int[result.size()][]);\n    }\n}\n\n```\n```python []\nclass Solution:\n    def insert(self, intervals, newInterval):\n        result = []\n        i = 0\n        \n        # Iterate through intervals and add non-overlapping intervals before newInterval\n        while i < len(intervals) and intervals[i][1] < newInterval[0]:\n            result.append(intervals[i])\n            i += 1\n        \n        # Merge overlapping intervals\n        while i < len(intervals) and intervals[i][0] <= newInterval[1]:\n            newInterval[0] = min(newInterval[0], intervals[i][0])\n            newInterval[1] = max(newInterval[1], intervals[i][1])\n            i += 1\n        \n        # Add merged newInterval\n        result.append(newInterval)\n        \n        # Add non-overlapping intervals after newInterval\n        while i < len(intervals):\n            result.append(intervals[i])\n            i += 1\n        \n        return result\n\n```\n```python3 []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        result = []\n        i = 0\n        \n        # Iterate through intervals and add non-overlapping intervals before newInterval\n        while i < len(intervals) and intervals[i][1] < newInterval[0]:\n            result.append(intervals[i])\n            i += 1\n        \n        # Merge overlapping intervals\n        while i < len(intervals) and intervals[i][0] <= newInterval[1]:\n            newInterval[0] = min(newInterval[0], intervals[i][0])\n            newInterval[1] = max(newInterval[1], intervals[i][1])\n            i += 1\n        \n        # Add merged newInterval\n        result.append(newInterval)\n        \n        # Add non-overlapping intervals after newInterval\n        while i < len(intervals):\n            result.append(intervals[i])\n            i += 1\n        \n        return result\n\n```\n```c []\nint **insert(int **intervals, int intervalsSize, int *intervalsColSize, int *newInterval, int newIntervalSize, int *returnSize, int **returnColumnSizes) {\n    int **result = (int **)malloc((intervalsSize + 1) * sizeof(int *));\n    *returnSize = 0;\n    *returnColumnSizes = (int *)malloc((intervalsSize + 1) * sizeof(int));\n    \n    // Iterate through intervals and add non-overlapping intervals before newInterval\n    int i = 0;\n    while (i < intervalsSize && intervals[i][1] < newInterval[0]) {\n        result[*returnSize] = (int *)malloc(2 * sizeof(int));\n        result[*returnSize][0] = intervals[i][0];\n        result[*returnSize][1] = intervals[i][1];\n        (*returnColumnSizes)[*returnSize] = 2;\n        (*returnSize)++;\n        i++;\n    }\n    \n    // Merge overlapping intervals\n    while (i < intervalsSize && intervals[i][0] <= newInterval[1]) {\n        newInterval[0] = (newInterval[0] < intervals[i][0]) ? newInterval[0] : intervals[i][0];\n        newInterval[1] = (newInterval[1] > intervals[i][1]) ? newInterval[1] : intervals[i][1];\n        i++;\n    }\n    \n    // Add merged newInterval\n    result[*returnSize] = (int *)malloc(2 * sizeof(int));\n    result[*returnSize][0] = newInterval[0];\n    result[*returnSize][1] = newInterval[1];\n    (*returnColumnSizes)[*returnSize] = 2;\n    (*returnSize)++;\n    \n    // Add non-overlapping intervals after newInterval\n    while (i < intervalsSize) {\n        result[*returnSize] = (int *)malloc(2 * sizeof(int));\n        result[*returnSize][0] = intervals[i][0];\n        result[*returnSize][1] = intervals[i][1];\n        (*returnColumnSizes)[*returnSize] = 2;\n        (*returnSize)++;\n        i++;\n    }\n    \n    return result;\n}\n```\n\n```csharp []\npublic class Solution {\n    public int[][] Insert(int[][] intervals, int[] newInterval) {\n        List<int[]> result = new List<int[]>();\n        \n        // Iterate through intervals and add non-overlapping intervals before newInterval\n        int i = 0;\n        while (i < intervals.Length && intervals[i][1] < newInterval[0]) {\n            result.Add(intervals[i]);\n            i++;\n        }\n        \n        // Merge overlapping intervals\n        while (i < intervals.Length && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);\n            newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);\n            i++;\n        }\n        \n        // Add merged newInterval\n        result.Add(newInterval);\n        \n        // Add non-overlapping intervals after newInterval\n        while (i < intervals.Length) {\n            result.Add(intervals[i]);\n            i++;\n        }\n        \n        return result.ToArray();\n    }\n}\n\n```\n```javascript []\nvar insert = function(intervals, newInterval) {\n    const result = [];\n\n    // Iterate through intervals and add non-overlapping intervals before newInterval\n    let i = 0;\n    while (i < intervals.length && intervals[i][1] < newInterval[0]) {\n        result.push(intervals[i]);\n        i++;\n    }\n    \n    // Merge overlapping intervals\n    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {\n        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n        i++;\n    }\n    \n    // Add merged newInterval\n    result.push(newInterval);\n    \n    // Add non-overlapping intervals after newInterval\n    while (i < intervals.length) {\n        result.push(intervals[i]);\n        i++;\n    }\n    \n    return result;\n};\n\n```\n``` typescript []\nfunction insert(intervals: number[][], newInterval: number[]): number[][] {\n    const result: number[][] = [];\n    \n    // Iterate through intervals and add non-overlapping intervals before newInterval\n    let i = 0;\n    while (i < intervals.length && intervals[i][1] < newInterval[0]) {\n        result.push(intervals[i]);\n        i++;\n    }\n    \n    // Merge overlapping intervals\n    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {\n        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n        i++;\n    }\n    \n    // Add merged newInterval\n    result.push(newInterval);\n    \n    // Add non-overlapping intervals after newInterval\n    while (i < intervals.length) {\n        result.push(intervals[i]);\n        i++;\n    }\n    \n    return result;\n}\n\n```\n```php []\nclass Solution {\n    function insert($intervals, $newInterval) {\n        $result = [];\n        \n        // Iterate through intervals and add non-overlapping intervals before newInterval\n        $i = 0;\n        while ($i < count($intervals) && $intervals[$i][1] < $newInterval[0]) {\n            $result[] = $intervals[$i];\n            $i++;\n        }\n        \n        // Merge overlapping intervals\n        while ($i < count($intervals) && $intervals[$i][0] <= $newInterval[1]) {\n            $newInterval[0] = min($newInterval[0], $intervals[$i][0]);\n            $newInterval[1] = max($newInterval[1], $intervals[$i][1]);\n            $i++;\n        }\n        \n        // Add merged newInterval\n        $result[] = $newInterval;\n        \n        // Add non-overlapping intervals after newInterval\n        while ($i < count($intervals)) {\n            $result[] = $intervals[$i];\n            $i++;\n        }\n        \n        return $result;\n    }\n}\n```\n```go []\nfunc insert(intervals [][]int, newInterval []int) [][]int {\n\tvar result [][]int\n\n    // Iterate through intervals and add non-overlapping intervals before newInterval\n\ti := 0\n\tfor i < len(intervals) && intervals[i][1] < newInterval[0] {\n\t\tresult = append(result, intervals[i])\n\t\ti++\n\t}\n\n    // Merge overlapping intervals\n\tfor i < len(intervals) && intervals[i][0] <= newInterval[1] {\n\t\tnewInterval[0] = int(math.Min(float64(newInterval[0]), float64(intervals[i][0])))\n\t\tnewInterval[1] = int(math.Max(float64(newInterval[1]), float64(intervals[i][1])))\n\t\ti++\n\t}\n\n    // Add merged newInterval\n\tresult = append(result, newInterval)\n\n    // Add non-overlapping intervals after newInterval\n\tfor i < len(intervals) {\n\t\tresult = append(result, intervals[i])\n\t\ti++\n\t}\n\n\treturn result\n}\n\n```\n```kotlin []\nclass Solution {\n    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {\n        val result = mutableListOf<IntArray>()\n        \n        // Iterate through intervals and add non-overlapping intervals before newInterval\n        var i = 0\n        while (i < intervals.size && intervals[i][1] < newInterval[0]) {\n            result.add(intervals[i])\n            i++\n        }\n        \n        // Merge overlapping intervals\n        while (i < intervals.size && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = minOf(newInterval[0], intervals[i][0])\n            newInterval[1] = maxOf(newInterval[1], intervals[i][1])\n            i++\n        }\n        \n        // Add merged newInterval\n        result.add(newInterval)\n        \n        // Add non-overlapping intervals after newInterval\n        while (i < intervals.size) {\n            result.add(intervals[i])\n            i++\n        }\n        \n        return result.toTypedArray()\n    }\n}\n```\n![upvote_new_cc82e8aa-dc98-4f10-af4c-64b1528c0fb6_1680844232.130332.png](https://assets.leetcode.com/users/images/ecc5d057-b028-4996-a51a-8de28d900404_1710695186.0211613.png)\n\n
['C', 'PHP', 'Python', 'C++', 'Java', 'Go', 'TypeScript', 'Kotlin', 'JavaScript', 'C#']