Accepted Java Solution O(n) with explanations

  • 0


    • 1.Traverse from right and identify the element such that num[i] < num[i+1] i.e. it breaks descending rule
    • a) If match not found we have reached the last element, so reverse the order of all elements
    • b) If match found, then traverse from right and identify the first element say num[i+x] that is greater than num[i]. Swap num[i] and num[i+x] and then reverse the order of elements to the right of num[i+x]

    (i) 3,2,1 -> 1,2,3 (1a)
    (ii) 1,3,2 -> 2,1,3 (1b)

    • 1 breaks descending rule
    • Swap(1,2) i.e. 2,3,1
    • Reverse all elements to the the right of 2 i.e. 2,1,3
    public static int[] nextPermutation(int[] nums) {
            if(nums.length == 0) {
                return null;
            boolean isMatch = false;
            int i = nums.length-2;
            for( ; i>=0; ) {
                if(nums[i] < nums[i+1]) {
                    isMatch = true;
            if(isMatch) {
                //Found an element that breaks the descending rule (1b)
                //Find an element > nums[i+x] that is greater than num[i]
                int j=nums.length - 1;
                for(; j>i;) {
                    if(nums[j] > nums[i])
                swap(nums, i, j);
                //Note: Since i and j are swapped, reverse the elements to right of index i+1
                reverse(nums, i+1, nums.length-1);
            } else {
                //Not Found an element that breaks the descending rule (1a), i.e. we have reached the end of lexicographical order
                //Reverse all elements to get the first element in lexicographical order
                reverse(nums, 0, nums.length-1);
            return nums;
        public static void reverse(int[] nums, int s, int e){
            while(s < e){
                swap(nums, s, e);
        public static void swap(int[] nums, int s, int e){
            int t = nums[s];
            nums[s] = nums[e];
            nums[e] = t;
        public static void main(String[] args) {
            nextPermutation(new int[] {1,3,2}); //2,1,3
            nextPermutation(new int[] {3,2,1}); //1,2,3

    Note: I have a return type of int[] to allow running some unit tests. Hope this helps.
    Special thanks to hot13399 who provided the detailed algorithm here:

  • 0
    This post is deleted!

Log in to reply

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