{"id":3593,"date":"2021-11-12T11:53:37","date_gmt":"2021-11-12T06:23:37","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3593"},"modified":"2021-11-12T11:53:38","modified_gmt":"2021-11-12T06:23:38","slug":"next-permutation-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/next-permutation-problem\/","title":{"rendered":"Next Permutation Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><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=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><li><a href=\"#approach-2-linear-solution\">Approach 2: Linear Solution<\/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=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given an array <strong>A[]<\/strong> of <strong>N<\/strong> distinct integers. The task is to return the lexicographically greater permutation than the given arrangement. If no such arrangement is possible, return the array sorted in non-decreasing order.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: A[] <\/strong>= [1, 2, 3]<br><strong>Output:<\/strong> [1, 3, 2]<br><strong>Explanation: <\/strong>The lexicographically greater permutation than <strong>A[]<\/strong> is [1, 3, 2]\n\n\n\n<p><strong>Input: <\/strong>&nbsp;A[] = [4, 3, 2, 1]\n\n\n\n<p><strong>Output:<\/strong> [1, 2, 3, 4]\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>A simple approach to solve this problem is to generate all the permutations of the given array and return the permutation which is just greater than the given array.<br>But this approach is very naive and won\u2019t work for N &gt; 10.<\/p>\n\n\n\n<p><br><strong>Time Complexity<\/strong>: O(N * N!), since total possible permutations are N!<br><strong>Space Complexity<\/strong>: O(N), since the permutation is stored.<\/p>\n\n\n\n<h2 id=\"approach-2-linear-solution\">Approach 2: Linear Solution<\/h2>\n\n\n\n<p>In the last approach, we were trying to find all possible permutations. It takes an undeniably large time. So how can we improve it?<\/p>\n\n\n\n<p>The problem can be solved using a simple trick.\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/<\/p>\n\n\n\n<p>Let us understand this with the help of an example:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"955\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Linear Solution\"  class=\"wp-image-3715 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 955px) 100vw, 955px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-955x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-955x1024.png 955w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-280x300.png 280w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-768x823.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-1433x1536.png 1433w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-380x407.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-550x590.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-800x858.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution-1160x1244.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Linear-Solution.png 1458w\" ><\/figure>\n\n\n\n<p>In the above example, we have followed four simple steps:<\/p>\n\n\n\n<ul><li>Find the first index, say <strong>idx<\/strong>, where <strong>A[i] &lt; A[i + 1]<\/strong>.<\/li><li>Find the first index,<strong> <\/strong>say <strong>ind,<\/strong> where <strong>A[i] &gt; A[idx]<\/strong><\/li><li>Swap <strong>A[idx] <\/strong>and <strong>A[ind]<\/strong>.<\/li><li>Reverse all elements from <strong>idx + 1<\/strong> till the end of the array.<\/li><\/ul>\n\n\n\n<p>But why does this work?<\/p>\n\n\n\n<p>Recall the problem. We need to find the permutation just greater than the current arrangement given.<br>So, if we traverse from the end of the array, there will be an index where the current element is smaller than the previous element. This ensures that all the elements to its right are larger than the current element.<br>Now, to get the next greater arrangement, the most optimal approach would be to find the element which is just greater than the current found element.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"718\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"next greater arrangement\"  class=\"wp-image-3718 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\/next-greater-arrangement-1024x718.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-1024x718.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-300x210.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-768x539.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-380x267.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-550x386.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-800x561.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement-1160x814.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/next-greater-arrangement.png 1458w\" ><\/figure>\n\n\n\n<p>So, now after swapping, we have found the pivot element. But we still have not got the required permutation. Therefore, simply sort the elements from the pivot till the end to get the required permutation.<\/p>\n\n\n\n<p>The following example will make the approach more clear.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"391\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"descending element\"  class=\"wp-image-3720 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\/descending-element-1024x391.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-1024x391.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-300x115.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-768x293.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-380x145.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-550x210.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-800x305.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element-1160x443.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/descending-element.png 1354w\" ><\/figure>\n\n\n\n<p><strong>Algorithm :<\/strong><\/p>\n\n\n\n<ul><li>Traverse the array from end and find the first index<strong>, idx<\/strong> such that <strong>A[i] &lt; A[i + 1]<\/strong>.<\/li><li>Again traverse the array from the end and find the first index<strong>, ind<\/strong> such that <strong>A[i] &gt; A[idx]<\/strong>.<\/li><li>Swap <strong>A[idx]<\/strong> and <strong>A[ind]<\/strong>.<\/li><li>Reverse the array from <strong>idx + 1<\/strong> till <strong>N<\/strong>.<\/li><li>The base case would be, if the array is in decreasing order, no next permutation will be found, hence return the array in sorted order.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/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 nextPermutation(vector &lt; int > &amp; nums) {\n  int n = nums.size(), k, l;\n  for (k = n - 2; k >= 0; k--) {\n    if (nums[k] &lt; nums[k + 1]) {\n      break;\n    }\n  }\n  if (k &lt; 0) {\n    reverse(nums.begin(), nums.end());\n  } else {\n    for (l = n - 1; l > k; l--) {\n      if (nums[l] > nums[k]) {\n        break;\n      }\n    }\n    swap(nums[k], nums[l]);\n    reverse(nums.begin() + k + 1, nums.end());\n  }\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 nextPermutation(int[] A) {\n  if (A == null || A.length &lt;= 1) return;\n  int i = A.length - 2;\n  while (i >= 0 &amp;&amp; A[i] >= A[i + 1]) i--; \n  if (i >= 0) { \n    int j = A.length - 1; \n    while (A[j] &lt;= A[i]) j--; \n    swap(A, i, j); \n  }\n  reverse(A, i + 1, A.length - 1); \n}\n \npublic void swap(int[] A, int i, int j) {\n  int tmp = A[i];\n  A[i] = A[j];\n  A[j] = tmp;\n}\n \npublic void reverse(int[] A, int i, int j) {\n  while (i &lt; j) swap(A, i++, j--);\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 nextPermutation(self, nums):\n    i = j = len(nums) - 1\n    while i > 0 and nums[i - 1] >= nums[i]:\n        i -= 1\n    if i == 0:\n        nums.reverse()\n        return\n    k = i - 1\n    while nums[j] &lt;= nums[k]:\n        j -= 1\n    nums[k], nums[j] = nums[j], nums[k]\n    l, r = k + 1, len(nums) - 1\n    while l &lt; r:\n        nums[l], nums[r] = nums[r], nums[l]\n        l += 1\n        r -= 1<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the total size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<p><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/next-permutation\/\" target=\"_blank\" rel=\"noreferrer noopener\">Next Permutation<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What if the input array is sorted in decreasing order?<\/strong><strong><br><\/strong>If the array is sorted in decreasing order, simply sort it in ascending order, since no greater permutation would be possible for such an array.<\/li><\/ul>\n\n\n\n<ul><li><strong>What is the approach to solve the Next Permutation problem?<\/strong><strong><br><\/strong>The idea is to find the longest non-increasing suffix and swap it with the pivot element found. Pivot element is the index where A[i] &lt; A[i + 1]. At last reversing the suffix, gives us the next greater permutation.<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given an array A[] of N distinct integers. The task is to return the lexicographically greater permutation than&hellip;\n","protected":false},"author":5,"featured_media":3713,"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":[556],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3593"}],"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=3593"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3593\/revisions"}],"predecessor-version":[{"id":3738,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3593\/revisions\/3738"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3713"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}