Modify Given Array By Reducing Each Element By Its Next Smaller Element
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 100
Complexity 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).
Optimized Approach
To optimize this Modify given array by reducing each element by its next smaller element problem, we’ll try to optimize time complexity using the stack data structure. In this, we will push the element in the stack if the stack is empty while traversing and if not empty, then we will remove the top element of the stack until the stack becomes empty or the top element is smaller than or equal to that respective element. If the still stack is not empty then reduce the current element value with the top element of the stack and then we need to remove that from the stack.
Note:- We need to traverse the array from the last element.
Algorithm
Step 1. In the function call ‘getResult()’, it takes one parameter:- one integral vector named ‘v’.
Step 2. Initialize a stack named ‘st’ and a variable ‘n’ to store the size of the vector and also initialize a vector named ‘result’ of size ‘n’ with zero.
Step 3. Make an iteration using the ‘for’ loop with the variable ‘i’ ranging from ‘n - 1’ to 0.
Step 4. In this, check if the stack is not empty and if top element of the stack is less than or equal to that particular element at ith index, then assign the value of top element of the stack to the element at ith index of the ‘result’ vector, else, make an iteration using ‘while’ loop till the stack is not empty and top element of the stack is greater than that particular element at ith index of vector ‘v’ and then if still stack is not empty then assign that top element of the stack to the ith index of ‘result’ vector.
Step 5. After all these iterations, push element at ith index of the vector ‘v’ to the stack ‘st’.
Step 6. Make another iteration using ‘for’ loop with variable ‘i’ ranging from 0 to ‘n’ and print the difference of elements at ith indexes of both vector ‘v’ and vector ‘result’.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
void getResult(vector<int>& v)
{
// Initialize the stack
stack<int> st;
int n = v.size();
// To store the corresponding resultant element
vector<int> result(n, 0);
for (int i = n - 1; i >= 0; i--) {
// If stack is not empty
if (!st.empty()) {
// If top element is smaller than the current element
if (st.top() <= v[i]) {
result[i] = st.top();
}
else
{
while (!st.empty() && (st.top() > v[i])) {
st.pop();
}
// If stack is not empty
if (!st.empty()) {
result[i] = st.top();
}
}
}
// Push current element
st.push(arr[i]);
}
// Print the final array
cout << "Modified Array:- " ;
for (int i = 0; i < n; i++)
{
cout << v[i] - result[i] << " ";
}
cout << endl;
}
// Driver Code
int main()
{
// Given array
vector<int> input = { 8, 4, 6, 2, 3 };
cout << "Input Array:- " ;
for(int i = 0 ; i < input.size() ; i++)
{
cout << input[i] << " ";
}
cout << endl;
// Function call
getResult(input);
return 0;
}
Output :
Input array :- 10 5 12 14 3 2 100
Modified Array :- 5 2 9 11 1 2 100
Complexity Analysis
Time Complexity: O(N)
Incall to ‘getResult()’, we are just traversing the whole vector of size ‘N’ once, therefore, the overall time complexity is O(N).
Space Complexity: O(N)
As we are using a stack of at max size ‘n’ space, therefore, the overall space complexity is O(N).
Frequently asked questions
1) What are the predefined functions in the stack?
There are five predefined functions in the stack which are as follows:-
- Push
- Pop
- Empty
- Top
- size
2) What is the time complexity of the push function in stack
In the stack, the overall time complexity of each push operation is constant, i.e., O(1).
3) What is the maximum size of the stack we can use?
Stack is a type of dynamically allocated array, therefore there is no size constraint on the stack.
Key takeaways
In this article, we discussed the What is Modify given array by reducing each element by its next smaller element problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem.
If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.
Until then, All the best for your future endeavors, and Keep Coding.
Comments
No comments yet
Be the first to share what you think