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

|

385 Discussions

|

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

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

  • pub_ashishk28
     + 0 comments

    Python3

    def largestPermutation(k, arr):
    # Write your code here
        
    n = len(arr) 
    D =  { v:k for k,v in enumerate(arr) } # dict lookup >>> arr.index()
    
    c = 0
    for i in range(n): 
        if arr[i]!=n-i:  # In sorted array, n-i should be at index i
            D[arr[i]] = D[n-i] # if not then update indexes
            arr[i],arr[D[n-i]]=n-i,arr[i] # do swap
            c = c + 1

        if c == k: #break if runs out of swaps
            break
    return arr

  • dorirgob
     + 0 comments

    Java:

    public static List<Integer> largestPermutation(int k, List<Integer> arr) {
  int n = arr.size();
  int max = n;
  int[] indexMap = new int[max + 1];

  for (int i = 0; i < n; i++) {
    indexMap[arr.get(i)] = i;
  }

  for (int i = 0; i < n && k > 0; i++) {
    int currentValue = arr.get(i);
    int targetValue = n - i;
    if (currentValue != targetValue) {
      int targetIndex = indexMap[targetValue];
      arr.set(targetIndex, currentValue);
      arr.set(i, targetValue);
      indexMap[currentValue] = targetIndex;
      indexMap[targetValue] = i;
      k--;
    }
  }
  return arr;
}