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

|

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

  • shreyavishwalin1
     + 0 comments
    def largestPermutation(k, arr):
    n = len(arr)
    position_map = {value: idx for idx, value in enumerate(arr)}
    
    current_max = max(arr)
    for i in range(n):
        if k == 0:
            break
        
        if arr[i] != current_max:
            # Swap arr[i] and current_max
            arr[position_map[current_max]], arr[i] = arr[i], current_max
            # Update position_map
            position_map[arr[position_map[current_max]]] = position_map[current_max]
            position_map[current_max] = i
            # Decrement k
            k -= 1
        
        # Update current_max to the next largest number
        current_max -= 1
    
    return arr

  • aldufc
     + 0 comments

    Ruby

    def largestPermutation(k, arr)    
    array_swap = Array.new(arr.length)   
    arr.length.times { |i| array_swap[arr[i]] = i}        
    arr.length.times do |i|
        next if arr[i] == arr.length-i
        if k > 0
            index_change = array_swap[arr.length-i]
            array_swap[arr[i]] = index_change
            arr[i], arr[index_change] = arr[index_change], arr[i]    
            k -= 1
        end        
    end
    arr    
end

  • jamie_ryu
     + 0 comments

    //Java8 // Write your code here int indx=0; Integer tempData; while (k>0) { if(indx>=arr.size()-1){ break; } if(arr.size()!=0 && arr.size()>2){ Integer max = arr.stream().skip(indx).max(Integer::compare).get(); tempData = arr.get(indx); int mxindx = arr.indexOf(max); if(mxindx==indx){ indx++; }else{ arr.set(indx,max); arr.set(mxindx,tempData); indx++; k--; } }else if(arr.size()==1){ break;} else if (arr.size()==2){ Boolean flag = arr.get(0)>arr.get(1)?true:false; if(!flag){ int a = arr.get(0); int b = arr.get(1); arr.set(0, b); arr.set(1, a); k--; } break; } }

        return arr;

  • ihorfinance
     + 0 comments

    C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star :) )

    std::vector<int> largestPermutation(
        int _swaps
    ,   std::vector<int> _arr
){
    using namespace std;
    size_t dst = 0;
    for(auto it = begin(_arr);
        it != end(_arr) && _swaps != 0; ++it){
        dst = distance(it, end(_arr));
        if(dst == *it){
            continue;
        }
        swap(*it, *(find( it + 1, end(_arr), dst)));
        --_swaps;
    }
    return _arr;
}