Replace every element with the greatest element on its left side
Given an array of integers, the task is to replace every element with the greatest element on its left side.
Note: Replace the first element with -1 as it has no element in its left.
Examples:
Input: arr[] = {4, 5, 2, 1, 7, 6}
Output: -1 4 5 5 5 7
Explanation:
Since, 4 has no element in its left, so replace it by -1.
For 5, 4 is the greatest element in its left.
For 2, 5 is the greatest element in its left.
For 1, 5 is the greatest element in its left.
For 7, 5 is the greatest element in its left.
For 6, 7 is the greatest element in its left.Input: arr[] = {3, 2, 5, 7, 1}
Output: -1 3 3 5 7
Approach:
- Maintain a variable max_ele which will store the greatest element.
- Initially, max_ele will be equal to the element at the 0th index.
- First replace arr[0] with -1 then traverse the array
- And then replace the element with the max_ele value and update the max_ele if the element is greater than max_ele.
- Print the modified array.
Below is the implementation of the above approach:
C++
// C++ program to Replace every // element with the greater element // on its left side #include <bits/stdc++.h> using namespace std; // Function to replace the elements void ReplaceElements( int arr[], int n) { // Max value initialised // to element at 0th index int max_ele = arr[0]; arr[0] = -1; for ( int i = 1; i < n; ++i) { // If max_ele is greater than arr[i] // then just replace arr[i] with max_ele if (max_ele > arr[i]) arr[i] = max_ele; // Else if update the max_ele also else if (max_ele <= arr[i]) { int temp = arr[i]; arr[i] = max_ele; max_ele = temp; } } } // Driver code int main() { int arr[] = { 4, 5, 2, 1, 7, 6 }; int n = sizeof (arr) / sizeof (arr[0]); // Replace the elements // with the smaller element // on its left side ReplaceElements(arr, n); // Print the modified array for ( int i = 0; i < n; ++i) cout << arr[i] << " " ; return 0; } |
Java
// Java program to Replace every // element with the greater element // on its left side import java.util.*; class Beginner { // Function to replace the elements static void ReplaceElements( int arr[], int n) { // Max value initialised // to element at 0th index int max_ele = arr[ 0 ]; arr[ 0 ] = - 1 ; for ( int i = 1 ; i < n; ++i) { // If max_ele is greater than arr[i] // then just replace arr[i] with max_ele if (max_ele > arr[i]) arr[i] = max_ele; // Else if update the max_ele also else if (max_ele <= arr[i]) { int temp = arr[i]; arr[i] = max_ele; max_ele = temp; } } } // Driver code public static void main(String args[]) { int arr[] = { 4 , 5 , 2 , 1 , 7 , 6 }; int n = arr.length; // Replace the elements // with the smaller element // on its left side ReplaceElements(arr, n); // Print the modified array for ( int i = 0 ; i < n; ++i) System.out.println(arr[i]); } } // This code is contributed by ankita_saini |
Python3
# Python3 program to Replace every # element with the greater element # on its left side # Function to replace the elements def ReplaceElements(arr, n): # Max value initialised # to element at 0th index max_ele = arr[ 0 ] arr[ 0 ] = - 1 for i in range ( 1 , n): # If max_ele is greater than arr[i] # then just replace arr[i] with max_ele if (max_ele > arr[i]): arr[i] = max_ele # Else if update the max_ele also elif (max_ele < = arr[i]): temp = arr[i] arr[i] = max_ele max_ele = temp # Driver code if __name__ = = "__main__" : arr = [ 4 , 5 , 2 , 1 , 7 , 6 ] n = len (arr) # Replace the elements # with the smaller element # on its left side ReplaceElements(arr, n) # Print the modified array for i in range (n): print ( arr[i], end = " " ) # This code is contributed # by ChitraNayal |
C#
// C# program to Replace every // element with the greater element // on its left side using System; public class GFG { // Function to replace the elements static void ReplaceElements( int []arr, int n) { // Max value initialised // to element at 0th index int max_ele = arr[0]; arr[0] = -1; for ( int i = 1; i < n; ++i) { // If max_ele is greater than arr[i] // then just replace arr[i] with max_ele if (max_ele > arr[i]) arr[i] = max_ele; // Else if update the max_ele also else if (max_ele <= arr[i]) { int temp = arr[i]; arr[i] = max_ele; max_ele = temp; } } } // Driver code public static void Main() { int []arr = { 4, 5, 2, 1, 7, 6 }; int n = arr.Length; // Replace the elements // with the smaller element // on its left side ReplaceElements(arr, n); // Print the modified array for ( int i = 0; i < n; ++i) { Console.Write(arr[i]+ " " ); } } } // This code is contributed by Rajput-Ji |
PHP
<?php // PHP program to Replace every // element with the greater element // on its left side // Function to replace the elements function ReplaceElements( $arr , $n ) { // Max value initialised // to element at 0th index $max_ele = $arr [0]; $arr [0] = -1; for ( $i = 1; $i < $n ; ++ $i ) { // If max_ele is greater than arr[i] // then just replace arr[i] with max_ele if ( $max_ele > $arr [ $i ]) $arr [ $i ] = $max_ele ; // Else if update the max_ele also else if ( $max_ele <= $arr [ $i ]) { $temp = $arr [ $i ]; $arr [ $i ] = $max_ele ; $max_ele = $temp ; } } return $arr ; } // Driver code $arr = array (4, 5, 2, 1, 7, 6); $n = sizeof( $arr ); // Replace the elements // with the smaller element // on its left side $arr1 = ReplaceElements( $arr , $n ); // Print the modified array for ( $i = 0; $i < $n ; ++ $i ) echo $arr1 [ $i ] . " " ; // This code is contributed // by Akanksha Rai |
Javascript
<script> // Java script program to Replace every // element with the greater element // on its left side // Function to replace the elements function ReplaceElements(arr,n) { // Max value initialised // to element at 0th index let max_ele = arr[0]; arr[0] = -1; for (let i = 1; i < n; ++i) { // If max_ele is greater than arr[i] // then just replace arr[i] with max_ele if (max_ele > arr[i]) arr[i] = max_ele; // Else if update the max_ele also else if (max_ele <= arr[i]) { let temp = arr[i]; arr[i] = max_ele; max_ele = temp; } } } // Driver code let arr = [ 4, 5, 2, 1, 7, 6 ]; let n = arr.length; // Replace the elements // with the smaller element // on its left side ReplaceElements(arr, n); // Print the modified array for (let i = 0; i < n; ++i) document.write(arr[i]+ " " ); // This code is contributed by sravan kumar G </script> |
Output
-1 4 5 5 5 7
Time Complexity: O(N)
Auxiliary space: O(1)