Given an array arr[] which consist of N integers, the task is to replace every element by the smallest of all other elements present in the array.
Examples:
Input: arr[] = {1, 1, 1, 2}
Output: 1 1 1 1Input: arr[] = {4, 2, 1, 3}
Output: 1 1 2 1
Naive Approach:
The simplest approach is to find the smallest of all remaining elements for every element with the help of a nested loop.
Time Complexity: O(N2)
Efficient Approach:
The idea is to maintain prefix and suffix min arrays. Maintain leftMin[] and rightMin[] arrays which stores the minimum on the left and right subarrays for every array element. Once computed, replace every ith index of the original array by storing the minimum of leftMin[i] and rightMin[i].
Below is the implementation of above approach:
C++
// C++ program to replace every element// with the smallest of all other// array elements#include<bits/stdc++.h>using namespace std;void ReplaceElements(int arr[], int n){ // There should be atleast two elements if (n < 2) { cout << (" Invalid Input "); return; } // leftMin array stores minimum // element of left subarray int leftMin[n]; leftMin[0] = INT_MAX; // rightMin array stores minimum // element of right subarray int rightMin[n]; rightMin[n - 1] = INT_MAX; for(int i = 1; i < n; i++) { leftMin[i] = min(leftMin[i - 1], arr[i - 1]); rightMin[n - 1 - i] = min(rightMin[n - 1 - i + 1], arr[n - 1 - i + 1]); } // Update original array with minimum // of leftMin[i] and rightMin[i] for(int i = 0; i < n; i++) { arr[i] = min(leftMin[i], rightMin[i]); } // Print the modified array. for(int i = 0; i < n; ++i) { cout << arr[i] << " "; }}// Driver codeint main(){ int arr[] = { 1, 2, 3, 2 }; int n = sizeof(arr) / sizeof(arr[0]); ReplaceElements(arr, n);}// This code is contributed by chitranayal |
Java
// Java program to replace every element// with the smallest of all other// array elementsimport java.util.*;class GFG { static void ReplaceElements(int[] arr, int n) { /* There should be atleast two elements */ if (n < 2) { System.out.println(" Invalid Input "); return; } // leftMin array stores minimum // element of left subarray int[] leftMin = new int[n]; leftMin[0] = Integer.MAX_VALUE; // rightMin array stores minimum // element of right subarray int[] rightMin = new int[n]; rightMin[n - 1] = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { leftMin[i] = Math.min(leftMin[i - 1], arr[i - 1]); rightMin[n - 1 - i] = Math.min( rightMin[n - 1 - i + 1], arr[n - 1 - i + 1]); } // Update original array with minimum // of leftMin[i] and rightMin[i] for (int i = 0; i < n; i++) { arr[i] = Math.min(leftMin[i], rightMin[i]); } // Print the modified array. for (int i = 0; i < n; ++i) { System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 2 }; int n = arr.length; ReplaceElements(arr, n); }} |
Python3
# Python3 program to replace every# element with the smallest of all # other array elements import sysdef ReplaceElements(arr, n): # There should be atleast two elements if (n < 2): print(" Invalid Input ") return # leftMin array stores minimum # element of left subarray leftMin = [0] * n leftMin[0] = sys.maxsize # rightMin array stores minimum # element of right subarray rightMin = [0] * n rightMin[n - 1] = sys.maxsize for i in range(1, n): leftMin[i] = min(leftMin[i - 1], arr[i - 1]) rightMin[n - 1 - i] = min(rightMin[n - 1 - i + 1], arr[n - 1 - i + 1]) # Update original array with minimum # of leftMin[i] and rightMin[i] for i in range(n): arr[i] = min(leftMin[i], rightMin[i]) # Print the modified array. print(*arr, sep = " ")# Driver code arr = [ 1, 2, 3, 2 ]n = len(arr)ReplaceElements(arr, n)# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to replace every element// with the smallest of all other// array elementsusing System;class GFG{static void ReplaceElements(int[] arr, int n){ // There should be atleast two elements if (n < 2) { Console.Write(" Invalid Input "); return; } // leftMin array stores minimum // element of left subarray int[] leftMin = new int[n]; leftMin[0] = Int32.MaxValue; // rightMin array stores minimum // element of right subarray int[] rightMin = new int[n]; rightMin[n - 1] = Int32.MaxValue; for(int i = 1; i < n; i++) { leftMin[i] = Math.Min(leftMin[i - 1], arr[i - 1]); rightMin[n - 1 - i] = Math.Min( rightMin[n - 1 - i + 1], arr[n - 1 - i + 1]); } // Update original array with minimum // of leftMin[i] and rightMin[i] for(int i = 0; i < n; i++) { arr[i] = Math.Min(leftMin[i], rightMin[i]); } // Print the modified array. for(int i = 0; i < n; ++i) { Console.Write(arr[i] + " "); }}// Driver codepublic static void Main(){ int []arr = { 1, 2, 3, 2 }; int n = arr.Length; ReplaceElements(arr, n);}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript program to replace every element// with the smallest of all other// array elementsfunction ReplaceElements(arr, n){ // There should be atleast two elements if (n < 2) { document.write(" Invalid Input "); return; } // leftMin array stores minimum // element of left subarray var leftMin = Array(n); leftMin[0] = 1000000000; // rightMin array stores minimum // element of right subarray var rightMin = Array(n); rightMin[n - 1] = 10000000000; for(var i = 1; i < n; i++) { leftMin[i] = Math.min(leftMin[i - 1], arr[i - 1]); rightMin[n - 1 - i] = Math.min(rightMin[n - 1 - i + 1], arr[n - 1 - i + 1]); } // Update original array with minimum // of leftMin[i] and rightMin[i] for(var i = 0; i < n; i++) { arr[i] = Math.min(leftMin[i], rightMin[i]); } // Print the modified array. for(var i = 0; i < n; ++i) { document.write( arr[i] + " "); }}// Driver codevar arr = [1, 2, 3, 2];var n = arr.length;ReplaceElements(arr, n);// This code is contributed by famously.</script> |
Output:
2 1 1 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Efficient Approach: The idea is to find the smallest and second smallest element in the array by traversing it. Then, traverse the array one more time:
- If the current element is the smallest element, then replace it with second smallest element.
- Else replace the current element with the smallest element
Below is the implementation of the above approach:
C++
// C++ program to replace every // element with the smallest// of all other array elements#include <bits/stdc++.h>using namespace std;void ReplaceElements(int arr[], int n){ // There should be // atleast two elements if (n < 2) { cout << " Invalid Input "; return; } // first stores minimum // element of the array int first = INT_MAX; // second stores second // minimum element of the array int second = INT_MAX; // Find the smallest and second // smallest elements of the array for(int i = 0; i < n; i++) { // If current element is smaller // than first then update both // first and second if (arr[i] < first) { second = first; first = arr[i]; } // If arr[i] is in between // first and second // then update second else if (arr[i] < second && arr[i] != first) second = arr[i]; } // Update original array with // first and second for(int i = 0; i < n; i++) { arr[i] = (arr[i] == first) ? second : first; } // Print the modified array. for(int i = 0; i < n; ++i) { cout << arr[i] << " "; }} // Driver codeint main(){ int arr[] = { 1, 2, 3, 2 }; int n = sizeof(arr) / sizeof(arr[0]); ReplaceElements(arr, n);} // This code is contributed by himanshu77 |
Java
// Java program to replace// every element with the smallest// of all other array elementsimport java.util.*;class GFG { static void ReplaceElements(int[] arr, int n) { // There should be // atleast two elements if (n < 2) { System.out.println( " Invalid Input "); return; } // first stores minimum // element of the array int first = Integer.MAX_VALUE; // second stores second // minimum element of the array int second = Integer.MAX_VALUE; // Find the smallest and second // smallest elements of the array for (int i = 0; i < n; i++) { // If current element // is smaller than first // then update both // first and second if (arr[i] < first) { second = first; first = arr[i]; } // If arr[i] is in between // first and second // then update second else if (arr[i] < second && arr[i] != first) second = arr[i]; } // Update original array with // first and second for (int i = 0; i < n; i++) { arr[i] = (arr[i] == first) ? second : first; } // Print the modified array. for (int i = 0; i < n; ++i) { System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 2 }; int n = arr.length; ReplaceElements(arr, n); }} |
Python3
# Python3 program to replace# every element with the smallest# of all other array elementsimport sysdef ReplaceElements(arr, n): # There should be # atleast two elements if (n < 2): print(" Invalid Input ") return # first stores minimum # element of the array first = sys.maxsize # second stores second # minimum element of the array second = sys.maxsize # Find the smallest and second # smallest elements of the array for i in range(n): # If current element # is smaller than first # then update both # first and second if (arr[i] < first): second = first first = arr[i] # If arr[i] is in between # first and second # then update second elif (arr[i] < second and arr[i] != first): second = arr[i] # Update original array with # first and second for i in range(n): if (arr[i] == first): arr[i] = second else: arr[i] = first # Print the modified array. for i in range(n): print(arr[i], end = " ")# Driver codeif __name__ == '__main__': arr = [ 1, 2, 3, 2 ] n = len(arr) ReplaceElements(arr, n)# This code is contributed by Amit Katiyar |
C#
// C# program to replace every // element with the smallest// of all other array elementsusing System;class GFG{ static void ReplaceElements(int[] arr, int n){ // There should be // atleast two elements if (n < 2) { Console.WriteLine(" Invalid Input "); return; } // first stores minimum // element of the array int first = Int32.MaxValue; // second stores second // minimum element of the array int second = Int32.MaxValue; // Find the smallest and second // smallest elements of the array for(int i = 0; i < n; i++) { // If current element // is smaller than first // then update both // first and second if (arr[i] < first) { second = first; first = arr[i]; } // If arr[i] is in between // first and second // then update second else if (arr[i] < second && arr[i] != first) second = arr[i]; } // Update original array with // first and second for(int i = 0; i < n; i++) { arr[i] = (arr[i] == first) ? second : first; } // Print the modified array. for(int i = 0; i < n; ++i) { Console.Write(arr[i] + " "); }}// Driver code static void Main(){ int[] arr = { 1, 2, 3, 2 }; int n = arr.Length; ReplaceElements(arr, n);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program to replace every // element with the smallest// of all other array elementsfunction ReplaceElements(arr, n){ // There should be // atleast two elements if (n < 2) { document.write( " Invalid Input "); return; } // first stores minimum // element of the array var first = Number.MAX_VALUE; // second stores second // minimum element of the array var second = Number.MAX_VALUE; // Find the smallest and second // smallest elements of the array for(var i = 0; i < n; i++) { // If current element is smaller // than first then update both // first and second if (arr[i] < first) { second = first; first = arr[i]; } // If arr[i] is in between // first and second // then update second else if (arr[i] < second && arr[i] != first) second = arr[i]; } // Update original array with // first and second for(var i = 0; i < n; i++) { arr[i] = (arr[i] == first) ? second : first; } // Print the modified array. for(var i = 0; i < n; ++i) { document.write( arr[i] + " "); }}var arr = [ 1, 2, 3, 2 ];var n = arr.length;ReplaceElements(arr, n);// This code is contributed by SoumikMondal</script> |
Output:
2 1 1 1
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
