{"id":2664,"date":"2021-10-14T11:00:00","date_gmt":"2021-10-14T05:30:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2664"},"modified":"2022-09-05T16:28:03","modified_gmt":"2022-09-05T10:58:03","slug":"rearrange-array-alternately","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/rearrange-array-alternately\/","title":{"rendered":"Rearrange Array Alternately"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" 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=\"#auxiliary-space-approach\">Auxiliary Space Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-auxiliary-space-approach\">C++ Code For Auxiliary Space Approach<\/a><\/li><li><a href=\"#java-code-for-auxiliary-space-approach\">Java Code For Auxiliary Space Approach<\/a><\/li><li><a href=\"#python-code-for-auxiliary-space-approach\">Python Code For Auxiliary Space Approach<\/a><\/li><\/ul><li><a href=\"#constant-space-approach---efficient-approach\">Constant Space Approach &#8211; Efficient Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-constant-space-approach\">C++ Code For Constant Space Approach<\/a><\/li><li><a href=\"#java-code-for-constant-space-approach\">Java Code For Constant Space Approach<\/a><\/li><li><a href=\"#python-code-for-constant-space-approach\">Python Code For Constant Space Approach<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a sorted array A[] consisting of <strong>N<\/strong> integers. The task is to rearrange the array alternatively i.e. the first element should be maxed value, second should be min value, third should be the second max, fourth should be the second min, and so on.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input: <\/strong>A[] = {1, 2, 3, 4, 5, 6, 7}<br><strong>Output: <\/strong>{7, 1, 6, 2, 5, 3, 4}<br><strong>Explanation:<\/strong><br><meta charset=\"utf-8\"><\/p>\n\n\n\n<p><strong>Input: <\/strong>A[] = {1, 2, 3, 4, 5, 6}<br><strong>Output:<\/strong> {6, 1, 5, 2, 4, 3}<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"auxiliary-space-approach\">Auxiliary Space Approach<\/h2>\n\n\n\n<p>The idea is to use a two-pointer<strong> <\/strong>approach. The below diagram shows the approach<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"423\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"two pointer approach\"  class=\"wp-image-2742 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 423px) 100vw, 423px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-423x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-423x1024.png 423w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-124x300.png 124w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-635x1536.png 635w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-380x919.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach-550x1331.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/two-pointer-approach.png 653w\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Consider two pointers <strong>low = 0 <\/strong>and <strong>high = N &#8211; 1<\/strong>, which are pointing to the first and last element of the array.<\/li><li>Create a <strong>temp[] <\/strong>array for storing the resultant array.<\/li><li>Start copying the last element of the array followed by the first element and so on into the <strong>temp array.<\/strong><\/li><li>Repeat the above process, until the <strong>low <\/strong>pointer becomes less than or equal to the <strong>high <\/strong>pointer<strong>.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-auxiliary-space-approach\">C++ Code For Auxiliary Space Approach<\/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=\"\"> \nvoid rearrange(int A[], int N)\n{\n    int temp[N];\n    int low = 0, high = N - 1;\n    int flag = true;\n    \n    for (int i = 0; i &lt; N; i++) {\n        if (flag)\n            temp[i] = A[high--];\n        else\n            temp[i] = A[low++];\n \n        flag = !flag;\n    }\n    for (int i = 0; i &lt; N; i++)\n        A[i] = temp[i];\n}<\/pre>\n\n\n\n<h3 id=\"java-code-for-auxiliary-space-approach\">Java Code For Auxiliary Space Approach<\/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 rearrange(int[] A, int N)\n    {\n        int temp[] = A.clone();\n        int low = 0, high = N - 1;\n        boolean flag = true;\n \n        \/\/ Store result in temp[]\n        for (int i = 0; i &lt; N; i++) {\n            if (flag)\n                A[i] = temp[high--];\n            else\n                A[i] = temp[low++];\n \n            flag = !flag;\n        }\n    }<\/pre>\n\n\n\n<h3 id=\"python-code-for-auxiliary-space-approach\">Python Code For Auxiliary Space Approach<\/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 rearrange(A, N):\n    temp = N*[None]\n    low, high = 0, N - 1\n \n    flag = True\n \n    for i in range(N):\n        if flag is True:\n            temp[i] = A[high]\n            high -= 1\n        else:\n            temp[i] = A[low]\n            low += 1\n \n        flag = bool(1-flag)\n \n    for i in range(N):\n        A[i] = temp[i]\n    return A<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) where N is the size of the array <strong>A[]<\/strong>.<br><strong>Space Complexity:<\/strong> O(N), as extra space, is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"constant-space-approach---efficient-approach\"><span id=\"constant-space-approach-efficient-approach\">Constant Space Approach &#8211; Efficient Approach<\/span><\/h2>\n\n\n\n<p>The efficient approach solves the problem in place without considering any auxiliary array.<\/p>\n\n\n\n<p>The idea is to use multiplication and modular tricks to store two elements at the same index. Observe the below example<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"744\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"multiplication and modular tricks\"  class=\"wp-image-2744 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 744px) 100vw, 744px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/multiplication-and-modular-tricks.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/multiplication-and-modular-tricks.png 744w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/multiplication-and-modular-tricks-300x202.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/multiplication-and-modular-tricks-380x255.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/multiplication-and-modular-tricks-550x370.png 550w\" ><\/figure>\n\n\n\n<p>We will use the same approach to solve the problem.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialize two pointers <strong>max_idx = <strong>N &#8211; 1<\/strong> <\/strong>and <strong>min_idx =0 <\/strong>, where N is the size of the array.<\/li><li>Initialise an element <strong>mx <\/strong>equal to <strong>1 + maximum element <\/strong>of the array. <strong>Note: <\/strong>You can initialise <strong>mx<\/strong> to any integer greater than the maximum element.&nbsp;<\/li><li>Iterate over the array and perform the following operations:<ul><li>If the current index is <strong>even<\/strong>:<ul><li>Update <strong>A[i] = A[i] + (A[max_idx] % mx) * mx<\/strong><\/li><li>Decrement <strong>max_idx <\/strong>by 1.<\/li><\/ul><\/li><li>If the current index is <strong>odd<\/strong>:<ul><li>Update <strong>A[i] = A[i] + (A[min_idx] % mx) * mx<\/strong><\/li><li>Increment <strong>min_idx <\/strong>by 1.<\/li><\/ul><\/li><\/ul><\/li><li>To update the array element back to its original form, divide <strong>A[i]<\/strong> by <strong>mx<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-constant-space-approach\">C++ Code For Constant Space Approach<\/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 rearrange(int A[], int N)\n{\n    int max_idx = N - 1, min_idx = 0;\n    int max_elem = A[N - 1] + 1;\n    for (int i = 0; i &lt; N; i++) {\n        if (i % 2 == 0) {\n            A[i] += (A[max_idx] % max_elem) * max_elem;\n            max_idx--;\n        }\n        else {\n            A[i] += (A[min_idx] % max_elem) * max_elem;\n            min_idx++;\n        }\n    }\n    for (int i = 0; i &lt; N; i++)\n        A[i] = A[i] \/ max_elem;\n}<\/pre>\n\n\n\n<h3 id=\"java-code-for-constant-space-approach\">Java Code For Constant Space Approach<\/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 rearrange(int A[], int N){\n        int max_idx = N - 1, min_idx = 0;\n        int mx = A[N - 1] + 1;\n        for (int i = 0; i &lt; N; i++) {\n            if (i % 2 == 0) {\n                A[i] += (A[max_idx] % mx) * mx;\n                max_idx--;\n            }\n            else {\n                A[i] += (A[min_idx] % mx) * mx;\n                min_idx++;\n            }\n        }\n        for (int i = 0; i &lt; N; i++)\n            A[i] = A[i] \/ mx;\n    }<\/pre>\n\n\n\n<h3 id=\"python-code-for-constant-space-approach\">Python Code For Constant Space Approach<\/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 rearrange(A, N):\n    max_idx = N - 1\n    min_idx = 0\n \n    mx = A[N-1] + 1\n \n    for i in range(0, N) :\n        if i % 2 == 0 :\n            A[i] += (A[max_idx] % mx ) * mx\n            max_idx -= 1\n \n        else :\n            A[i] += (A[min_idx] % mx ) * mx\n            min_idx += 1\n \n    for i in range(0, N) :\n        A[i] = A[i] \/ mx<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(N) where N is the size of the array <strong>A[]<\/strong>.<br><strong>Space Complexity: <\/strong>O(1), as no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/rearrange-array\/\" target=\"_blank\" rel=\"noreferrer noopener\">Rearrange Array<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the time and complexity of arranging in max-min form?<br><\/strong>The time complexity is <strong>O(N)<\/strong>. The space complexity is <strong>O(N)<\/strong> for the naive approach and O(1) using the efficient approach.<\/p>\n\n\n\n<p><strong>Do you need to sort the array A[]?<\/strong><strong><br><\/strong>If the given array is unsorted, then we need to sort the array first and then apply the given approach.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a sorted array A[] consisting of N integers. The task is to rearrange the array&hellip;\n","protected":false},"author":4,"featured_media":2741,"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":[455],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2664"}],"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\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2664"}],"version-history":[{"count":10,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2664\/revisions"}],"predecessor-version":[{"id":11092,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2664\/revisions\/11092"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2741"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2664"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2664"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2664"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}