Largest Permutation Hackerrank solution

Largest Permutation Hackerrank solution

  July 13, 2017    

---

Problem:

You are given an array of N integers which is a permutation of the first N natural numbers. You can swap any two elements of the array. You can make at most K swaps. Find the largest permutation

Approach:

Idea is to use index array and find n-i(maximum no. in n range for position i) and swap them.

Code:

import java.io.*;
import java.util.*;

public class Solution {
        public static void main(String[] args) {
     
        Scanner ab=new Scanner(System.in);
        int n=ab.nextInt();
        int k=ab.nextInt();
        int arr[]=new int[n];
            int index[]=new int[n+1];
        for(int i=0;i<n;i++)
           { arr[i]=ab.nextInt();
           index[arr[i]]=i;
           }
        for(int i=0;i<n && k>0;i++)
        {
            if(arr[i]==n-i)
                continue;
            arr[index[n-i]]=arr[i];
            index[arr[i]]=index[n - i];
            index[n-i]=i;
            arr[i]=n-i;
            k--;
        }
            for(int x:arr)
                System.out.print(x+" ");
    }
}