Introduction
This blog will discuss the various approaches to solve the Modify given array by reducing each element by its next smaller element problem. Before jumping into the problem to Modify the given array by reducing each element by its next smaller element, let’s first understand how we need to modify our array.
In this problem, we need to reduce the individual element with its next smaller element, and after that, we need to print that modified array.
For Example:-
Array:-
8 |
4 |
6 |
2 |
3 |
Output:-
4 |
2 |
4 |
2 |
3 |
Explanation:
In this example,
The Element at the ‘0th’ index will be replaced by the difference of its next smaller element i,e. 4 (8 - 4 = 4).
The Element at the ‘1st’ index will be replaced by the difference of its next smaller element i,e. 2 (4 - 2 = 2).
The Element at the ‘2nd’ index will be replaced by the difference of its next smaller element i,e. 2 (6 - 2 = 4).
The Element at the ‘3rd’ index will not be replaced by the difference of its next smaller element because no element is smaller than this element in the later part of the array.
The Element at the ‘4th’ index will not be replaced by the difference of its next smaller element because no element is smaller than this element in the later part of the array.
Brute Force Approach
Brute Force Solution considers traversing the complete array and checking each element with the remaining elements left in the array for the smaller element. If found then we need to reduce that respective element.
Algorithm
Step 1. Create a function ‘getResult()’ that will accept one parameter, i.e., one vector of integer named ‘v’.
Step 2. Initialize an empty vector ‘result’ to store the modified vector.
Step 3. Make an iteration using a ‘for’ loop with variable ‘i’ ranging from 0 to the size of the vector ‘v’.
Step 4. Initialize a boolean variable ‘temp’ with 1, which means a true value.
Step 5. Make another iteration using a ‘for’ loop with variable ‘j’ ranging from ‘i + 1’ to the size of the vector ‘v’.
Step 6. In this loop, we need to check that if the element at index ‘j’ of vector ‘v’ is smaller than or equal to the element at index ‘i’ of vector ‘v’ then we need to push the difference of both the elements in the ‘result’ vector, and assign false value to ‘temp’ and after this we need to break the loop.
Step 7. After this whole iteration, if the value of ‘temp’ is true, then push the element at index ‘i’ of vector ‘v’ to the ‘result’ vector.
Step 8. Return the ‘result’ vector and print it in the ‘main’ function.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
vector<int> getResult(vector<int>& v)
{
// Stores the resultant vector
vector<int> result;
// Traverse the complete array
for (int i = 0; i < v.size(); i++)
{
int temp = 1;
for (int j = i + 1; j < v.size(); j++) {
// If a smaller element is found after that respective element
if (v[j] <= v[i]) {
// Reduce current element by next smaller element
result.push_back(v[i] - v[j]);
temp = 0;
break;
}
}
// If no smaller element is found
if (temp == 1)
result.push_back(v[i]);
}
return result;
}
// Driver Code
int main()
{
// Given array
vector<int> input = { 10, 5, 12, 14, 3, 2, 100};
cout << "Input Array :- ";
for(int i = 0 ; i < input.size() ; i++)
{
cout << input[i] << " " ;
}
cout << endl;
// Function Call
vector<int> output;
output = getResult(input);
cout << "Modified Array :- ";
for(int i = 0 ; i < output.size() ; i++)
{
cout << output[i] << " " ;
}
cout << endl;
return 0;
}
Output :
Input array :- 10 5 12 14 3 2 100
Modified Array :- 5 2 9 11 1 2 100Complexity Analysis
Time Complexity: O(N * 2)
Incall to ‘getResult()’, we are using the nested loop to check for each element and then reduce it accordingly, therefore, the overall time complexity is O(N).
Space Complexity: O(N)
As we are using a vector of size ‘N’ to store the resultant array, therefore, the overall space complexity will be O(N).
Read More - Time Complexity of Sorting Algorithms
40+ registered 
