Easiest JAVA Solution


  • 48

    Using a simple example, we can derive the following steps:

    public void nextPermutation(int[] A) {
        if(A == null || A.length <= 1) return;
        int i = A.length - 2;
        while(i >= 0 && A[i] >= A[i + 1]) i--; // Find 1st id i that breaks descending order
        if(i >= 0) {                           // If not entirely descending
            int j = A.length - 1;              // Start from the end
            while(A[j] <= A[i]) j--;           // Find rightmost first larger id j
            swap(A, i, j);                     // Switch i and j
        }
        reverse(A, i + 1, A.length - 1);       // Reverse the descending sequence
    }
    
    public void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
    
    public void reverse(int[] A, int i, int j) {
        while(i < j) swap(A, i++, j--);
    }

  • 2
    R

    Nice solution. I believe that there is no need to test for i < j in this line. It will always be satisfied. :

    while(i < j && nums[j] <= nums[i]) j--;


  • 0

    @rohan99 Nice catch! I've updated my answer.


  • 0
    Y

    Hi @yavinci, great solution as always!


  • 0

    @yanggao Thanks!


  • 1
    Y

    there are two modifications I can think of:

    1. adding a check for corner cases, since array may not have length >= 2, you may need:

       if (nums == null || nums.length <= 1) {
           return;
       }
      
    2. move this inside of the if block to make it more logical:

       int j = nums.length - 1;

  • 0

    @yanggao, very nice catch. Updated. Thanks!


  • 0
    B
    This post is deleted!

  • 0

    This is so coollll!


Log in to reply
 

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