Data Modelling & AI Data Structure & Algorithm

Modify given array by reducing each element by its next smaller element

23 June 2025

0

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(N²)
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>

Output:

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>

Output:

4 2 4 2 3

Time Complexity: O(N)
Auxiliary Space: O(N)

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!

Modify given array by reducing each element by its next smaller element

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US