{"id":284,"date":"2021-04-06T19:31:43","date_gmt":"2021-04-06T19:31:43","guid":{"rendered":"https:\/\/uqcodewall.com\/?page_id=284"},"modified":"2021-04-18T20:09:11","modified_gmt":"2021-04-18T20:09:11","slug":"31-next-permutation","status":"publish","type":"page","link":"https:\/\/uqcodewall.com\/?page_id=284","title":{"rendered":"31. Next Permutation"},"content":{"rendered":"\n

\/**<\/p>\n\n\n\n

 * 31. Next Permutation<\/p>\n\n\n\n

 * Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.<\/p>\n\n\n\n

 * If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).<\/p>\n\n\n\n

 * The replacement must be in place and use only constant extra memory.<\/p>\n\n\n\n

 *\/<\/p>\n\n\n\n

See solution to the problem on github here: https:\/\/github.com\/zcoderz\/leetcode\/blob\/main\/src\/main\/java\/frequent\/medium\/NextPermutation.java<\/a><\/p>\n\n\n\n

This is unfair question to ask on interviews as it requires a fair amount of pre hand knowledge regarding lexicographic permutations to be able to solve this in a short amount of time.<\/p>\n\n\n\n

But the question is interesting in that it explores flow of numbers in permutations, which is good to understand and hence I have included it here.<\/p>\n\n\n\n

Some facts regarding lexicographic permutations:<\/p>\n\n\n\n

  1. A decreasing array is the last permutation of the array, and the next one is the reverse of it. For example, `3,2,1` is the last permutation of this array and `1,2,3` will be next.<\/li>
  2. For a decreasing subarray there is a number before the decreasing subarray which \u2018leads\u2019 to the decreasing subarray. I,e  for array \u20184,7,6,5,3,2,1\u2019 4 is the leading number before the decreasing subarray \u20187,6,5,3,2,1\u2019. The logic to find the next permutation here is:
    1. Swap the leading 4 with the number that is greater than itself, in this case 5 so the array would become 5,7,6,4,3,2,1<\/li><\/ol>
      1. Reverse the decreasing subarray to right of the subarray I,e reverse the subarray to right of 4 above so that the array becomes 5,1,2,3,4,6,7<\/li><\/ol><\/li><\/ol>\n\n\n\n

         You can look at this article on wiki pedia to understand more about permutations: https:\/\/en.wikipedia.org\/wiki\/Permutation       <\/p>\n\n\n\n

        Here is the code:<\/h4>\n\n\n
        \npublic void nextPermutation(int[] nums) {\n    \/\/step 1: find first index thats not in descending order from right\n    int j = nums.length-1; boolean nonDesc = false;\n    for (; j>0; j--) {\n        if (nums[j-1] < nums[j]) {\n            nonDesc = true;\n            j--;\n            break;\n        }\n    }\n    if (!nonDesc) {\n        Arrays.sort(nums);\n        return;\n    }\n    \/\/step 2: find first index from right thats higher than the index found above\n    int i = nums.length-1;\n    for (; i > j; i--) {\n        if (nums[i] > nums[j]) {\n            break;\n        }\n    }\n    \/\/step 3: swap i and j\n    swap(nums, i, j);\n    \/\/step 4: the index right of this index are in descending order, change them to be in ascending order\n    for (i =j+1, j = nums.length-1; j > i; j--,i++) {\n        swap(nums, i, j);\n    }\n}\n<\/pre><\/div>\n\n\n
        <\/p>\n","protected":false},"excerpt":{"rendered":"
        \/**  * 31. Next Permutation  * Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.  * If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).  * The replacement must be in place and use only constant extra memory.Continue reading “31. Next Permutation”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"wf_page_folders":[21],"class_list":["post-284","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=284"}],"version-history":[{"count":5,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/284\/revisions"}],"predecessor-version":[{"id":1068,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/284\/revisions\/1068"}],"wp:attachment":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=284"}],"wp:term":[{"taxonomy":"wf_page_folders","embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fwf_page_folders&post=284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}