Maximum possible middle element of the array after deleting exactly k elements

0 0 6 minutes read

Given an integer array of size n and a number k. If the indexing is 1 based then the middle element of the array is the element at index (n + 1) / 2, if n is odd otherwise n / 2. The task is to delete exactly k elements from the array in such a way that the middle element of the reduced array is as maximum as possible. Find the maximum possible middle element of the array after deleting exactly k elements.
Examples:

Input :
n = 5, k = 2
arr[] = {9, 5, 3, 7, 10};
Output : 7

Input :
n = 9, k = 3
arr[] = {2, 4, 3, 9, 5, 8, 7, 6, 10};
Output : 9

In the first input, if we delete 5 and 3 then the array becomes {9, 7, 10} and
the middle element will be 7.
In the second input, if we delete one element before 9 and two elements after 9 
(for example 2, 5, 8) then the array becomes {4, 3, 9, 7, 6, 10} and middle 
element will be 9 and it will be the optimum solution.

Naive Approach :
The naive approach is to check all possible solutions. There could be C(n, k) possible solutions. If we check all possible solutions to find an optimal solution, it will consume a lot of time.
Optimal Approach :
After deleting k elements, the array will be reduced to size n – k. Since we can delete any k numbers from the array to find the maximum possible middle elements. If we note, the index of the middle element after deleting k elements will lie in the range ( n + 1 – k ) / 2 and ( n + 1 – k ) / 2 + k. So in order to find the optimal solution, simply iterate the array from the index ( n + 1 – k ) / 2 to index ( n + 1 – k ) / 2 + k and select the maximum element in this range.
The is the implementation is given below.

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate maximum possible middle 
// value of the array after deleting exactly k 
// elements
int maximum_middle_value(int n, int k, int arr[])
{
    // Initialize answer as -1
    int ans = -1;
 
    // Calculate range of elements that can give 
    // maximum possible middle value of the array
    // since index of maximum possible middle
    // value after deleting exactly k elements from 
    // array will lie in between low and high
    int low = (n + 1 - k) / 2;
 
    int high = (n + 1 - k) / 2 + k;
 
    // Find maximum element of the array in
    // range low and high
    for (int i = low; i <= high; i++) {
 
        // since indexing is 1 based so 
        // check element at index i - 1
        ans = max(ans, arr[i - 1]);
    }
 
    // Return the maximum possible middle value
    //  of the array after deleting exactly k
    // elements from the array
    return ans;
}
 
// Driver Code
int main()
{
    int n = 5, k = 2;
    int arr[] = { 9, 5, 3, 7, 10 };
    cout << maximum_middle_value(n, k, arr) << endl;
 
    n = 9;
    k = 3;
    int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 };
    cout << maximum_middle_value(n, k, arr1) << endl;
 
    return 0;
}

Java

// Java implementation of the approach 
import java.util.*;
 
class GFG
{
 
// Function to calculate maximum possible middle 
// value of the array after deleting exactly k 
// elements 
static int maximum_middle_value(int n, int k, int arr[]) 
{ 
    // Initialize answer as -1 
    int ans = -1; 
 
    // Calculate range of elements that can give 
    // maximum possible middle value of the array 
    // since index of maximum possible middle 
    // value after deleting exactly k elements from 
    // array will lie in between low and high 
    int low = (n + 1 - k) / 2; 
 
    int high = (n + 1 - k) / 2 + k; 
 
    // Find maximum element of the array in 
    // range low and high 
    for (int i = low; i <= high; i++) 
    { 
 
        // since indexing is 1 based so 
        // check element at index i - 1 
        ans = Math.max(ans, arr[i - 1]); 
    } 
 
    // Return the maximum possible middle value 
    // of the array after deleting exactly k 
    // elements from the array 
    return ans; 
} 
 
// Driver Code 
public static void main(String args[]) 
{ 
    int n = 5, k = 2; 
    int arr[] = { 9, 5, 3, 7, 10 }; 
    System.out.println( maximum_middle_value(n, k, arr)); 
 
    n = 9; 
    k = 3; 
    int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 }; 
    System.out.println( maximum_middle_value(n, k, arr1)); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
 
# Function to calculate maximum possible 
# middle value of the array after 
# deleting exactly k elements 
def maximum_middle_value(n, k, arr): 
  
    # Initialize answer as -1 
    ans = -1
 
    # Calculate range of elements that can give 
    # maximum possible middle value of the array 
    # since index of maximum possible middle 
    # value after deleting exactly k elements 
    # from array will lie in between low and high 
    low = (n + 1 - k) // 2
 
    high = (n + 1 - k) // 2 + k 
 
    # Find maximum element of the 
    # array in range low and high 
    for i in range(low, high+1):  
 
        # since indexing is 1 based so 
        # check element at index i - 1 
        ans = max(ans, arr[i - 1]) 
      
    # Return the maximum possible middle 
    # value of the array after deleting 
    # exactly k elements from the array 
    return ans 
  
# Driver Code 
if __name__ == "__main__": 
  
    n, k = 5, 2
    arr = [9, 5, 3, 7, 10] 
    print(maximum_middle_value(n, k, arr)) 
 
    n, k = 9, 3
    arr1 = [2, 4, 3, 9, 5, 8, 7, 6, 10]  
    print(maximum_middle_value(n, k, arr1)) 
 
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach 
using System;
 
class GFG
{
     
// Function to calculate maximum possible middle 
// value of the array after deleting exactly k 
// elements 
static int maximum_middle_value(int n, int k, int []arr) 
{ 
    // Initialize answer as -1 
    int ans = -1; 
 
    // Calculate range of elements that can give 
    // maximum possible middle value of the array 
    // since index of maximum possible middle 
    // value after deleting exactly k elements from 
    // array will lie in between low and high 
    int low = (n + 1 - k) / 2; 
 
    int high = (n + 1 - k) / 2 + k; 
 
    // Find maximum element of the array in 
    // range low and high 
    for (int i = low; i <= high; i++) 
    { 
 
        // since indexing is 1 based so 
        // check element at index i - 1 
        ans = Math.Max(ans, arr[i - 1]); 
    } 
 
    // Return the maximum possible middle value 
    // of the array after deleting exactly k 
    // elements from the array 
    return ans; 
} 
 
// Driver Code 
static public void Main ()
{
         
    int n = 5, k = 2; 
    int []arr = { 9, 5, 3, 7, 10 }; 
    Console.WriteLine( maximum_middle_value(n, k, arr)); 
 
    n = 9; 
    k = 3; 
    int []arr1 = { 2, 4, 3, 9, 5, 8, 7, 6, 10 }; 
    Console.WriteLine( maximum_middle_value(n, k, arr1)); 
} 
}
 
// This code is contributed by ajit.

Javascript

<script>
 
// Function to calculate maximum possible middle 
// value of the array after deleting exactly k 
// elements 
function maximum_middle_value(n, k, arr) 
{ 
    // Initialize answer as -1 
    let ans = -1; 
 
    // Calculate range of elements that can give 
    // maximum possible middle value of the array 
    // since index of maximum possible middle 
    // value after deleting exactly k elements from 
    // array will lie in between low and high 
    let low = Math.floor((n + 1 - k) / 2); 
 
    let high = Math.floor(((n + 1 - k) / 2) + k); 
 
    // Find maximum element of the array in 
    // range low and high 
    for (let i = low; i <= high; i++) { 
 
        // since indexing is 1 based so 
        // check element at index i - 1 
        ans = Math.max(ans, arr[i - 1]); 
    } 
 
    // Return the maximum possible middle value 
    // of the array after deleting exactly k 
    // elements from the array 
    return ans; 
} 
 
// Driver Code 
 
    let n = 5, k = 2; 
    let arr = [ 9, 5, 3, 7, 10 ]; 
    document.write(maximum_middle_value(n, k, arr) + "<br>"); 
 
    n = 9; 
    k = 3; 
    let arr1 = [ 2, 4, 3, 9, 5, 8, 7, 6, 10 ]; 
    document.write(maximum_middle_value(n, k, arr1) + "<br>"); 
 
 
// This code is contributed by Mayank Tyagi
 
</script>

Output:

7
9

Time Complexity: O(high-low), where high and low are the terms calculated
Auxiliary Space: O(1), as no extra space is used

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!