Largest Permutation Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Largest Permutation
  5. Discussions

Largest Permutation

Sort by

recency

|

387 Discussions

|

  • patrickgao2020
     + 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

  • alban_tyrex
     + 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;
}

  • emhhacker
     + 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;
    }

  • saminazubair93
     + 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;

  • CS_2212256_T
     + 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]+" ");
    }
}