Leftmost and rightmost indices of the maximum and the minimum element of an array
Given an array arr[], the task is to find the leftmost and the rightmost indices of the minimum and the maximum element from the array where arr[] consists of non-distinct elements.
Examples:
Input: arr[] = {2, 1, 1, 2, 1, 5, 6, 5}
Output: Minimum left : 1
Minimum right : 4
Maximum left : 6
Maximum right : 6
Minimum element is 1 which is present at indices 1, 2 and 4.
Maximum element is 6 which is present only at index 6.
Input: arr[] = {0, 1, 0, 2, 7, 5, 6, 7}
Output: Minimum left : 0
Minimum right : 2
Maximum left : 4
Maximum right : 7
Method 1: When the array is unsorted.
- Initialize the variable leftMin = rightMin = leftMax = rightMax = arr[0] and min = max = arr[0].
- Start traversing the array from 1 to n – 1.
- If arr[i] < min then a new minimum is found. Update leftMin = rightMin = i.
- Else arr[i] = min then another copy of the current minimum is found. Update the rightMin = i.
- If arr[i] > max then a new maximum is found. Update leftMax = rightMax = i.
- Else arr[i] = max then another copy of the current maximum is found. Update the rightMax = i.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; void findIndices( int arr[], int n) { int leftMin = 0, rightMin = 0; int leftMax = 0, rightMax = 0; int min = arr[0], max = arr[0]; for ( int i = 1; i < n; i++) { // If found new minimum if (arr[i] < min) { leftMin = rightMin = i; min = arr[i]; } // If arr[i] = min then rightmost index // for min will change else if (arr[i] == min) rightMin = i; // If found new maximum if (arr[i] > max) { leftMax = rightMax = i; max = arr[i]; } // If arr[i] = max then rightmost index // for max will change else if (arr[i] == max) rightMax = i; } cout << "Minimum left : " << leftMin << "\n" ; cout << "Minimum right : " << rightMin << "\n" ; cout << "Maximum left : " << leftMax << "\n" ; cout << "Maximum right : " << rightMax << "\n" ; } // Driver code int main() { int arr[] = { 2, 1, 1, 2, 1, 5, 6, 5 }; int n = sizeof (arr)/ sizeof (arr[0]); findIndices(arr, n); } // This code is contributed // by ihritik |
Java
// Java implementation of the approach public class GFG { public static void findIndices( int arr[], int n) { int leftMin = 0 , rightMin = 0 ; int leftMax = 0 , rightMax = 0 ; int min = arr[ 0 ], max = arr[ 0 ]; for ( int i = 1 ; i < n; i++) { // If found new minimum if (arr[i] < min) { leftMin = rightMin = i; min = arr[i]; } // If arr[i] = min then rightmost index // for min will change else if (arr[i] == min) rightMin = i; // If found new maximum if (arr[i] > max) { leftMax = rightMax = i; max = arr[i]; } // If arr[i] = max then rightmost index // for max will change else if (arr[i] == max) rightMax = i; } System.out.println( "Minimum left : " + leftMin); System.out.println( "Minimum right : " + rightMin); System.out.println( "Maximum left : " + leftMax); System.out.println( "Maximum right : " + rightMax); } // Driver code public static void main(String[] args) { int arr[] = { 2 , 1 , 1 , 2 , 1 , 5 , 6 , 5 }; int n = arr.length; findIndices(arr, n); } } |
Python3
# Python3 implementation of the approach def findIndices(arr, n) : leftMin, rightMin = 0 , 0 leftMax, rightMax = 0 , 0 min_element = arr[ 0 ] max_element = arr[ 0 ] for i in range (n) : # If found new minimum if (arr[i] < min_element) : leftMin = rightMin = i min_element = arr[i] # If arr[i] = min then rightmost # index for min will change elif (arr[i] = = min_element) : rightMin = i # If found new maximum if (arr[i] > max_element) : leftMax = rightMax = i max_element = arr[i] # If arr[i] = max then rightmost # index for max will change elif (arr[i] = = max_element) : rightMax = i print ( "Minimum left : " , leftMin) print ( "Minimum right : " , rightMin) print ( "Maximum left : " , leftMax ) print ( "Maximum right : " , rightMax) # Driver code if __name__ = = "__main__" : arr = [ 2 , 1 , 1 , 2 , 1 , 5 , 6 , 5 ] n = len (arr) findIndices(arr, n) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; class GFG { static void findIndices( int []arr, int n) { int leftMin = 0, rightMin = 0; int leftMax = 0, rightMax = 0; int min = arr[0], max = arr[0]; for ( int i = 1; i < n; i++) { // If found new minimum if (arr[i] < min) { leftMin = rightMin = i; min = arr[i]; } // If arr[i] = min then rightmost index // for min will change else if (arr[i] == min) rightMin = i; // If found new maximum if (arr[i] > max) { leftMax = rightMax = i; max = arr[i]; } // If arr[i] = max then rightmost index // for max will change else if (arr[i] == max) rightMax = i; } Console.WriteLine( "Minimum left : " + leftMin); Console.WriteLine( "Minimum right : " + rightMin); Console.WriteLine( "Maximum left : " + leftMax); Console.WriteLine( "Maximum right : " + rightMax); } // Driver code public static void Main() { int []arr = { 2, 1, 1, 2, 1, 5, 6, 5 }; int n = arr.Length; findIndices(arr, n); } } // This code is contributed // By ihritik |
PHP
<?php // PHP implementation of the approach function findIndices( $arr , $n ) { $leftMin = 0; $rightMin = 0; $leftMax = 0; $rightMax = 0; $min = $arr [0]; $max = $arr [0]; for ( $i = 1; $i < $n ; $i ++) { // If found new minimum if ( $arr [ $i ] < $min ) { $leftMin = $rightMin = $i ; $min = $arr [ $i ]; } // If arr[i] = min then rightmost // index for min will change else if ( $arr [ $i ] == $min ) $rightMin = $i ; // If found new maximum if ( $arr [ $i ] > $max ) { $leftMax = $rightMax = $i ; $max = $arr [ $i ]; } // If arr[i] = max then rightmost // index for max will change else if ( $arr [ $i ] == $max ) $rightMax = $i ; } echo "Minimum left : " , $leftMin , "\n" ; echo "Minimum right : " , $rightMin , "\n" ; echo "Maximum left : " , $leftMax , "\n" ; echo "Maximum right : " , $rightMax , "\n" ; } // Driver code $arr = array ( 2, 1, 1, 2, 1, 5, 6, 5 ); $n = sizeof( $arr ); findIndices( $arr , $n ); // This code is contributed // by Sachin ?> |
Javascript
<script> // Javascript implementation of the approach function findIndices(arr,n) { let leftMin = 0, rightMin = 0; let leftMax = 0, rightMax = 0; let min = arr[0], max = arr[0]; for (let i = 1; i < n; i++) { // If found new minimum if (arr[i] < min) { leftMin = rightMin = i; min = arr[i]; } // If arr[i] = min then rightmost index // for min will change else if (arr[i] == min) rightMin = i; // If found new maximum if (arr[i] > max) { leftMax = rightMax = i; max = arr[i]; } // If arr[i] = max then rightmost index // for max will change else if (arr[i] == max) rightMax = i; } document.write( "Minimum left : " + leftMin+ "<br>" ); document.write( "Minimum right : " + rightMin+ "<br>" ); document.write( "Maximum left : " + leftMax+ "<br>" ); document.write( "Maximum right : " + rightMax+ "<br>" ); } // Driver code let arr=[2, 1, 1, 2, 1, 5, 6, 5 ]; let n = arr.length; findIndices(arr, n); // This code is contributed by unknown2108 </script> |
Minimum left : 1 Minimum right : 4 Maximum left : 6 Maximum right : 6
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 2: When the array is sorted.
- When the array is sorted then leftMin = 0 and rightMax = n – 1.
- In order to find the rightMin, apply a modified binary search:
- Set i = 1.
- While arr[i] = min update rightMin = i and i = i * 2.
- Finally do a linear search for the rest of the elements from rightMin + 1 to n – 1 while arr[i] = min.
- Return rightMin in the end.
- Similarly, for leftMax repeat the above steps but in reverse i.e. from n – 1 and update i = i / 2 after every iteration.
Below is the implementation of the above approach:
C++
// C++ implementation of above idea #include<bits/stdc++.h> using namespace std; // Function to return the index of the rightmost // minimum element from the array int getRightMin( int arr[], int n) { // First element is the minimum in a sorted array int min = arr[0]; int rightMin = 0; int i = 1; while (i < n) { // While the elements are equal to the minimum // update rightMin if (arr[i] == min) rightMin = i; i *= 2; } i = rightMin + 1; // Final check whether there are any elements // which are equal to the minimum while (i < n && arr[i] == min) { rightMin = i; i++; } return rightMin; } // Function to return the index of the leftmost // maximum element from the array int getLeftMax( int arr[], int n) { // Last element is the maximum in a sorted array int max = arr[n - 1]; int leftMax = n - 1; int i = n - 2; while (i > 0) { // While the elements are equal to the maximum // update leftMax if (arr[i] == max) leftMax = i; i /= 2; } i = leftMax - 1; // Final check whether there are any elements // which are equal to the maximum while (i >= 0 && arr[i] == max) { leftMax = i; i--; } return leftMax; } // Driver code int main() { int arr[] = { 0, 0, 1, 2, 5, 5, 6, 8, 8 }; int n = sizeof (arr)/ sizeof (arr[0]); // First element is the leftmost minimum in a sorted array cout << "Minimum left : " << 0 << "\n" ; cout << "Minimum right : " << getRightMin(arr, n) << "\n" ; cout << "Maximum left : " << getLeftMax(arr, n) << "\n" ; // Last element is the rightmost maximum in a sorted array cout << "Maximum right : " << (n - 1); } // This code is contributed by ihritik |
Java
// Java implementation of above idea public class GFG { // Function to return the index of the rightmost // minimum element from the array public static int getRightMin( int arr[], int n) { // First element is the minimum in a sorted array int min = arr[ 0 ]; int rightMin = 0 ; int i = 1 ; while (i < n) { // While the elements are equal to the minimum // update rightMin if (arr[i] == min) rightMin = i; i *= 2 ; } i = rightMin + 1 ; // Final check whether there are any elements // which are equal to the minimum while (i < n && arr[i] == min) { rightMin = i; i++; } return rightMin; } // Function to return the index of the leftmost // maximum element from the array public static int getLeftMax( int arr[], int n) { // Last element is the maximum in a sorted array int max = arr[n - 1 ]; int leftMax = n - 1 ; int i = n - 2 ; while (i > 0 ) { // While the elements are equal to the maximum // update leftMax if (arr[i] == max) leftMax = i; i /= 2 ; } i = leftMax - 1 ; // Final check whether there are any elements // which are equal to the maximum while (i >= 0 && arr[i] == max) { leftMax = i; i--; } return leftMax; } // Driver code public static void main(String[] args) { int arr[] = { 0 , 0 , 1 , 2 , 5 , 5 , 6 , 8 , 8 }; int n = arr.length; // First element is the leftmost minimum in a sorted array System.out.println( "Minimum left : " + 0 ); System.out.println( "Minimum right : " + getRightMin(arr, n)); System.out.println( "Maximum left : " + getLeftMax(arr, n)); // Last element is the rightmost maximum in a sorted array System.out.println( "Maximum right : " + (n - 1 )); } } |
Python3
# Python 3 implementation of above idea # Function to return the index of the # rightmost minimum element from the array def getRightMin(arr, n): # First element is the minimum # in a sorted array min = arr[ 0 ] rightMin = 0 i = 1 while (i < n): # While the elements are equal to # the minimum update rightMin if (arr[i] = = min ): rightMin = i i * = 2 i = rightMin + 1 # Final check whether there are any # elements which are equal to the minimum while (i < n and arr[i] = = min ): rightMin = i i + = 1 return rightMin # Function to return the index of the # leftmost maximum element from the array def getLeftMax(arr, n): # Last element is the maximum # in a sorted array max = arr[n - 1 ] leftMax = n - 1 i = n - 2 while (i > 0 ): # While the elements are equal to # the maximum update leftMax if (arr[i] = = max ): leftMax = i i = int (i / 2 ) i = leftMax - 1 # Final check whether there are any # elements which are equal to the maximum while (i > = 0 and arr[i] = = max ): leftMax = i i - = 1 return leftMax # Driver code if __name__ = = '__main__' : arr = [ 0 , 0 , 1 , 2 , 5 , 5 , 6 , 8 , 8 ] n = len (arr) # First element is the leftmost # minimum in a sorted array print ( "Minimum left :" , 0 ) print ( "Minimum right :" , getRightMin(arr, n)) print ( "Maximum left :" , getLeftMax(arr, n)) # Last element is the rightmost maximum # in a sorted array print ( "Maximum right :" , (n - 1 )) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of above idea using System; public class GFG { // Function to return the index of the rightmost // minimum element from the array public static int getRightMin( int []arr, int n) { // First element is the minimum in a sorted array int min = arr[0]; int rightMin = 0; int i = 1; while (i < n) { // While the elements are equal to the minimum // update rightMin if (arr[i] == min) rightMin = i; i *= 2; } i = rightMin + 1; // Final check whether there are any elements // which are equal to the minimum while (i < n && arr[i] == min) { rightMin = i; i++; } return rightMin; } // Function to return the index of the leftmost // maximum element from the array public static int getLeftMax( int []arr, int n) { // Last element is the maximum in a sorted array int max = arr[n - 1]; int leftMax = n - 1; int i = n - 2; while (i > 0) { // While the elements are equal to the maximum // update leftMax if (arr[i] == max) leftMax = i; i /= 2; } i = leftMax - 1; // Final check whether there are any elements // which are equal to the maximum while (i >= 0 && arr[i] == max) { leftMax = i; i--; } return leftMax; } // Driver code public static void Main() { int []arr = { 0, 0, 1, 2, 5, 5, 6, 8, 8 }; int n = arr.Length; // First element is the leftmost minimum in a sorted array Console.WriteLine( "Minimum left : " + 0); Console.WriteLine( "Minimum right : " + getRightMin(arr, n)); Console.WriteLine( "Maximum left : " + getLeftMax(arr, n)); // Last element is the rightmost maximum in a sorted array Console.WriteLine( "Maximum right : " + (n - 1)); } } // This code is contributed by ihritik |
PHP
<?php // PHP implementation of above idea // Function to return the index of the // rightmost minimum element from the array function getRightMin( $arr , $n ) { // First element is the minimum // in a sorted array $min = $arr [0]; $rightMin = 0; $i = 1; while ( $i < $n ) { // While the elements are equal to // the minimum update rightMin if ( $arr [ $i ] == $min ) $rightMin = $i ; $i *= 2; } $i = $rightMin + 1; // Final check whether there are any // elements which are equal to the minimum while ( $i < $n && $arr [ $i ] == $min ) { $rightMin = $i ; $i ++; } return $rightMin ; } // Function to return the index of the // leftmost maximum element from the array function getLeftMax( $arr , $n ) { // Last element is the maximum in // a sorted array $max = $arr [ $n - 1]; $leftMax = $n - 1; $i = $n - 2; while ( $i > 0) { // While the elements are equal to // the maximum update leftMax if ( $arr [ $i ] == $max ) $leftMax = $i ; $i /= 2; } $i = $leftMax - 1; // Final check whether there are any // elements which are equal to the maximum while ( $i >= 0 && $arr [ $i ] == $max ) { $leftMax = $i ; $i --; } return $leftMax ; } // Driver code $arr = array (0, 0, 1, 2, 5, 5, 6, 8, 8 ); $n = sizeof( $arr ); // First element is the leftmost // minimum in a sorted array echo "Minimum left : " , 0, "\n" ; echo "Minimum right : " , getRightMin( $arr , $n ), "\n" ; echo "Maximum left : " , getLeftMax( $arr , $n ), "\n" ; // Last element is the rightmost // maximum in a sorted array echo "Maximum right : " , ( $n - 1), "\n" ; // This code is Contributed // by Mukul singh ?> |
Javascript
<script> // Javascript implementation of above idea // Function to return the index of the rightmost // minimum element from the array function getRightMin(arr, n) { // First element is the minimum in a sorted array let min = arr[0]; let rightMin = 0; let i = 1; while (i < n) { // While the elements are equal to the minimum // update rightMin if (arr[i] == min) rightMin = i; i *= 2; } i = rightMin + 1; // Final check whether there are any elements // which are equal to the minimum while (i < n && arr[i] == min) { rightMin = i; i++; } return rightMin; } // Function to return the index of the leftmost // maximum element from the array function getLeftMax(arr, n) { // Last element is the maximum in a sorted array let max = arr[n - 1]; let leftMax = n - 1; let i = n - 2; while (i > 0) { // While the elements are equal to the maximum // update leftMax if (arr[i] == max) leftMax = i; i = parseInt(i / 2, 10); } i = leftMax - 1; // Final check whether there are any elements // which are equal to the maximum while (i >= 0 && arr[i] == max) { leftMax = i; i--; } return leftMax; } let arr = [ 0, 0, 1, 2, 5, 5, 6, 8, 8 ]; let n = arr.length; // First element is the leftmost minimum in a sorted array document.write( "Minimum left : " + 0 + "</br>" ); document.write( "Minimum right : " + getRightMin(arr, n) + "</br>" ); document.write( "Maximum left : " + getLeftMax(arr, n) + "</br>" ); // Last element is the rightmost maximum in a sorted array document.write( "Maximum right : " + (n - 1)); // This code is contributed by suresh07. </script> |
Minimum left : 0 Minimum right : 1 Maximum left : 7 Maximum right : 8
Time Complexity: O(n) As linear search is applied for a set of elements so the worst case time complexity will be O(n).
Auxiliary Space: O(1)