Given an array arr[] of size N, and an integer K, the task is to maximize the first element of the array in K operations where in each operation:
- If the array is not empty, remove the topmost element of the array.
- Add any one of the previously removed element back at the starting of the array.
Examples:
Input: arr[] = [5, 2, 2, 4, 0, 6], K = 4
Output: 5
Explanation: The 4 operations are as:
- Remove the topmost element = 5. The arr becomes [2, 2, 4, 0, 6].
- Remove the topmost element = 2. The arr becomes [2, 4, 0, 6].
- Remove the topmost element = 2. The arr becomes [4, 0, 6].
- Add 5 back onto the arr. The arr becomes [5, 4, 0, 6].
Here 5 is the largest answer possible after 4 moves.
Input: arr[] = [2], K = 1
Output: -1
Explanation: Only one move can be applied and in the first move.
The only option is to remove the first element of the arr[].
If that is done the array becomes empty. So answer is -1
Approach: This problem can be solved with the help of the Greedy approach based on the following idea:
In first K-1 operations, the K-1 value of the starting can be removed. So currently at Kth node. Now in the last operation there are two possible choice:
- Either remove the current starting node (optimal if the value of the (K+1)th node is greater than the largest amongst first K-1 already removed elements)
- Add the largest from the already removed K-1 elements (optimal when the (K+1)th node has less value than this largest one)
Follow the illustration shown below for a better understanding.
Illustration:
For example arr[] = {5, 2, 2, 4, 0, 6}, K = 4
1st Operation:
=> Remove 5. arr[] = {2, 2, 4, 0, 6}
=> maximum = 5, K = 4 – 1 = 32nd Operation:
=> Remove 2. arr[] = {2, 4, 0, 6}
=> maximum = max (5, 2) = 5, K = 3 – 1 = 23rd Operation:
=> Remove 2. arr[] = {4, 0, 6}
=> maximum = max (5, 2) = 5, K = 2 – 1 = 14th Operation:
=> Here the current 2nd element i.e. 0 is less than 5.
=> So add 5 back in the array. arr[] = {5, 4, 0, 6}
=> maximum = max (5, 0) = 5, K = 1 – 1 = 0Therefore the maximum possible first element is 5.
Follow the steps to solve the problem:
- If K = 0, then return first node value.
- If K = 1, then return the second node value(if any) else return -1 (because after K operations the list does not exist).
- If the size of the linked list is one then in every odd operation (i.e. 1, 3, 5, . . . ), return -1, else return the first node value (because if performed odd operation then array will become empty).
- If K > 2, then:
- Traverse first K-1 nodes and find out the maximum value.
- Compare that maximum value with the (K+1)th node value.
- If (K+1)th value is greater than the previous maximum value, update it with (K+1)th Node value. Otherwise, don’t update the maximum value.
- Return the maximum value.
Below is the implementation of the above approach :
C++
// C++ code to implement the approach#include <iostream>using namespace std;int maximumTopMost(int arr[], int k,int N){ // Checking if k is odd and // length of array is 1 if (N == 1 and k % 2 != 0) return -1; // Initializing ans with -1 int ans = -1; // If k is greater or equal to the // length of array for(int i = 0; i < min(N, k - 1); i++) ans = max(ans, arr[i]); // If k is less than length of array if (k < N) ans = max(ans, arr[k]); // Returning ans return ans;}// Driver codeint main() { int arr[] = {5, 2, 2, 4, 0, 6}; int N = 6; int K = 4; cout <<(maximumTopMost(arr, K, N)); return 0;}// This code is contributed by hrithikgarg03188. |
Java
// Java code to implement the approachclass GFG { static int maximumTopMost(int[] arr, int k, int N) { // Checking if k is odd and // length of array is 1 if (N == 1 && k % 2 != 0) return -1; // Initializing ans with -1 int ans = -1; // If k is greater or equal to the // length of array for (int i = 0; i < Math.min(N, k - 1); i++) ans = Math.max(ans, arr[i]); // If k is less than length of array if (k < N) ans = Math.max(ans, arr[k]); // Returning ans return ans; } public static void main(String[] args) { int[] arr = { 5, 2, 2, 4, 0, 6 }; int N = 6; int K = 4; System.out.println(maximumTopMost(arr, K, N)); }}// This code is contributed by phasing17. |
Python3
# Python code to implement the approachdef maximumTopMost(arr, k): # Checking if k is odd and # length of array is 1 if len(arr) == 1 and k % 2 != 0: return -1 # Initializing ans with -1 ans = -1 # If k is greater or equal to the # length of array for i in range(min(len(arr), k - 1)): ans = max(ans, arr[i]) # If k is less than length of array if k < len(arr): ans = max(ans, arr[k]) # Returning ans return ans# Driver codeif __name__ == "__main__": arr = [5, 2, 2, 4, 0, 6] K = 4 print(maximumTopMost(arr, K)) |
C#
// C# code to implement the approachusing System;class GFG { static int maximumTopMost(int[] arr, int k, int N) { // Checking if k is odd and // length of array is 1 if (N == 1 && k % 2 != 0) return -1; // Initializing ans with -1 int ans = -1; // If k is greater or equal to the // length of array for (int i = 0; i < Math.Min(N, k - 1); i++) ans = Math.Max(ans, arr[i]); // If k is less than length of array if (k < N) ans = Math.Max(ans, arr[k]); // Returning ans return ans; } // Driver code public static void Main() { int[] arr = { 5, 2, 2, 4, 0, 6 }; int N = 6; int K = 4; Console.Write(maximumTopMost(arr, K, N)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the approach const maximumTopMost = (arr, k) => { // Checking if k is odd and // length of array is 1 if (arr.length == 1 && k % 2 != 0) return -1; // Initializing ans with -1 let ans = -1; // If k is greater or equal to the // length of array for (let i = 0; i < Math.min(arr.length, k - 1); ++i) ans = Math.max(ans, arr[i]); // If k is less than length of array if (k < arr.length) ans = Math.max(ans, arr[k]); // Returning ans return ans; } // Driver code let arr = [5, 2, 2, 4, 0, 6]; let K = 4; document.write(maximumTopMost(arr, K));// This code is contributed by rakeshsahni</script> |
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
