Introduction
This blog will discuss the various approaches to solve find the closest value for every element in the array problem. Before jumping on the approach of the problem to get the closest smaller value for every element in the array, let’s first understand the problem,
In this problem, we need to return an array containing the closest value of the respective elements in the array, and if the closest element is not present, which means the size of the array is one, then, we need to print -1.
Note: Closest value here refers to the nearest element with respect to that particular element; it can be either less than or more than that particular value of that element.
For Example:
Input:-
15 |
10 |
6 |
18 |
12 |
1 |
5 |
Output:-
18 |
12 |
5 |
15 |
10 |
5 |
6 |
Brute Force Approach
This approach considers using two nested loops. We’ll try to find the closest element for a particular element using the inner loop in these loops.
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.
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 and closest element for an element.
Step 5. In the second ‘for’ loop, assign the value at the ‘jth’ position of the ‘input’ vector, if that element is close to the respective element.
Step 6. Print the closest element.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
void getResult(vector<int> input, int n)
{
if(n <= 1)
{
cout << "-1" << endl;
return;
}
for(int i = 0 ; i < n ; i++)
{
int mini = INT_MAX;
int mini_diff = INT_MAX;
for(int j = 0 ; j < n ; j++)
{
if(i != j)
{
int temp = abs(input[i] - input[j]);
if(temp < mini_diff)
{
mini = input[j];
mini_diff = temp;
}
}
}
cout << mini << " " ;
}
return;
}
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 << "Resultant Array:- ";
getResult(input, n);
}
Output:
Input Array:- 15 10 6 18 12 1 5
Resultant Array:- 18 12 5 15 10 5 6Complexity Analysis
Time Complexity: O(N * 2)
Incall to ‘getResult()’, we are using nested loops to find the closest element. 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).
305+ registered