Modify given array by reducing each element by its next smaller element
Given an array arr[] of length N, the task is to modify the given array by replacing each element of the given array by its next smaller element, if possible. Print the modified array as the required answer.
Examples:
Input: arr[] = {8, 4, 6, 2, 3}
Output: 4 2 4 2 3
Explanation: The operations can be performed as follows:
- For arr[0], arr[1] is the next smaller element.
- For arr[1], arr[3] is the next smaller element.
- For arr[2], arr[3] is the next smaller element.
- For arr[3], no smaller element present after it.
- For arr[4], no smaller element present after it.
Input: arr[] = {1, 2, 3, 4, 5}
Output: 1 2 3 4 5
Naive Approach: The simplest approach is to traverse the array and for each element, traverse the remaining elements after it and check if any smaller element is present or not. If found, reduce that element by the first smaller element obtained.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the final array // after reducing each array element // by its next smaller element void printFinalPrices(vector< int >& arr) { // Stores the resultant array vector< int > ans; // Traverse the array for ( int i = 0; i < arr.size(); i++) { int flag = 1; for ( int j = i + 1; j < arr.size(); j++) { // If a smaller element is found if (arr[j] <= arr[i]) { // Reduce current element by // next smaller element ans.push_back(arr[i] - arr[j]); flag = 0; break ; } } // If no smaller element is found if (flag == 1) ans.push_back(arr[i]); } // Print the answer for ( int i = 0; i < ans.size(); i++) cout << ans[i] << " " ; } // Driver Code int main() { // Given array vector< int > arr = { 8, 4, 6, 2, 3 }; // Function Call printFinalPrices(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the final array // after reducing each array element // by its next smaller element static void printFinalPrices( int [] arr) { // Stores the resultant array ArrayList<Integer> ans = new ArrayList<Integer>(); // Traverse the array for ( int i = 0 ; i < arr.length; i++) { int flag = 1 ; for ( int j = i + 1 ; j < arr.length; j++) { // If a smaller element is found if (arr[j] <= arr[i]) { // Reduce current element by // next smaller element ans.add(arr[i] - arr[j]); flag = 0 ; break ; } } // If no smaller element is found if (flag == 1 ) ans.add(arr[i]); } // Print the answer for ( int i = 0 ; i < ans.size(); i++) System.out.print(ans.get(i) + " " ); } // Driver Code public static void main(String[] args) { // Given array int [] arr = { 8 , 4 , 6 , 2 , 3 }; // Function Call printFinalPrices(arr); } } // This code is contributed by code_hunt |
Python3
# Python3 program for the above approach # Function to print the final array # after reducing each array element # by its next smaller element def printFinalarr(arr): # Stores resultant array ans = [] # Traverse the given array for i in range ( len (arr)): flag = 1 for j in range (i + 1 , len (arr)): # If a smaller element is found if arr[j] < = arr[i]: # Reduce current element by # next smaller element ans.append(arr[i] - arr[j]) flag = 0 break if flag: # If no smaller element is found ans.append(arr[i]) # Print the final array for k in range ( len (ans)): print (ans[k], end = ' ' ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 8 , 4 , 6 , 2 , 3 ] # Function call printFinalarr(arr) |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the final array // after reducing each array element // by its next smaller element static void printFinalPrices( int [] arr) { // Stores the resultant array List< int > ans = new List< int >(); // Traverse the array for ( int i = 0; i < arr.Length; i++) { int flag = 1; for ( int j = i + 1; j < arr.Length; j++) { // If a smaller element is found if (arr[j] <= arr[i]) { // Reduce current element by // next smaller element ans.Add(arr[i] - arr[j]); flag = 0; break ; } } // If no smaller element is found if (flag == 1) ans.Add(arr[i]); } // Print the answer for ( int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " " ); } // Driver code static void Main() { // Given array int [] arr = { 8, 4, 6, 2, 3 }; // Function Call printFinalPrices(arr); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Js program for the above approach // Function to print the final array // after reducing each array element // by its next smaller element function printFinalPrices( arr) { // Stores the resultant array let ans = []; // Traverse the array for (let i = 0; i < arr.length; i++) { let flag = 1; for (let j = i + 1; j < arr.length; j++) { // If a smaller element is found if (arr[j] <= arr[i]) { // Reduce current element by // next smaller element ans.push(arr[i] - arr[j]); flag = 0; break ; } } // If no smaller element is found if (flag == 1) ans.push(arr[i]); } // Print the answer for (let i = 0; i < ans.length; i++) document.write(ans[i], " " ); } // Driver Code // Given array let arr = [ 8, 4, 6, 2, 3 ]; // Function Call printFinalPrices(arr); </script> |
4 2 4 2 3
Time Complexity: O(N^2) ,As we are running two nested loops to traverse the array.
Space Complexity: O(N),As we are storing the resultant array.
Efficient Approach: To optimize the above approach, the idea is to use Stack data structure. Follow the steps below to solve the problem:
- Initialize a Stack and an array ans[] of size N, to store the resultant array.
- Traverse the given array over the indices i = N – 1 to 0.
- If the stack is empty, push the current element arr[i] to the top of the stack.
- Otherwise, if the current element is greater than the element at the top of the stack, push it into the stack and then remove elements from the stack, until the stack becomes empty or an element smaller than or equal to arr[i] is found. After that, if the stack is not empty, set ans[i] = arr[i] – top element of the stack and then remove it from the stack.
- Otherwise, remove the top element from the stack and set ans[i] equal to the top element in the stack and then remove it from the stack.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the final array // after reducing each array element // by its next smaller element void printFinalPrices(vector< int >& arr) { // Initialize stack stack< int > minStk; // Array size int n = arr.size(); // To store the corresponding element vector< int > reduce(n, 0); for ( int i = n - 1; i >= 0; i--) { // If stack is not empty if (!minStk.empty()) { // If top element is smaller // than the current element if (minStk.top() <= arr[i]) { reduce[i] = minStk.top(); } else { // Keep popping until stack is empty // or top element is greater than // the current element while (!minStk.empty() && (minStk.top() > arr[i])) { minStk.pop(); } // If stack is not empty if (!minStk.empty()) { reduce[i] = minStk.top(); } } } // Push current element minStk.push(arr[i]); } // Print the final array for ( int i = 0; i < n; i++) cout << arr[i] - reduce[i] << " " ; } // Driver Code int main() { // Given array vector< int > arr = { 8, 4, 6, 2, 3 }; // Function call printFinalPrices(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the final array // after reducing each array element // by its next smaller element static void printFinalPrices( int [] arr) { // Initialize stack Stack<Integer> minStk = new Stack<>(); // Array size int n = arr.length; // To store the corresponding element int [] reduce = new int [n]; for ( int i = n - 1 ; i >= 0 ; i--) { // If stack is not empty if (!minStk.isEmpty()) { // If top element is smaller // than the current element if (minStk.peek() <= arr[i]) { reduce[i] = minStk.peek(); } else { // Keep popping until stack is empty // or top element is greater than // the current element while (!minStk.isEmpty() && (minStk.peek() > arr[i])) { minStk.pop(); } // If stack is not empty if (!minStk.isEmpty()) { reduce[i] = minStk.peek(); } } } // Push current element minStk.add(arr[i]); } // Print the final array for ( int i = 0 ; i < n; i++) System.out.print(arr[i] - reduce[i] + " " ); } // Driver Code public static void main(String[] args) { // Given array int [] arr = { 8 , 4 , 6 , 2 , 3 }; // Function call printFinalPrices(arr); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Function to print the final array # after reducing each array element # by its next smaller element def printFinalPrices(arr): # Initialize stack minStk = [] # To store the corresponding element reduce = [ 0 ] * len (arr) for i in range ( len (arr) - 1 , - 1 , - 1 ): # If stack is not empty if minStk: # If top element is smaller # than the current element if minStk[ - 1 ] < = arr[i]: reduce [i] = minStk[ - 1 ] else : # Keep popping until stack is empty # or top element is greater than # the current element while minStk and minStk[ - 1 ] > arr[i]: minStk.pop() if minStk: # Corresponding elements reduce [i] = minStk[ - 1 ] # Push current element minStk.append(arr[i]) # Final array for i in range ( len (arr)): print (arr[i] - reduce [i], end = ' ' ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 8 , 4 , 6 , 2 , 3 ] # Function Call printFinalPrices(arr) |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to print the readonly array // after reducing each array element // by its next smaller element static void printFinalPrices( int [] arr) { // Initialize stack Stack< int > minStk = new Stack< int >(); // Array size int n = arr.Length; // To store the corresponding element int [] reduce = new int [n]; for ( int i = n - 1; i >= 0; i--) { // If stack is not empty if (minStk.Count != 0) { // If top element is smaller // than the current element if (minStk.Peek() <= arr[i]) { reduce[i] = minStk.Peek(); } else { // Keep popping until stack is empty // or top element is greater than // the current element while (minStk.Count != 0 && (minStk.Peek() > arr[i])) { minStk.Pop(); } // If stack is not empty if (minStk.Count != 0) { reduce[i] = minStk.Peek(); } } } // Push current element minStk.Push(arr[i]); } // Print the readonly array for ( int i = 0; i < n; i++) Console.Write(arr[i] - reduce[i] + " " ); } // Driver Code public static void Main(String[] args) { // Given array int [] arr = { 8, 4, 6, 2, 3 }; // Function call printFinalPrices(arr); } } // This code contributed by shikhasingrajput |
Javascript
<script> // javascript program for the above approach // Function to print the final array // after reducing each array element // by its next smaller element function printFinalPrices(arr) { // Initialize stack var minStk = [] // Array size var n = arr.length; var i; // To store the corresponding element var reduce = Array(n).fill(0); for (i = n - 1; i >= 0; i--) { // If stack is not empty if (minStk.length>0) { // If top element is smaller // than the current element if (minStk[minStk.length-1] <= arr[i]) { reduce[i] = minStk[minStk.length-1]; } else { // Keep popping until stack is empty // or top element is greater than // the current element while (minStk.length>0 && (minStk[minStk.length-1] > arr[i])) { minStk.pop(); } // If stack is not empty if (minStk.length>0) { reduce[i] = minStk[minStk.length-1]; } } } // Push current element minStk.push(arr[i]); } // Print the final array for (i = 0; i < n; i++) document.write(arr[i] - reduce[i] + " " ); } // Driver Code // Given array var arr = [8, 4, 6, 2, 3]; // Function call printFinalPrices(arr); // This code is contributed by ipg2016107. </script> |
4 2 4 2 3
Time Complexity: O(N)
Auxiliary Space: O(N)