HackerRank Largest Permutation Problem Solution

In this post, we will solve HackerRank Largest Permutation Problem Solution.

You are given an unordered array of unique integers incrementing from 1. You can swap any two elements a limited number of times. Determine the largest lexicographical value array that can be created by executing no more than the limited number of swaps.
Example
arr = [1,2,3,4]
k=1
The following arrays can be formed by swapping the 1 with the other elements:

[2,1,3,4]
[3,2,1,4]
[4,2,3,1]

The highest value of the four (including the original) is [4, 2, 3, 1]. If k> 2, we can swap to the highest possible value: [4, 3, 2, 1].

Function Description

Complete the largestPermutation function in the editor below. It must return an array that represents the highest value permutation that can be formed.

largestPermutation has the following parameter(s):

int k: the maximum number of swaps
int arr[n]: an array of integers

Output Format

Print the lexicographically largest permutation you can make with at most K swaps.
Sample Input 0

STDIN       Function
-----       --------
5 1         n = 5, k = 1
4 2 3 5 1   arr = [4, 2, 3, 5, 1]

Sample Output 0

5 2 3 4 1

HackerRank Largest Permutation Problem Solution

Largest Permutation C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void quicksort(int x[100000],int first,int last)
    {
    int i,j,temp,pivot;
    if(first<last)
        {
        i=first;
        j=last;
        pivot=first;
        while(i<j)
            {
            while(x[i]>=x[pivot]&&i<last)
                {
                i++;
            }
            while(x[j]<x[pivot])
                {
                j--;
            }
            if(i<j)
                {
                temp=x[i];
                x[i]=x[j];
                x[j]=temp;
            }
        }
        temp=x[pivot];
        x[pivot]=x[j];
        x[j]=temp;
        quicksort(x,first,j-1);
        quicksort(x,j+1,last);
    }
}
 main() {

    int i,j,k,l,m,n,p;
     scanf("%d %d\n",&n,&k);
     int a[n],b[n],d[n];
     for(i=0;i<n;i++)
         {
         scanf("%d ",&a[i]);
         b[i]=a[i];
             d[i]=a[i];
     }
     quicksort(b,0,n-1);
     int c[n];
     for(i=0;i<n;i++)
         {
         for(j=0;j<n;j++)
             {
             if(b[i]==d[j])
                 {
                 c[i]=j;
               d[j]=-1;  
             }
         }
     }
     i=0;
     m=0;
     while((m<k)&&i<n)
         {
         if(a[i]<b[i])
             {
            for(j=i+1;j<n;j++)
                {
                if(b[i]==a[j])
                    {
                    l=j;
                    j=n+5;
                }
            }
             p=a[l];
             a[l]=a[i];
             a[i]=p;
             m++;
             i++;
         }
         else
             {
             i++;
         }
     }
     for(i=0;i<n;i++)
         {
         printf("%d ",a[i]);
     }
}

Largest Permutation C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, k;
    int k2 = 0;
    cin >> n >> k;
    vector<int> a(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i < k && a[i] == n - i){
            //cout << "correct position" << endl;
            k++;
        }
    }
    
    for (int i = 0; i < n; i++){
        //cout << "value: " << a[i] << endl;
        while (a[i] > n - k && a[i] != n - i){
            //cout << "swapping " << a[i] << " with " << a[n-a[i]] << endl;
            swap(a[i], a[n - a[i]]);
            k += i < k && a[i] == n - i;
        }
        //cout << "element " << i << " is " << a[i] << endl;
    }
    
    for (auto x : a) cout << x << " ";
    cout << endl;
    
    return 0;
}

Largest Permutation C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {
    static void Main(String[] args) {
        string[] temp = Console.ReadLine().Split(' ');
        int N = Convert.ToInt32(temp[0]);
        int K = Convert.ToInt32(temp[1]);
        int[] input = new int[N];
        temp = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; ++i) {
            input[i] = Convert.ToInt32(temp[i]);
        }
        
        Process(input, K);
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; ++i) {
            sb.Append(input[i] + " ");
        }
        
        Console.WriteLine(sb.ToString());
    }
    
        static void Write(int[] input)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < input.Length; ++i)
            {
                sb.Append(input[i] + " ");
            }

            Console.WriteLine(sb.ToString());
        }

        static void Process(int[] input, int K)
        {
            int current = 0;
            for (int i = 0; i < input.Length; ++i)
            {
                for (int j = i + 1; j < input.Length; ++j)
                {
                    if (input[j] > input[i])
                    {
                        int maxIndex = j;
                        for (int k = j; k < input.Length; ++k)
                        {
                            if (input[k] > input[maxIndex])
                            {
                                maxIndex = k;
                            }
                        }

                        Exchange(input, i, maxIndex);
                        current++;
                        if (current == K)
                        {
                            return;
                        }
                    }
                }
            }
        }

        static void Exchange(int[] input, int i, int j)
        {
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
}

Largest Permutation Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'largestPermutation' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY arr
     */

    public static List<Integer> largestPermutation(int k, List<Integer> arr) {

        // **** initialization ****
        var n = arr.size();

        // **** sanity checks ****
        if (n == 1) return arr;
        if (k >= n) {
            Collections.sort(arr, Collections.reverseOrder());
            return arr;
        }

        // **** position of numbers in list ****
        int[] position = new int[n + 1];
        for (var i = 0; i < arr.size(); i++)
            position[arr.get(i)] = i;

        // **** ****
        for (int i = n, swaps = k; i > 0; --i) {

            // **** ****
            var actualPos = position[i];
      
            // **** ****
            var expectedPos = n - i;

            // **** check if i'th value is in the expected place ****
            if (actualPos != expectedPos) {

                // **** swap list elements ****
                Collections.swap(arr, actualPos, expectedPos);

                // **** update positions ****
                position[arr.get(actualPos)]    = actualPos;
                position[arr.get(expectedPos)]  = expectedPos;

                // **** check if we are done ****
                if (--swaps < 1) break;
            }
        }

        // **** return modified list ****
        return arr;

    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        List<Integer> result = Result.largestPermutation(k, arr);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining(" "))
            + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Largest Permutation JavaScript Solution

function processData(input) {
    var lines = input.split("\n");
    var params = lines[0].split(' ').map(Number);
    var n = params[0];
    var k = params[1];
    var arr = lines[1].trim().split(' ').map(Number);
    var pos = new Array(n + 1);
    var numSwaps = 0;
    var i, smaller, larger;
    
    for (i = 0; i < n; i++) {
        pos[arr[i]] = i;
    }
    
    for (i = 0; i < n; i++) {
        if (n - i > arr[i]) {
            smaller = arr[i];
            larger = n - i;
            swap(arr, i, pos[larger]);
            swap(pos, smaller, larger);
            numSwaps++;
            if (numSwaps === k) {
                break;
            }
        }
    }
    
    console.log(arr.join(' '));
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Largest Permutation Python Solution

n, k = input().split()
n = int(n)
k = int(k)
a = n * [0]
a = input().split()
a = [int(i) for i in a]
b = n * [0]

for i in range(0, n):
    b[a[i] - 1] = i

count = 0
j = 0
    
while count < k and j < n:
    if a[j] != n - j:
        a[j], a[b[n - j - 1]] = a[b[n - j - 1]], a[j]
        b[a[b[n - j - 1]] - 1], b[a[j] - 1] = b[a[j] - 1], b[a[b[n - j - 1]] - 1]
        count += 1
    j += 1
    
for i in range(0, n):
    print(a[i], end = " ")

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python