Introduction
This blog will discuss the various approaches to finding the closest smaller element for each element in the array. Before jumping on the approach of the problem to get the closest smaller element for each element in the array, let’s first understand the problem.
Problem Statement
In this problem, we need to return an array containing the closest smaller element of the respective elements in the array. If the closest smaller element is not present, then we need to insert -1 at that position. The closest smaller element means that the element should be closer to the element in respect of the difference between them, and the element must be lesser than that respective element.
Example
Input:
15 |
10 |
6 |
18 |
12 |
1 |
5 |
Output:
12 |
6 |
5 |
15 |
10 |
-1 |
1 |
Brute Force Approach
This approach considers using two nested loops. We’ll try to find the closest smaller element for a particular element using the inner loop in these loops, which means the whole array will be traversed for each and every element to find its closest smaller element.
Steps of Algorithm
Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one vector of integer ‘input’, and the second one is the ‘N’ - the size of the vector ‘input’.
Step 2. Create a base case in which print -1, if the size of the ‘input’ array is one or less than one.
Step 3. Make nested iterations using the ‘for’ loop with the help of ‘i’ and ‘j’ variables.
Step 4. Take two variables to store the difference of the elements and the closest smaller element for an element.
Step 5. In the second ‘for’ loop, if we are not dealing with the same element, then calculate the difference between both the elements and store its absolute value in the ‘diff’.
Step 6. If that difference is less than the previously stored minimum difference in the ‘temp’ variable, and the element’s value is lesser than the value of the respective elements, then assign the new difference value to ‘temp’ and the element’s value to ‘nearest’
Step 7. Print the value of ‘nearest’.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
void getResult(vector<int> input, int n)
{
// If no more than 1 element is present in the array
if(n <= 1)
{
cout << "-1" << endl;
return;
}
// Nested loops to check the closest smaller element
for(int i = 0 ; i < n ; i++)
{
int temp = INT_MAX;
int nearest = -1;
// A loop to check the entire array
for(int j = 0 ; j < n ; j++)
{
// Check all the elements of the array except the respective element itself
if(i != j)
{
int diff = abs(input[i] - input[j]);
if(diff < temp && (input[j] < input[i]))
{
nearest = input[j];
temp = diff;
}
}
}
cout << nearest << ", ";
}
cout << endl;
}
int main()
{
vector<int> input = { 15, 10, 6, 18, 12, 1, 5};
int n = input.size();
cout << "Input Array:- ";
for(int i = 0 ; i < n ; i++)
{
cout << input[i] << ", ";
}
cout << endl;
cout << "Closest Smaller Element for each element in the array are: ";
getResult(input, n);
cout << endl;
}
Output:
Input Array:- 15, 10, 6, 18, 12, 1, 5,
Closest Smaller Element for each element in the array are: 12, 6, 5, 15, 10, -1, 1,Complexity Analysis
Time Complexity: O(N * 2)
In call to ‘getResult()’, we are using nested loops to find the closest smaller element for each element in the array, therefore, the overall time complexity is O(N * 2), where ‘N’ is the size of the ‘input’ vector.
Space Complexity: O(1)
As we are using constant space, therefore, the overall space complexity will be O(1).
Efficient Approach
This approach considers inserting and getting the smaller element that is the closest while consuming only ‘log N’ time, where ‘N’ denotes the size of the array. This can be achieved using the Self-Balancing BST, where BST represents the Binary Search Tree.
Steps of Algorithm
Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one vector of integer ‘input’, and the second one is the ‘N’ - the size of the vector ‘input’.
Step 2. Create a TreeSet of an integer using STL named ‘temp’.
Step 3. Insert all the elements of the ‘input’ vector in treeset ‘temp’ using the ‘for’ loop.
Step 4. Make an iteration using the ‘for’ loop with variable ‘i’.
Step 5. In this ‘for’ loop, find the largest smallest value from the treeset ‘temp’ according to the element at index ‘i’ in the input vector using the ‘lower_bound’ function and assign this value to a variable ‘smallest’.
Step 6. Now check if the value of ‘smallest’ is equal to the value of the initial pointer of the treeset, which means that the closest smaller value is not present, then print -1, else, print the value at the previous pointer of ‘smallest’.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
void getResult(vector<int> input, int n)
{
// Inserting all the elements of the 'input' vector in TreeSet
set<int> temp;
for (int i = 0; i < n; i++)
{
temp.insert(input[i]);
}
// To get the largest smaller element for respective element
for (int i = 0; i < n; i++)
{
auto smallest = temp.lower_bound(input[i]);
// If no smaller element is not present
if (smallest == temp.begin())
{
cout << -1 << ", ";
}
else
cout << *(--smallest) << ", ";
}
}
int main()
{
vector<int> input = {15, 10, 6, 18, 12, 1, 5};
int n = input.size();
cout << "Input Array:- ";
for(int i = 0; i < n ; i++)
{
cout << input[i] << ", ";
}
cout << endl;
cout << "Required Array:- ";
getResult(input, n);
cout << endl;
return 0;
}
Output:
Input Array:- 15, 10, 6, 18, 12, 1, 5,
Closest Smaller Element for each element in the array are: 12, 6, 5, 15, 10, Complexity Analysis
Time Complexity: O(N * Log N)
Incall to ‘getResult()’, we are inserting and calculating the smallest value at the same time, which will take log N time, and due to the ‘for’ loop ranging from 0 - ‘N’, the overall time complexity is O(N * log N), where ‘N’ is the size of the ‘input’ vector.
Space Complexity: O(N)
As we are using a treeset of at max ‘N’ size, therefore, the overall space complexity will be O(N).
You can also read about insertion into bst.
8+ registered 