Largest Permutation Discussions | Algorithms | HackerRank

Largest Permutation

Sort by

recency

|

387 Discussions

|

  • + 0 comments

    Here is my Python solution. I had to import copy in order for this to work.

    def largestPermutation(k, arr):
        indices = {a: b for b, a in enumerate(arr)}
        for i in range(len(arr)):
            if k > 0:
                if arr[i] != len(arr) - i:
                    value = copy.deepcopy(arr[i])
                    arr[i], arr[indices[len(arr) - i]] = len(arr) - i, arr[i]
                    indices[value] = indices[len(arr) - i]
                    k -= 1
        return arr
    
  • + 0 comments

    Here is my c++ solution O(n), you also have a vidéo explanation here : https://youtu.be/baZOM6KLSWM

    vector<int> largestPermutation(int k, vector<int> arr) {
        map<int, int> indexes;
        for(int i = 0; i < arr.size(); i++) indexes[arr[i]] = i;
        
        int Mx = arr.size(), position = 0;
        while(k && position < arr.size()){
            if(arr[position] != Mx){
                int temps = arr[position];
                arr[position] = Mx;
                arr[indexes[Mx]] = temps;
                k--;
                indexes[temps] = indexes[Mx];
            }
            Mx--;
            position++;
        }
        
        return arr;
    }
    
  • + 0 comments

    My Java solution with linear time and space complexity:

    public static List<Integer> largestPermutation(int k, List<Integer> arr) {
            if(arr.size() == 1) return arr; //no permutations possible
            
            //get the indices of each val in arr
            Map<Integer, Integer> valMap = new HashMap<>();
            for(int i = 0; i < arr.size(); i++) valMap.put(arr.get(i), i);
            
            //store the max val as size of arr
            int max = arr.size(), j = 0;
            
            //iterate through the arr and do k permutations
            while(j < arr.size() && k > 0){
                if(arr.get(j) != max){
                    int temp = arr.get(j);
                    arr.set(j, max);
                    arr.set(valMap.get(max), temp);
                    valMap.put(temp, valMap.get(max));
                    k--;
                }
                max--;
                j++;
            }
            return arr;
        }
    
  • + 0 comments

    here is my php solution arr);

    for (`$i=0; $`i < `$n && $`k>0 ; $i++) { 
        if (`$arr[$`i] == `$n-$`i) {
           continue;
        }
        `$swapElement2Index = array_search($`n-`$i, $`arr);
        `$arr[$`swapElement2Index] = `$arr[$`i];
        `$arr[$`i] = `$n-$`i;
       $k--;
      }
    

    return $arr;

  • + 0 comments
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
    
        public static void main(String[] args) {
            Scanner scc = new Scanner(System.in);
            int n = scc.nextInt();
            int k = scc.nextInt();
            int arr[] = new int[n];
            for(int i=0; i<n; i++){
                arr[i] = scc.nextInt();
            }
            
            
            for(int i=0; i<k && i<n; i++){
                int j;
                for(j=i; j<n; j++){
                    if(arr[j]==n-i){
                        break;
                    }
                }
                if(j!=i){
                   int temp = arr[j];
                   arr[j] = arr[i];
                   arr[i] = temp;
                }
                else{
                    k++;
                }
            }
            
            for(int i=0; i<n; i++)
                System.out.print(arr[i]+" ");
        }
    }