Next Permutation by O(n)

import java.util.*;

public class Solution {

    public static List< Integer > nextGreaterPermutation(List< Integer > A) {

        // Write your code here

        int n= A.size();

        int dip_idx = -1;

        for(int i=n-2; i>=0; i--)

        {

            if(A.get(i)<A.get(i+1))

            {

                dip_idx = i;

                break;

            }

        }

        if(dip_idx== -1)

        {

            Collections.reverse(A);

        }

        for(int i=n-1;i>=dip_idx;i--)

        {

            if(A.get(i)>A.get(dip_idx))

            {

                int temp=A.get(dip_idx);

                A.set(dip_idx,A.get(i));

                A.set(i,temp);

                break;

            }

        }

        Collections.reverse(A.subList(dip_idx+1, n));

        return A;

    }

}