{"id":3458,"date":"2023-08-14T18:28:13","date_gmt":"2023-08-14T12:58:13","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3458"},"modified":"2023-08-14T18:34:09","modified_gmt":"2023-08-14T13:04:09","slug":"merge-two-sorted-arrays-without-extra-space","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/merge-two-sorted-arrays-without-extra-space\/","title":{"rendered":"Merge Two Sorted Arrays Without Extra Space"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#method-1\">Method 1<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#merging-without-using-extra-space\">Merging Without Using Extra Space<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-why-does-merge-sort-require-extra-space\">Q.1: Why does merge sort require extra space?<\/a><\/li><li><a href=\"#q2-is-quicksort-faster-than-mergesort\">Q.2: Is Quicksort faster than mergesort?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>We are given two sorted arrays, our task is to merge two sorted arrays in a sorted manner.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input: <\/strong>vec1[] = { 1, 3, 4, 5}, vec2[] = {2, 4, 6, 8}<\/li><li><strong>Output: <\/strong>vec3[] = {1, 2, 3, 4, 4, 5, 6, 8}<\/li><\/ul>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input :<\/strong> vec1[]= {-7,12,17,29,41,56,79} , vec2[]= {-9,-3,0,5,19}<\/li><li><strong>Output: <\/strong>{-9,-7,-3,0,5,12,17,19,29,41,56,79}<\/li><\/ul>\n\n\n\n<p>Explanation:\u00a0 If we merge both arrays in a sorted fashion then the resultant array will be sorted array as above.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"473\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3527 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-1024x473.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-1024x473.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-300x139.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-768x355.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-380x176.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-550x254.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-800x370.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3-1160x536.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-3.png 1331w\" ><\/figure>\n\n\n\n<h2 id=\"method-1\">Method 1<\/h2>\n\n\n\n<p><strong>INTUITION: <\/strong>We can see the given arrays are sorted. Now our target is to make a sorted array by merging both the arrays so if we will put the smallest element always in the front of the final array then we can make our sorted array. So to choose which element is smaller we can just simply compare the front elements of both arrays.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Create an array vec3[] of size n1 + n2.<\/li><li>Simultaneously traverse vec1[] and vec2[].\u00a0<\/li><li>Pick a smaller of the current elements in vec1[] and vec2[], copy this smaller element to the next position in vec3[] and move ahead in vec3[] and the array whose element is picked.<\/li><li>If there are remaining elements in vec1[] or vec2[], copy them also in vec3[].<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void mergeArrays(int vec1[], int vec2[], int n1,\n  int n2, int vec3[]) {\n  int i = 0, j = 0, k = 0;\n\n  while (i &lt; n1 &amp;&amp; j &lt; n2) {\n\n    if (vec1[i] &lt; vec2[j])\n      vec3[k++] = vec1[i++];\n    else\n      vec3[k++] = vec2[j++];\n  }\n\n  while (i &lt; n1)\n    vec3[k++] = vec1[i++];\n\n  while (j &lt; n2)\n    vec3[k++] = vec2[j++];\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\"><span id=\"java-code-implementation-2\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void mergeArrays(int[] vec1, int[] vec2, int n1,\n  int n2, int[] vec3) {\n  int i = 0, j = 0, k = 0;\n  while (i &lt; n1 &amp;&amp; j &lt; n2) {\n    if (vec1[i] &lt; vec2[j])\n      vec3[k++] = vec1[i++];\n    else\n      vec3[k++] = vec2[j++];\n  }\n  while (i &lt; n1)\n    vec3[k++] = vec1[i++];\n  while (j &lt; n2)\n    vec3[k++] = vec2[j++];\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def mergeArrays(vec1, vec2, n1, n2):\n    vec3 = [None] * (n1 + n2)\n    i = 0\n    j = 0\n    k = 0\n    while i &lt; n1 and j &lt; n2:\n        if vec1[i] &lt; vec2[j]:\n            vec3[k] = vec1[i]\n            k = k + 1\n            i = i + 1\n        else:\n            vec3[k] = vec2[j]\n            k = k + 1\n            j = j + 1\n    while i &lt; n1:\n        vec3[k] = vec1[i];\n        k = k + 1\n        i = i + 1\n    while j &lt; n2:\n        vec3[k] = vec2[j];\n        k = k + 1\n        j = j + 1<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(n1 * n2) where n1 and n2 are the sizes of two arrays.<br>Space Complexity: O(n1+n2) where n1 and n2 are the sizes of two arrays.<\/p>\n\n\n\n<h2 id=\"merging-without-using-extra-space\">Merging Without Using Extra Space<\/h2>\n\n\n\n<p>While iterating over the two sorted arrays parallelly, if we encounter the jth second array element being smaller than ith first array element, then the jth element is to be included and replace some kth element in the first array.<\/p>\n\n\n\n<p id=\"-algorithm-\"><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialize i,j,k as 0,0,n-1 where n is the size of vec1\u00a0<\/li><li>Iterate through every element of vec1 and vec2 using two pointers i and j respectively<\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>if vec1&#91;i] is less than vec2&#91;j]\n        increment i\n    else\n        swap the vec2&#91;j] and vec1&#91;k]\n        increment j and decrement k\n<\/code><\/pre>\n\n\n\n<ul><li>Sort both vec1 and vec2.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void merge(int vec1[], int vec2[], int n, int m) {\n  int i = 0, j = 0, k = n - 1;\n  while (i &lt;= k &amp;&amp; j &lt; m) {\n    if (vec1[i] &lt; vec2[j])\n      i++;\n    else {\n      swap(vec2[j++], vec1[k--]);\n    }\n  }\n\n  sort(vec1, vec1 + n);\n  sort(vec2, vec2 + m);\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static void merge(int m, int n)\n{\n    int i = 0, j = 0, k = n - 1;\n    while (i &lt;= k &amp;&amp; j &lt; m) {\n        if (vec1[i] &lt; vec2[j])\n            i++;\n        else {\n            int temp = vec2[j];\n            vec2[j] = vec1[k];\n            vec1[k] = temp;\n            j++;\n            k--;\n        }\n    }\n    Arrays.sort(vec1);\n    Arrays.sort(vec2);\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def merge(self, nums1, m, nums2, n):\n        while m > 0 and n > 0:\n            if nums1[m-1] >= nums2[n-1]:\n                nums1[m+n-1] = nums1[m-1]\n                m -= 1\n            else:\n                nums1[m+n-1] = nums2[n-1]\n                n -= 1\n        if n > 0:\n            nums1[:n] = nums2[:n]<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O((n+m)log(n+m)) where n and m are the sizes of two arrays.<\/li><li><strong>Space Complexity:<\/strong> O(1).<\/li><\/ul>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/merge-two-sorted-lists\/\" target=\"_blank\">Merge 2 Sorted Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/merge-k-sorted-arrays\/\" target=\"_blank\">Merge K Sorted Arrays<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-why-does-merge-sort-require-extra-space\"><span id=\"q-1-why-does-merge-sort-require-extra-space\">Q.1: Why does merge sort require extra space?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>When we are merging two arrays then for merging we need one more additional space to create the array.<\/p>\n\n\n\n<h3 id=\"q2-is-quicksort-faster-than-mergesort\"><span id=\"q-2-is-quicksort-faster-than-mergesort\">Q.2: Is Quicksort faster than mergesort?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Merge sort is more efficient and works faster than quicksort in the case of a larger size array. Quicksort is more efficient and works faster than merge sort in case of the smaller size of an array.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement We are given two sorted arrays, our task is to merge two sorted arrays in a&hellip;\n","protected":false},"author":5,"featured_media":3529,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[144,545],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3458"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3458"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3458\/revisions"}],"predecessor-version":[{"id":22722,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3458\/revisions\/22722"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3529"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3458"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}