{"id":3531,"date":"2021-11-11T13:52:02","date_gmt":"2021-11-11T08:22:02","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3531"},"modified":"2021-11-11T13:52:04","modified_gmt":"2021-11-11T08:22:04","slug":"merge-two-sorted-arrays","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/merge-two-sorted-arrays\/","title":{"rendered":"Merge Two Sorted Arrays"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">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=\"#insert-and-sort-approach\">Insert and Sort Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#merge-sort-method\">Merge Sort Method<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two sorted arrays <strong>A[]<\/strong> and <strong>B[] <\/strong>of size <strong>N<\/strong> and <strong>M<\/strong>. The task is to merge both the arrays into a single array in <strong>non-decreasing <\/strong>order.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>A[]<strong> <\/strong>=[3, 9, 10, 18, 23], B[] = [5, 12, 15, 20, 21, 25]<br><strong>Output:<\/strong> [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]<br><strong>Explanation: <\/strong>The merged array contains all the elements from both arrays in sorted order.<\/p>\n\n\n\n<p><strong>Input: <\/strong>\u00a0A[] = [1, 5], B[] = [4, 6, 7]<br><strong>Output:<\/strong> [1, 4, 5, 6, 7]\n\n\n\n<h2 id=\"insert-and-sort-approach\">Insert and Sort Approach<\/h2>\n\n\n\n<p id=\"the-most-naive-approach-is-to-simply-merge-elements-of-one-array-into-another-and-sort-the-resultant-array\">The most naive approach is to simply merge elements of one array into another and sort the resultant array.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/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 nums1[], int m, int nums2[], int n) {\n        for (int i = 0; i &lt; n; i++) {\n            nums1[i + m] = nums2[i];\n        }\n        sort(nums1, nums1 + n + m);\n    }<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/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 void merge(int[] nums1, int m, int[] nums2, int n) {\n        for (int i = 0; i &lt; n; i++) {\n            nums1[i + m] = nums2[i];\n        }\n        Arrays.sort(nums1);\n    }<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/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(nums1, m, nums2, n)\n        for i in range(n):\n            nums1[i + m] = nums2[i]\n        \n        nums1.sort()<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O((N + M)log(N+M)), where N and M are the size of array A[] and B[]<br><strong>Space Complexity:<\/strong>O(N), built-in sort takes space<\/p>\n\n\n\n<h2 id=\"merge-sort-method\">Merge Sort Method<\/h2>\n\n\n\n<p>The key idea to note here is that both the arrays are sorted. Therefore, taking advantage of this fact, we can apply a method similar to the merge sort technique.<br>Create an auxiliary array of size N + M and insert the merge element in this array.<br><br>Let us understand this approach with an example:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"394\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3573 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 394px) 100vw, 394px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-394x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-394x1024.png 394w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-115x300.png 115w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-768x1997.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-591x1536.png 591w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-788x2048.png 788w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-380x988.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-550x1430.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-800x2080.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4-1160x3017.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-4.png 1269w\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Create an auxiliary array of size <strong>N + M.<\/strong><\/li><li>Put two pointers <strong>i<\/strong> and <strong>j<\/strong> and initialise them to 0.\u00a0<\/li><li><strong>Pointer<\/strong> <strong>i<\/strong> points to the first array, whereas <strong>pointer j<\/strong> points to the second array.<\/li><li>Traverse both the array simultaneously using the pointers, and pick the smallest elements among both the array and insert in into the auxiliary array.<\/li><li>Increment the pointers.<\/li><li>After traversal, return the merged array.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ 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 mergeArrays(int arr1[], int arr2[], int n1,\n  int n2, int arr3[]) {\n  int i = 0, j = 0, k = 0;\n  while (i &lt; n1 &amp;&amp; j &lt; n2) {\n    if (arr1[i] &lt; arr2[j])\n      arr3[k++] = arr1[i++];\n    else\n      arr3[k++] = arr2[j++];\n  }\n  while (i &lt; n1)\n    arr3[k++] = arr1[i++];\n \n  while (j &lt; n2)\n    arr3[k++] = arr2[j++];\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java 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=\"\">public static void mergeArrays(int[] arr1, int[] arr2, int n1,\n  int n2, int[] arr3) {\n  int i = 0, j = 0, k = 0;\n  while (i &lt; n1 &amp;&amp; j &lt; n2) {\n    if (arr1[i] &lt; arr2[j])\n      arr3[k++] = arr1[i++];\n    else\n      arr3[k++] = arr2[j++];\n  }\n  while (i &lt; n1)\n    arr3[k++] = arr1[i++];\n \n  while (j &lt; n2)\n    arr3[k++] = arr2[j++];\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python 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 mergeArrays(arr1, arr2, n1, n2):\n    arr3 = [None] * (n1 + n2)\n    i = 0\n    j = 0\n    k = 0\n \n    while i &lt; n1 and j &lt; n2:\n        if arr1[i] &lt; arr2[j]:\n            arr3[k] = arr1[i]\n            k = k + 1\n            i = i + 1\n        else:\n            arr3[k] = arr2[j]\n            k = k + 1\n            j = j + 1\n \n    while i &lt; n1:\n        arr3[k] = arr1[i]\n        k = k + 1\n        i = i + 1\n \n    while j &lt; n2:\n        arr3[k] = arr2[j]\n        k = k + 1\n        j = j + 1<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N + M), where N and M is the size of array A[] and B[]<br><strong>Space Complexity:<\/strong>O(N + M), as the auxiliary array is used<\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p>How is the space complexity O(1) for the two-pointers approach?<br>Since, we are in placing merging all the elements into the first array, without creating any other auxiliary space, the space complexity is O(1)<\/p>\n\n\n\n<p><strong>How is the two pointer approach different from the merge sort approach?<br><\/strong>The merge sort approach considers an auxiliary array to sort and keeps two-pointer and the beginning of the array and merges accordingly.<\/p>\n\n\n\n<p>Whereas, the two-pointer approach, starts iterating from backward and keeps merging the elements in place.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two sorted arrays A[] and B[] of size N and M. The task is to&hellip;\n","protected":false},"author":5,"featured_media":3533,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","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":[551],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3531"}],"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=3531"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3531\/revisions"}],"predecessor-version":[{"id":3575,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3531\/revisions\/3575"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3533"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}