My C# solution, beats 87% - O(n) complexity and O(1) space


  • 0
    N
    
    public void NextPermutation(int[] nums) 
        {
            if(nums.Length < 2)
            return;
            
            int i = nums.Length-1;
            
            while (i > 0)
            {
                if(nums[i] > nums[i-1])
                {
                    int j = nums.Length -1;
                    
                    while(j >=0 && nums[j] <= nums[i-1])
                    {
                        j--;
                    }
                    if(i >= 0)
                    {
                        int temp = nums[i-1];
                        nums[i-1] = nums[j];
                        nums[j] = temp;
                        Reverse(ref nums, i, nums.Length-1);
                    }
                    return;
                }
                i--;
            }
            
            Reverse(ref nums, 0, nums.Length-1);
        }
        public void Reverse(ref int[]nums,  int startIndex,  int endIndex)
        {
            int temp;
            while(startIndex < endIndex)
            {
                temp = nums[startIndex];
                nums[startIndex] = nums[endIndex];
                nums[endIndex] = temp;
                startIndex++;
                endIndex--;
            }
        }
    

Log in to reply
 

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