//compare function (utility function for qsort)

int compare (const void* a,const void* b) {

return ( *(int*)a - *(int*)b);

}

class Solution {

public:

void nextPermutation(vector<int> &num) {

```
int len =num.size();
int *arr;
arr= new int[len];
// copying elements given in vector form to array arr[]
for (int i=0;i<len;i++)
arr[i]=num[i];
// finding next permutation of arr[]
nextnum(arr,len);
// copying back to vector
for (int i=0;i<len;i++)
num[i]=arr[i];
```

}

```
void nextnum(int* arr,int size) {
// initially start from 2nd last index
int i=size-2;
//store last element as pre
int pre = arr[size-1];
//find first element from right which is smaller than element at its right
while (i>=0&&arr[i]>=pre){
pre = arr[i];
i--;
}
//if no found sort arr[] in asending order
if (i==-1) {
qsort((void*)arr,size,sizeof (int) ,compare);
return ;
}
//if found
else {
//find ceilling from arr in its right-side of element found
int ceilling=i+1;
for (int j=i+2;j<size;j++)
if (arr[j]>arr[i]&&arr[j]<arr[ceilling])
ceilling=j;
//swap element with its ceil
int temp=arr[i];
arr[i]=arr[ceilling];
arr[ceilling]=temp;
//sort remaining arr in its right
qsort(arr+i+1,size-i,sizeof (int),compare);
}
}
```

};