C# O(n) Solution


  • 0
    K

    We want to modify the least significant numbers first, so we start from the right hand side. We look for the first value that is decreasing (call it A). This is the position we want to modify to get the next lexicographically higher permutation. Scan for the first number (call it B) that is greater than the value we just found. Swap them. By replacing A with B, we increase the value of the permutation by the smallest amount. At the same time, A is in a sorted position, just like B before (the number to the right of A is smaller than it, otherwise it would have been chosen as B). Reverse the list from the index after where B was placed, to reset it back to the smallest value. (Right now it is in ascending order right to left).

    public class Solution {
        public void NextPermutation(int[] nums) {
            // Find the first index where less than prev number
            int firstDecreasing = -1;
            for(int i = nums.Length - 2; i >= 0; i--) {
                if(nums[i] < nums[i + 1]) {
                    firstDecreasing = i;
                    break;
                }
            }
            
            if(firstDecreasing == -1) {
                reverse(nums, 0, nums.Length - 1);
                return;
            }
            
            // Find number thats just greater than num[firstDecreasing] to replace it
            int replace = -1;
            for(int i = nums.Length - 1; i > firstDecreasing; i--) { 
                if(nums[i] > nums[firstDecreasing]) {
                    if(replace == -1 || nums[i] < nums[replace]){
                        replace = i;
                    }
                }
            }
            
            swap(nums, firstDecreasing, replace);
            reverse(nums, firstDecreasing + 1, nums.Length - 1);
        }
        
        private void swap(int[] nums, int a, int b) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
        
        private void reverse(int[] nums, int start, int end){
            int left = start;
            int right = end;
            while(left < right){
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.