Find position of the leader element in given Array with given operations
Given an array arr[]. The task is to find the position of the leader element in arr[]. The leader element is the one, which can remove all other elements in the array using the below operations.
- If arr[i] > arr[i + 1], It removes the (i+1)th element and increment their value by 1 and decrease the size of array by 1.
- If arr[i] > arr[i – 1], It removes the (i-1)th element and increment their value by 1 and decrease the size of array by 1.
Examples
Input: arr[] = { 5, 3, 4, 4, 5 }
Output: 3
Explanation: Following are the operations performed in array arr[]
A3 remove A2 and increment by 1 and array becomes { 5, 5, 4, 5 }
A2 remove A3 and increment by 1 and array becomes { 5, 6, 5 }
A2 remove A1 and increment by 1 and array becomes { 7, 5 }
A1 remove A2 and increment by 1 and array becomes { 8 }
Hence, The position of leader of array is 3.Input: arr[] = { 4, 4, 3, 4, 4 }
Output: 2
Explanation: Following are the operations performed in array arr[]
A2 remove A3 and increment by 1 and array becomes { 4, 5, 4, 4 }
A2 remove A1 and increment by 1 and array becomes { 6, 4, 4 }
A1 remove A2 and increment by 1 and array becomes { 7, 4 }
A1 remove A2 and increment by 1 and array becomes { 8 }
Hence, The position of leader of array is 2.Input: arr[] = { 1, 1, 1 }
Output: -1
Explanation: No leader is present in the array
Approach: This problem is implementation-based. Follow the steps below to solve the given problem.
- Find the maximum and minimum elements of the array arr.
- If the minimum and maximum elements are the same that means no leader element is present.
- Traverse the array.
- Now, check if arr[i] is max element.
- Check arr[i-1] or arr[i+1] is smaller than max .
- So, that element is the leader element in the array.
- Print the position of the leader element found.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find the leader element in array int LeaderElement( int arr[], int n) { // Initialize two variable int maxElement = INT_MIN, minElement = INT_MAX; // Traverse the array for ( int i = 0; i < n; i++) { maxElement = max(maxElement, arr[i]); minElement = min(minElement, arr[i]); } // Now if both are equal return -1 if (maxElement == minElement) { return -1; } // Now traverse the array and // check if adjacent element // of max element because // maxelement of array always // leader But if more than 1 // leader element so, check // the adjacent elements of that int ans = -1; for ( int i = 0; i < n; i++) { if (arr[i] == maxElement) { if (i > 0 and arr[i] > arr[i - 1]) { ans = i + 1; break ; } if (i < n - 1 and arr[i] > arr[i + 1]) { ans = i + 1; break ; } } } return ans; } // Driver Code int main() { int arr[] = { 4, 4, 3, 4, 4 }; int N = 5; // Function Call int ans = LeaderElement(arr, N); cout << ans; return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the leader element in array static int LeaderElement( int arr[], int n) { // Initialize two variable int maxElement = Integer.MIN_VALUE; int minElement = Integer.MAX_VALUE; // Traverse the array for ( int i = 0 ; i < n; i++) { maxElement = Math.max(maxElement, arr[i]); minElement = Math.min(minElement, arr[i]); } // Now if both are equal return -1 if (maxElement == minElement) { return - 1 ; } // Now traverse the array and // check if adjacent element // of max element because // maxelement of array always // leader But if more than 1 // leader element so, check // the adjacent elements of that int ans = - 1 ; for ( int i = 0 ; i < n; i++) { if (arr[i] == maxElement) { if (i > 0 && arr[i] > arr[i - 1 ]) { ans = i + 1 ; break ; } if (i < n - 1 && arr[i] > arr[i + 1 ]) { ans = i + 1 ; break ; } } } return ans; } public static void main (String[] args) { int arr[] = { 4 , 4 , 3 , 4 , 4 }; int N = 5 ; // Function Call int ans = LeaderElement(arr, N); System.out.print(ans); } } // This code is contributed by hrithikgarg03188 |
Python
# Python3 program for the above approach # import the module import sys # Function to find the leader element in array def LeaderElement(arr, n): # Initialize two variable maxElement = - sys.maxsize - 1 minElement = sys.maxint # Traverse the array for i in range (n): maxElement = max (maxElement, arr[i]) minElement = min (minElement, arr[i]) # Now if both are equal return -1 if (maxElement = = minElement): return - 1 # Now traverse the array and # check if adjacent element # of max element because # maxelement of array always # leader But if more than 1 # leader element so, check # the adjacent elements of that ans = - 1 for i in range (n): if (arr[i] = = maxElement): if (i > 0 and arr[i] > arr[i - 1 ]): ans = i + 1 break if (i < n - 1 and arr[i] > arr[i + 1 ]): ans = i + 1 break return ans # Driver Code # Given Input arr = [ 4 , 4 , 3 , 4 , 4 ] N = len (arr) # Function Call ans = LeaderElement(arr, N) print (ans) # This code is contributed by hrithikgarg03188. |
C#
// C# program for the above approach using System; class GFG { // Function to find the leader element in array static int LeaderElement( int []arr, int n) { // Initialize two variable int maxElement = Int32.MinValue; int minElement = Int32.MaxValue; // Traverse the array for ( int i = 0; i < n; i++) { maxElement = Math.Max(maxElement, arr[i]); minElement = Math.Min(minElement, arr[i]); } // Now if both are equal return -1 if (maxElement == minElement) { return -1; } // Now traverse the array and // check if adjacent element // of max element because // maxelement of array always // leader But if more than 1 // leader element so, check // the adjacent elements of that int ans = -1; for ( int i = 0; i < n; i++) { if (arr[i] == maxElement) { if (i > 0 && arr[i] > arr[i - 1]) { ans = i + 1; break ; } if (i < n - 1 && arr[i] > arr[i + 1]) { ans = i + 1; break ; } } } return ans; } public static void Main () { int []arr = { 4, 4, 3, 4, 4 }; int N = 5; // Function Call int ans = LeaderElement(arr, N); Console.Write(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for above approach // Function to find the leader element in array function LeaderElement(arr, n) { // Initialize two variable let maxElement = Number.MIN_SAFE_INTEGER, minElement = Number.MIN_SAFE_INTEGER; // Traverse the array for (let i = 0; i < n; i++) { maxElement = Math.max(maxElement, arr[i]); minElement = Math.min(minElement, arr[i]); } // Now if both are equal return -1 if (maxElement == minElement) { return -1; } // Now traverse the array and // check if adjacent element // of max element because // maxelement of array always // leader But if more than 1 // leader element so, check // the adjacent elements of that let ans = -1; for (let i = 0; i < n; i++) { if (arr[i] == maxElement) { if (i > 0 && arr[i] > arr[i - 1]) { ans = i + 1; break ; } if (i < n - 1 && arr[i] > arr[i + 1]) { ans = i + 1; break ; } } } return ans; } // Driver Code let arr = [4, 4, 3, 4, 4]; let N = 5; // Function Call let ans = LeaderElement(arr, N); document.write(ans) // This code is contributed by gfgking. </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)