Maximize the minimum Array value by changing elements with adjacent K times
Given an array arr[] of N integers and an integer K, where K denotes the maximum number of operations which can be applied to the array, the task is to maximize the minimum value of arr[] by using the given operation at most K times.
 In one operation it is possible to select any element of arr[] in one operation and can change it with its adjacent element.
Examples:
Input: N = 7, K = 4, arr[] = {9, 7, 3, 5, 7, 8, 7}
Output: 7
Explanation: First operation: Change 3 at index 2 with 7 at index 1.
So the arr[] becomes: {9, 7, 7, 5, 7, 8, 7}
Second Operation: Change 5 at index 3 with 7 at index 2.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 7}
Third operation: Change 7 at index 6 with 8 at index 5.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 8}
Fourth Operation: Change 7 at index 1 with 9 at index 0.
So the arr[] becomes: {9, 9, 7, 7, 7, 8, 8}
The minimum value in arr[] after applying operation at most K times is: 7Input: N = 4, K = 2, arr[] = {2, 5, 6, 8}
Output: 6
Explanation: First operation: Change 5 at index 1 with 6 at index 2.
So that the arr[] becomes: {2, 6, 6, 8}
Second operation: Change 2 at index 0 with 6 at index 1.
So that the arr[] becomes: {6, 6, 6, 8}
The minimum value of arr[] can be achieved by applying operations is: 6
Approach: To solve the problem follow the below idea:
Sort the arr[], if K is greater than or equal to length of arr[], simply return element at last index of arr[] else return element at K_{th} index of arr[].
Illustration with an Example:
Consider N = 6, K = 3, arr[] = {9, 7, 3, 1, 2, 5}
We can perform the following operations
Operation 1: Change 2 at index 4 with 5 at index 5 . So the arr[] becomes: {9, 7, 3, 1, 5, 5}
Operation 2: Change 1 at index 3 with 5 at index 4 . So the arr[] becomes: {9, 7, 3, 5, 5, 5}
Operation 3: Change 3 at index 2 with 7 at index 1 . So the arr[] becomes: {9, 7, 7, 5, 5, 5}
Minimum element after applying operation at most 3 times is: 5When you will sort the arr[] and return arr[K] you will get the same output :
Sorted arr[]: {1, 2, 3, 5, 7, 9}
arr[K] = arr[3] = 5, which is out required answer.
Follow the steps to solve the problem:
 Sort the array.
 Check if K is greater than or equal to arr[] or not.
 If yes, then simply return the element at the last index of arr[].
 Else return the element at the K^{th} index of arr[].
 Print the output.
Below is the implementation for the above approach:
Java

Time Complexity: O(N * logN), because sorting is performed.
Auxiliary Space: O(1), as no extra space is required.
Kashish Kumar
Source link