Next Permutation

                                            
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        
        reverse(nums.begin() + i + 1, nums.end());
    }
};

                                            
class Solution {
    public void nextPermutation(int[] nums) {
        // Find the first decreasing element from the right
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // Find the element to swap with
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

                                            
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place 
instead.
        """
        
        # Find the first decreasing element from the right
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        
        # Find the element just larger than nums[i]
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        
        # Reverse the elements from i+1 to the end
        left, right = i+1, len(nums)-1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

                                            
void nextPermutation(int* nums, int numsSize) {
    int i = numsSize - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = numsSize - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    int left = i + 1;
    int right = numsSize - 1;
    while (left < right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

                                            
public class Solution {
    public void NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        
        if (i >= 0) {
            int j = nums.Length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            Swap(nums, i, j);
        }
        
        Reverse(nums, i + 1);
    }
    
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void Reverse(int[] nums, int start) {
        int i = start, j = nums.Length - 1;
        while (i < j) {
            Swap(nums, i, j);
            i++;
            j--;
        }
    }
}

                                            
/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;

    // Find the first decreasing element from the right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        let j = nums.length - 1;

        // Find the next greater element from the right
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }

        // Swap the elements at positions i and j
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    // Reverse the subarray from i+1 to the end
    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function nextPermutation(&$nums) {
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
            $i--;
        }
        if ($i >= 0) {
            $j = count($nums) - 1;
            while ($nums[$j] <= $nums[$i]) {
                $j--;
            }
            $this->swap($nums, $i, $j);
        }
        $this->reverse($nums, $i + 1);
    }
    
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
    
    function reverse(&$nums, $start) {
        $i = $start;
        $j = count($nums) - 1;
        while ($i < $j) {
            $this->swap($nums, $i, $j);
            $i++;
            $j--;
        }
    }
}

                                            
class Solution {
    func nextPermutation(_ nums: inout [Int]) {
        var i = nums.count - 2
        
        while i >= 0 && nums[i] >= nums[i + 1] {
            i -= 1
        }
        
        if i >= 0 {
            var j = nums.count - 1
            while j >= 0 && nums[j] <= nums[i] {
                j -= 1
            }
            nums.swapAt(i, j)
        }
        
        reverse(&nums, start: i + 1)
    }
    
    func reverse(_ nums: inout [Int], start: Int) {
        var i = start
        var j = nums.count - 1
        while i < j {
            nums.swapAt(i, j)
            i += 1
            j -= 1
        }
    }
}

                                            
class Solution {
    fun nextPermutation(nums: IntArray): Unit {
        var k = nums.lastIndex - 1
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--
        }
        
        if (k == -1) {
            nums.reverse()
            return
        }
        
        var l = nums.lastIndex
        while (l > k && nums[l] <= nums[k]) {
            l--
        }
        
        nums[k] = nums[l].also { nums[l] = nums[k] }
        var left = k + 1
        var right = nums.lastIndex
        while (left < right) {
            nums[left] = nums[right].also { nums[right] = nums[left] }
            left++
            right--
        }
    }
}

                                            
class Solution {
  void nextPermutation(List<int> nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i + 1] <= nums[i]) {
      i--;
    }
    
    if (i >= 0) {
      int j = nums.length - 1;
      while (j >= 0 && nums[j] <= nums[i]) {
        j--;
      }
      swap(nums, i, j);
    }
    
    reverse(nums, i + 1);
  }
  
  void swap(List<int> nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
  
  void reverse(List<int> nums, int start) {
    int i = start;
    int j = nums.length - 1;
    while (i < j) {
      swap(nums, i, j);
      i++;
      j--;
    }
  }
}

                                            
func nextPermutation(nums []int)  {
    n := len(nums)
    i := n - 2
    for i >= 0 && nums[i+1] <= nums[i] {
        i--
    }
    if i >= 0 {
        j := n - 1
        for j >= 0 && nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(nums[i+1:])
}

func reverse(nums []int) {
    i, j := 0, len(nums)-1
    for i < j {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
}

                                            
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
    i = nums.length - 2
    while i >= 0 && nums[i] >= nums[i + 1]
        i -= 1
    end
    
    if i >= 0
        j = nums.length - 1
        while j >= 0 && nums[j] <= nums[i]
            j -= 1
        end
        nums[i], nums[j] = nums[j], nums[i]
    end
    
    nums[i+1..] = nums[i+1..].reverse
end

                                            
object Solution {
    def nextPermutation(nums: Array[Int]): Unit = {
        var i = nums.length - 2
        while (i >= 0 && nums(i) >= nums(i + 1)) {
            i -= 1
        }
        
        if (i >= 0) {
            var j = nums.length - 1
            while (j >= 0 && nums(j) <= nums(i)) {
                j -= 1
            }
            swap(nums, i, j)
        }
        
        reverse(nums, i + 1)
    }
    
    def swap(nums: Array[Int], i: Int, j: Int): Unit = {
        val temp = nums(i)
        nums(i) = nums(j)
        nums(j) = temp
    }
    
    def reverse(nums: Array[Int], start: Int): Unit = {
        var i = start
        var j = nums.length - 1
        while (i < j) {
            swap(nums, i, j)
            i += 1
            j -= 1
        }
    }
}

                                            
impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        let mut i = nums.len() as i32 - 2;
        while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
            i -= 1;
        }
        
        if i >= 0 {
            let mut j = nums.len() as i32 - 1;
            while j >= 0 && nums[j as usize] <= nums[i as usize] {
                j -= 1;
            }
            nums.swap(i as usize, j as usize);
        }
        
        nums[(i + 1) as usize..].reverse();
    }
}

To solve this coding challenge, we need to find the next permutation of a given list of integers. The goal is to rearrange the numbers to find the lexicographically next greater permutation. If this is not possible, the array should be rearranged to its lowest possible order (i.e., sorted in ascending order). This all needs to be done in-place using only constant extra memory.

Explanation

Identifying the Pivot Point (First Decreasing Element from Right):

First, we need to traverse the list from right to left to identify the first pair of consecutive elements (nums[i], nums[i+1]) where nums[i] < nums[i+1]. This element, nums[i], is called the pivot point.
If no such element is found (meaning the list is sorted in descending order), the next permutation is the list sorted in ascending order.

Finding the Element Just Larger than nums[i]:

Once we've identified nums[i], we need to find the smallest element to the right of nums[i] that is larger than nums[i]. This element will be swapped with nums[i] to get a slightly larger permutation.

Swapping and Reversing the Subarray:

After swapping, the subarray to the right of i (i.e., from i+1 to the end of the list) needs to be reversed to obtain the smallest lexicographic order for that subarray.

Detailed Steps in Pseudocode

Initialization : Start by setting an index to the second last element of the list.
Finding the Pivot :

Traverse from the end of the list moving left to find the first index 'i' such that nums[i] < nums[i+1].

Condition to Handle Reverse Sorted List :

If no such 'i' exists, reverse the entire list to get the smallest permutation.

Finding the Element Just Larger Than nums[i] :

Traverse again from the end of the list moving left to find the first index 'j' such that nums[j] > nums[i].

Swap Elements :

Swap the elements at indices 'i' and 'j'.

Reverse the Subarray :

Reverse the subarray from index 'i+1' to the end of the list.

Below is the pseudocode with comments to illustrate the methodology explained:

                                            
// Step 1: Find the first decreasing element from the right
index = length(nums) - 2  
while index >= 0 and nums[index] >= nums[index + 1] do
index = index - 1

// Step 2: If such an element exists, find the element just larger than nums[index]
if index >= 0 then
largerIndex = length(nums) - 1
while largerIndex >= 0 and nums[largerIndex] <= nums[index] do
largerIndex = largerIndex - 1

// Step 3: Swap nums[index] and nums[largerIndex]
temp = nums[index]
nums[index] = nums[largerIndex]
nums[largerIndex] = temp

// Step 4: Reverse the subarray from index + 1 to the end of the list
left = index + 1
right = length(nums) - 1
while left < right do
// Swap elements at left and right
temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left = left + 1
right = right - 1

Step-by-Step Explanation

Find the Pivot : Start from the second last element of the list and move leftwards while comparing each element with the next element. The goal is to find the first element that is smaller than the element to its right. This identifies the "pivot" element, which needs to be changed to get the next permutation.
Handle Special Case : If no such element is found (which means the list is in descending order), the entire list is reversed to make it ascending (the smallest possible permutation).
Locate Element for Swap : If such a "pivot" element is found, then another traversal from the list's end is done to find the smallest element that is larger than the pivot element.
Perform the Swap : Swap this found element with the pivot to make the permutation slightly larger.
Reverse the Tail : Finally, reverse the subarray from the pivot's next element to the list’s end to ensure it's the next immediate permutation in lexicographic order.

By following these steps, we can efficiently find the next permutation with an in-place modification and constant extra memory.