Select Page

# Maximize the minimum Array value by changing elements with adjacent K times

Kashish Kumar
Published: September 8, 2022

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: 7

Input: 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 Kth 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:  5

When 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 = 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 Kth index of arr[].
• Print the output.

Below is the implementation for the above approach:

## Java

 ` ` `import` `java.util.*;`` ` `class` `GFG {`` ` `    ``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `N = ``6``, X = ``3``;``        ``int``[] arr = { ``9``, ``7``, ``3``, ``1``, ``2``, ``5` `};`` ` `        ``        ``System.out.println(Min_Value(N, X, arr));``    ``}`` ` `    ``    ``static` `int` `Min_Value(``int` `N, ``int` `X, ``int` `arr[])``    ``{``        ``        ``        ``Arrays.sort(arr);`` ` `        ``        ``        ``        ``        ``if` `(X == arr.length || X > arr.length)``            ``return` `(arr[arr.length - ``1``]);`` ` `        ``        ``        ``        ``else``            ``return` `(arr[X]);``    ``}``}`

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

Source: www.geeksforgeeks.org