1.
Introduction
2.
Brute Force Approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Efficient Approach
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.3.
Complexity Analysis
4.
4.1.
What is the unordered map used in the above approach?
4.2.
Can we copy two vectors without running a ‘for’ loop?
4.3.
What is the average case time complexity to sort the vector using the inbuilt sort function?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find Closest Value For Every Element In Array

Harsh Goyal
0 upvote

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

Output:-

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 6``````

Complexity 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).

Efficient Approach

This approach considers sorting the copy of the ‘input’ vector and then iterating over that sorted array to calculate the closest value with respect to the element. Then, it adds that closest value in the unordered_map along with its key.

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 an auxiliary vector ‘copy’ and copy all the elements of the ‘input’ vector in ‘copy’.

Step 3. Sort the ‘copy’ vector.

Step 4. Apply the base case, that if the size of the ‘input’ vector received is one, then we need to print -1.

Step 5. If the size of the vector is two, then manually assign the closest value in the map, and then print them.

Step 6. Manually assign the closest value of the first and last element in the map, and then assign all the closest value using a ‘for’ loop iterating over the ‘copy’ sorted vector.

Step 7. Make another iteration using the ‘for’ loop, and print all the closest value stored in ‘mp’ with respect to each element in ‘input’ vector.

Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
void getResult(vector<int> input, int n)
{
if(n <= 1)
{
cout << "-1 " << endl;
return;
}
vector<int> copy;
copy = input;
unordered_map<int,int> mp;
sort(copy.begin(), copy.end());
if(n == 2)
{
mp[copy[0]] = copy[1];
mp[copy[1]] = copy[0];
for(int i = 0 ; i < n ; i++)
{
cout << mp[input[i]] << ", ";
}
cout << endl;
return;
}
mp[copy[0]] = copy[1];
mp[copy[n - 1]] = copy[n - 2];

for(int i = 1 ; i < (n - 1) ; i++)
{
int x = abs(copy[i] - copy[i - 1]);
int y = abs(copy[i] - copy[i + 1]);
int res = x >= y ? copy[i + 1] : copy[i - 1];
mp[copy[i]] = res;
}
for(int i = 0 ; i < n ; i++)
{
cout << mp[input[i]] << " ";
}
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);
cout << endl;
}``````

Output:

``````Input Array:- 15 10 6 18 12 1 5
Resultant Array:- 18 12 5 15 10 5 6``````

Complexity Analysis

Time Complexity: O(N * log N)

Incall to ‘getResult()’, we are sorting the array, which will take N * logN computational time, and then iterating the whole vector of size ‘N’ to calculate and insert the closest value in the unordered map; therefore, 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 auxiliary vector ‘copy’ and one unordered_map ‘mp,’ therefore, the overall space complexity will be O(N).

What is the unordered map used in the above approach?

The unordered map is used to store the key and a mapped value. In this code, the mapped value is the closest element in the array with respect to the key.

Can we copy two vectors without running a ‘for’ loop?

Yes, we can copy two vectors using the assignment (=) operator in the code.

What is the average case time complexity to sort the vector using the inbuilt sort function?

The average case time complexity to sort the vector using the inbuilt sort function is O(N * logN).

Conclusion

In this article, we discussed the find the closest value for every element in the array problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach 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.

Also check out - Inorder Predecessor

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

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

Live masterclass