{"id":1552,"date":"2024-01-31T13:00:00","date_gmt":"2024-01-31T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1552"},"modified":"2024-02-01T07:25:04","modified_gmt":"2024-02-01T07:25:04","slug":"insert-interval-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/insert-interval-problem\/","title":{"rendered":"Insert Interval Problem Solved (C++, Java, Python)"},"content":{"rendered":"\n<p>Interval-related questions are frequently asked in technical interviews. Some of the common questions among them are Insert Interval, Merge Interval, Meeting Room, etc. This article will explore various approaches to solving the Insert Interval Problem, with implementation in C++, Java, and Python. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Insert Interval Problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Insert Interval problem, you are given an array containing intervals in sorted and non-overlapping intervals,  And you are also provided with an additional interval, Now the task is to insert this interval into the array such that the given array will still be sorted and in a non-overlapping interval. Return a new array as a result.<\/strong><\/p>\n\n\n\n<p>Let us understand this with an example:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Consider you have an array arr = [[2,5], [6,8], [10,13]]. Intervals in the given array look like this,<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/sqlCM-4Sbtk-LIK6n6baesd8R--Hf5InIir6aBcwHvjd6KK89wxGT09_R_xAfQVbo7C2QjAE5B4ikyoEseXykIRjjQeNijI0ByamJgRxZiVnzJC1rIp3W54I7gTRMcIp0RHyd3FsdRICGdOp83ajV_M\" alt=\"Example Array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>And an additional interval = [4,7] will look like this<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/vWONw3ynHygc79Gay18ABV3vrpJF1A_KExAoHKwMT7fXpFr_oLiNePDMWcVkxxOTapO3uvzY1YnSuOtP7Vxsv15TN0k1ZwkSbuuKS9IFoc_-eINXatcMdVCP0-H2Z8ya-GXXNnGMzD80r7Tm6Me22-s\" alt=\"Adding interval 4-7\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>After overlapping that new interval into the given array the new array will be&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/5VrK5vkF_29uoCqy8nJMkC5OjrorzdcIG_vfaOlzRQ95N3y3SB0XG71FS9OyD6Pe3YWFAF0Ph-5sfY5O8moXBx-NL0q7ckY7Aq1OB6H7Rt6JxiWwiAGbJBSRx-KA18W0PShRlll_ecf8hTiM3PjrDes\" alt=\"Overlapping the intervals\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>So the resultant arr = [[2,8], [10,13]].<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/fgVDHSSCTRa7LxTEMhZTeJnQo-wvndWgx-mJ3DMUgITpxEuHJn0xydLqQ2OzzzB6IVpUcSE-TewjaWJdRdq0yiv_7sX2wDODbeZWSsEZocctp12jLnSUIyQo9DubzmnvBbUe62N_6E7O-pxQ_ERRfKg\" alt=\"Output\"\/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Brute Force Approach: Using Sorting&nbsp;<\/strong><\/h2>\n\n\n\n<p>Before using this method, you may have to go through some <a href=\"https:\/\/favtutor.com\/blogs\/sorting-algorithms-java\">sorting algorithms<\/a> and understand their time complexity. This problem incorporates concepts from sorting.<\/p>\n\n\n\n<p><strong>Sorting can be used to solve the Insert Interval problem.<\/strong> First, create a new array, then copy the given array into the new array result and insert the new interval into the original array. Then sort the whole array and merge the intervals if they are overlapping.<\/p>\n\n\n\n<p>We can take an example:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Let the given array be [[2,5], [6,8], [10,13]] and interval be interval= [4,7]<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/vWONw3ynHygc79Gay18ABV3vrpJF1A_KExAoHKwMT7fXpFr_oLiNePDMWcVkxxOTapO3uvzY1YnSuOtP7Vxsv15TN0k1ZwkSbuuKS9IFoc_-eINXatcMdVCP0-H2Z8ya-GXXNnGMzD80r7Tm6Me22-s\" alt=\"Input Array and Interval 4-7\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>&nbsp;Now create a new array ans, copy the values in the array, and then push the interval into the ans.&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/LqBGmNe1rxHA0tESvTUst_lyLvYaGMdtNtAE3YS4G-epb2CFJOjuw6pAc7b8lGTt10-aWHwelsLpTOU5AdjNlzLd-8ptOtQULjVKAzJ1SgPcvapbOaNVHpfwoDWDpCZVtwiEwhVEfn-VQeUwD5UxtgU\" alt=\"Push interval in ans array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now sort the new array ans, it will look like this<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/DvCzObDon06hfdKrJ31SCRjv-ht-2Te9S4kkGTlMmZSCOiN5fXedNX4dhcwsqZ4Rg8jj_akv8gVBoA9g5AK-1yFW7Wfve7V_TjR8SddbQjNelWc9AC88fvrbwVaVGA2lmrHFGSrKqp4kB8q6dDPvs3s\" alt=\"Sort the new array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now merge the overlapping intervals in this case overlapping intervals are [2,5], [4,7], [6,8], and they are all combined into a single interval [2,8].<\/li>\n\n\n\n<li>The new array ans=[[2,8], [10,13]] will look like this&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/fgVDHSSCTRa7LxTEMhZTeJnQo-wvndWgx-mJ3DMUgITpxEuHJn0xydLqQ2OzzzB6IVpUcSE-TewjaWJdRdq0yiv_7sX2wDODbeZWSsEZocctp12jLnSUIyQo9DubzmnvBbUe62N_6E7O-pxQ_ERRfKg\" alt=\"New answer array\"\/><\/figure>\n\n\n\n<p>The Time complexity of solving the problem using sorting is Nlog(N) where N is the size of the array. While sorting, we need Nlog(N) to\u00a0sort the array and N to merge the whole array into a single array, so the total time will be (Nlog(N)+ N) ~\u00a0 Nlog(N). The Space Complexity is O(N) for the new array as it stores all the values of the array.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimized Approach to Solve It<\/strong><\/h2>\n\n\n\n<p>As in the above approach, we are making use of sorting which increases our time complexity to O(Nlog(N)) which can be reduced by taking advantage of the sorted array as we know that the given array arr is already sorted. So insert the element into the resultant array and compare the values. This can easily be done by following the steps,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First, create a resultant array, so your interval, array, and the new resultant array will look like this&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/Nhj1OxQgfTRiJ6YGQ6uhvSRShqX0sl4s5Sd_Ub3FdKqRCYyRSY34rCTdJVCf2L3QcamGS7d1Z4Raoqsnk4uRIktFpxpkx9R5WQ7EvAbAW98X5cjmSN-tovOqGHTuarVwPbJqKGvUMWiEdU9AGjA6EZc\" alt=\"Resultant Array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Second step, we will keep on inserting the values from the array i.e. arr into the ans if <strong>interval[0] &gt; arr[i][1]<\/strong> where i is the current index. So in this case, as arr[0][1] is greater than interval[0] we will not push the interval into the array.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/aRXXQQ6kogxTcanTR7IniVWuc_kWEM7ufEy9T2ji6qXx7VLfnwPpXvX_ezpIHWOiIPwJU7T_2NDgNoTlkIY_igC_flS-yXFnR8__Od3i_fBApZH-_vjMbnKkQNtx3qINqFGcK-HVrDYQtoOA8H_HaMY\" alt=\"Condition to push\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In the third step, we will keep on updating the interval till <strong>arr[i][0] &lt; interval[1], <\/strong>and if not we will add that interval to the ans.&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/yI12ZsjFuxZGycH4ORspg3PimZwz3cStAF_mVrH2gay56ytxd2OhMIT-tMNrPm6duY8UCKwGC9AP8EbBgo9GK0FicxQq0Qjw1Ot-zpGcobtsr4rrLjZlOTAu3YxNsttLFDbQIiODyfRCufeZUhALW70\" alt=\"updating the interval till arr[i][0] < interval[1]\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>At last, we will add all the remaining arr intervals into the ans and return ans as a resultant array. As in this case only interval left is [10,13] so the resultant array will be ans= [[2,8], [10,13]].<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/F6L_Ut9gRxq7OxflrxMWWZ1I6-CRz9lyqE0w716gmG4_6uMNs3vdIlUNfTd5cDH_prge3dl5y46LqAK81F1dYB15DIPYH7dIO11CKs84a1An_1KfHgtFMfVOpXYO5UrJ5ykeCosgfASpD3NDpGYwWVQ\" alt=\"Resultant array\"\/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to solve the Insert Interval problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint main(){\n\n    vector&lt;vector&lt;int&gt;&gt;arr = {{2,5},{6,8},{10,13}};\n    vector&lt;int&gt;interval={4,7};\n    vector&lt;vector&lt;int&gt;&gt;ans;\n\n    int n= arr.size(), i=0;  \/\/ n is the size of arr \n\n    \/\/ keep on pushing the intervals of array into the ans till they are not overlapping and index is  less than the current size of array\n\n    while(i&lt;n &amp;&amp; (arr[i][1] &lt; interval[0])){\n        ans.push_back(arr[i]);\n        i++;\n    }\n\n    \/\/ keep updating values till they are overlapping\n    while(i&lt;n &amp;&amp; (arr[i][0] &lt;= interval[1])){\n        interval[0] = min(arr[i][0], interval[0]);\n        interval[1] = max(arr[i][1],interval[1]);\n        i++;\n    }\n\n    ans.push_back(interval);\n\n    while(i&lt;n){\n        ans.push_back(arr[i]);\n        i++;\n    }\n\n    for(int j=0;j&lt;ans.size();j++){\n        cout&lt;&lt;ans[j][0]&lt;&lt;&quot; &quot;&lt;&lt;ans[j][1]&lt;&lt;endl;\n    }\n    \/\/ the array in this case is \n    \/\/ Output ans={{2,8}, {10,13}}\n\n    return 0;\n\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the implementation in Java:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.ArrayList;\n\nclass MergeIntervals {\n\n    public static void main(String[] args) {\n        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; arr = new ArrayList&lt;&gt;();\n        arr.add(new ArrayList&lt;Integer&gt;() {{ add(2); add(5); }});\n        arr.add(new ArrayList&lt;Integer&gt;() {{ add(6); add(8); }});\n        arr.add(new ArrayList&lt;Integer&gt;() {{ add(10); add(13); }});\n\n        ArrayList&lt;Integer&gt; interval = new ArrayList&lt;Integer&gt;() {{ add(4); add(7); }};\n        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; ans = new ArrayList&lt;&gt;();\n\n        int n = arr.size();\n        int i = 0;\n\n        while (i &lt; n &amp;&amp; arr.get(i).get(1) &lt; interval.get(0)) {\n            ans.add(arr.get(i));\n            i++;\n        }\n\n        while (i &lt; n &amp;&amp; arr.get(i).get(0) &lt;= interval.get(1)) {\n            interval.set(0, Math.min(arr.get(i).get(0), interval.get(0)));\n            interval.set(1, Math.max(arr.get(i).get(1), interval.get(1)));\n            i++;\n        }\n\n        ans.add(interval);\n\n        while (i &lt; n) {\n            ans.add(arr.get(i));\n            i++;\n        }\n\n        for (ArrayList&lt;Integer&gt; pair : ans) {\n            System.out.println(pair.get(0) + &quot; &quot; + pair.get(1));\n        }\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>You can do it in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">arr = [[2, 5], [6, 8], [10, 13]]\ninterval = [4, 7]\nans = []\n\nn = len(arr)\ni = 0\n\n# Keep pushing intervals into ans until they are not overlapping and index is less than the current size of an array\nwhile i &lt; n and arr[i][1] &lt; interval[0]:\n    ans.append(arr[i])\n    i += 1\n\n# Keep updating values until intervals are overlapping\nwhile i &lt; n and arr[i][0] &lt;= interval[1]:\n    interval[0] = min(arr[i][0], interval[0])\n    interval[1] = max(arr[i][1], interval[1])\n    i += 1\n\nans.append(interval)\n\n# Push the remaining intervals into ans\nwhile i &lt; n:\n    ans.append(arr[i])\n    i += 1\n\n# Print the result\nfor j in ans:\n    print(j[0], j[1])<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-4672c66788e9b16c33b6d6e2865de8b6\" style=\"background-color:#fedcba\"><code>2 8\n10 13<\/code><\/pre>\n\n\n\n<p>In the above approach the time complexity will be O(N) as in this case, we are iterating over the whole array only once. Space Complexity will also be O(N) as we are making an array ans as a resultant array.<\/p>\n\n\n\n<p>Here is a small comparison of both the approaches:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th><strong>Approach<\/strong><\/th><th><strong>Time Complexity&nbsp;<\/strong><\/th><th><strong>Space Complexity<\/strong><\/th><th><strong>Description<\/strong><\/th><\/tr><\/thead><tbody><tr><td>Brute Force: Using Sorting<\/td><td>O(N*logN)<\/td><td>O(N)<\/td><td>Sort the whole array and merge the intervals if they are overlapping with the copy of the original array.<\/td><\/tr><tr><td>Optimized Approach<\/td><td>O(N)<\/td><td>O(N)<\/td><td>Reduce the time complexity by using the arr array as it is already sorted.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>We solved the Insert Interval problem from <a href=\"https:\/\/leetcode.com\/problems\/insert-interval\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode<\/a> in this article, as well as found out how can we approach a problem through different methods.\u00a0Practice more similar problems to get a good grasp of this concept.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Interval-related questions are frequently asked in technical interviews. Some of the common questions among them are Insert Interval, Merge Interval, Meeting Room, etc. This article will explore various approaches to solving the Insert Interval Problem, with implementation in C++, Java, and Python. What is the Insert Interval Problem? In the Insert Interval problem, you are [&hellip;]<\/p>\n","protected":false},"author":14,"featured_media":1557,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1552","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1552","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1552"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1552\/revisions"}],"predecessor-version":[{"id":1631,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1552\/revisions\/1631"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1557"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}