Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Brute Force Approach
2.1.1.
Steps of Algorithm
2.1.2.
Implementation in C++
2.1.3.
Complexity Analysis
2.2.
Efficient Approach
2.2.1.
Steps of Algorithm
2.2.2.
Implementation in C++
2.2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the TreeSet?
3.2.
What is the brute force approach for this problem?
3.3.
Can we use sorting for this problem?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Find Closest Smaller Value For Every Element In Array

Harsh Goyal
0 upvote

## 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:

Output:

### 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.

## Frequently Asked Questions

### What is the TreeSet?

TreeSet is a type of storage that uses the tree as its storage, and it stores elements in sorted order, in other words, it is a self-balancing BST.

### What is the brute force approach for this problem?

The brute force approach for this problem is to use two nested loops, in which we check the whole array for a particular element and compute the closest smaller element for that respective element.

### Can we use sorting for this problem?

Yes, we can use sorting for this problem, in which we have to sort all the elements of the ‘input’ array, and we need to traverse from right to left and find the smaller element.

## Conclusion

In this article, we discussed the What is Find the closest smaller value for every element in the array problem, discussed the various approaches to solve this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the time complexity of the problem.

Refer to this article for Top Array Coding Interview Questions to ace your programming skills in the array data structure.

Check out some of the articles based on the Binary Search TreeCheck if a given Binary Search Tree is height-balanced like a Red-Black Tree, and Check if the binary tree contains a balanced BST of size k.

Also, refer to other self-balancing binary search tree articles for future reference like→ Red-Black Tree, and AVL Trees

Recommended Problem - Merge K Sorted Arrays

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! Enroll in our courses, refer to the test series and problems available, and look at the problems, interview experiences, and interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, etc.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass