Given an array of integers, the task is to replace every element with the smallest 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 4 2 1 1
Since, 4 has no element in its left, so replace it by -1.
For 5, 4 is the smallest element in its left.
For 2, 4 is the smallest element in its left.
For 1, 2 is the smallest element in its left.
For 7, 1 is the smallest element in its left.
For 6, 1 is the smallest element in its left.
Input: arr[] = {3, 2, 5, 7, 1}
Output: -1 3 2 2 2
Approach:
- Maintain a variable min_ele which will store the smallest element.
- Initially, min_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 min_ele value and update the min_ele if the element is smaller than min_ele.
- Print the modified array.
Below is the implementation of the above approach:
C++
// C++ program to Replace every// element with the smaller element// on its left side#include <bits/stdc++.h>using namespace std;// Function to replace the elementsvoid ReplaceElements(int arr[], int n){ // MIN value initialised // to element at 0th index int min_ele = arr[0]; arr[0] = -1; for (int i = 1; i < n; ++i) { // If min_ele is smaller than arr[i] // then just replace arr[i] with min_ele if (min_ele < arr[i]) arr[i] = min_ele; // Else if update the min_ele also else if (min_ele >= arr[i]) { int temp = arr[i]; arr[i] = min_ele; min_ele = temp; } }}// Driver codeint 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 smaller element // on its left side class GFG {// Function to replace the elements static void ReplaceElements(int arr[], int n) { // MIN value initialised // to element at 0th index int min_ele = arr[0]; arr[0] = -1; for (int i = 1; i < n; ++i) { // If min_ele is smaller than arr[i] // then just replace arr[i] with min_ele if (min_ele < arr[i]) { arr[i] = min_ele; } // Else if update the min_ele also else if (min_ele >= arr[i]) { int temp = arr[i]; arr[i] = min_ele; min_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.print(arr[i] + " "); } }}// This code is contributed by Rajput-JI |
Python3
# Python3 program to Replace every# element with the smaller element# on its left side# Function to replace the elementsdef ReplaceElements(arr, n): # MIN value initialised # to element at 0th index min_ele = arr[0] arr[0] = -1 for i in range(1, n): # If min_ele is smaller than arr[i] # then just replace arr[i] with min_ele if (min_ele < arr[i]): arr[i] = min_ele # Else if update the min_ele also elif (min_ele >= arr[i]) : temp = arr[i] arr[i] = min_ele min_ele = temp# Driver codeif __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 smaller element // on its left side using System;public class GFG { // Function to replace the elements static void ReplaceElements(int []arr, int n) { // MIN value initialised // to element at 0th index int min_ele = arr[0]; arr[0] = -1; for (int i = 1; i < n; ++i) { // If min_ele is smaller than arr[i] // then just replace arr[i] with min_ele if (min_ele < arr[i]) { arr[i] = min_ele; } // Else if update the min_ele also else if (min_ele >= arr[i]) { int temp = arr[i]; arr[i] = min_ele; min_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 smaller element// on its left side// Function to replace the elementsfunction ReplaceElements($arr, $n){ // MIN value initialised // to element at 0th index $min_ele = $arr[0]; $arr[0] = -1; for ($i = 1; $i < $n; ++$i) { // If min_ele is smaller than arr[i] // then just replace arr[i] with min_ele if ($min_ele < $arr[$i]) $arr[$i] = $min_ele; // Else if update the min_ele also else if ($min_ele >= $arr[$i]) { $temp = $arr[$i]; $arr[$i] = $min_ele; $min_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 arrayfor ($i = 0; $i < $n; ++$i) echo $arr1[$i] . " ";// This code is contributed // by Akanksha Rai?> |
Javascript
<script> // JavaScript program to Replace every // element with the smaller element // on its left side // Function to replace the elements function ReplaceElements(arr, n) { // MIN value initialised // to element at 0th index var min_ele = arr[0]; arr[0] = -1; for (var i = 1; i < n; ++i) { // If min_ele is smaller than arr[i] // then just replace arr[i] with min_ele if (min_ele < arr[i]) arr[i] = min_ele; // Else if update the min_ele also else if (min_ele >= arr[i]) { var temp = arr[i]; arr[i] = min_ele; min_ele = temp; } } } // Driver code var arr = [4, 5, 2, 1, 7, 6]; var n = arr.length; // Replace the elements // with the smaller element // on its left side ReplaceElements(arr, n); // Print the modified array for (var i = 0; i < n; ++i) document.write(arr[i] + " "); // This code is contributed by rdtank. </script> |
Output
-1 4 4 2 1 1
Time Complexity: O(N)
Auxiliary Space: O(1) because constant space is being used for variables
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
