Arrays: Find the closest greater element for every array element from another array

Problem Statement:

You are given 2 arrays a[] and b[], you need to build a new array c[], such that every element of c[i], contains a value from a[] which is greater than b[i] and is closest to b[i].

If a[] has no greater element than b[i], then value of c[i] is -1.

Example:

Input : a[] = [ 3, 7, 6, 8, 1]  
        b[] = [ 2, 4, 3, 6, 9]

Output : c[] = [3, 6, 6, 7, -1]

c[0] is 3, because 3 > 2.

c[1] is 6, because (7 > 4) and(6 > 4). But 6 is closest to 4, hence the anser is 6.

Solution Explanation:

Sort the array a.

For each index of b[i], apply binary search in sorted array a[].

Time Complexity: O(nlog(n))
Space Complexity: O(n)

Code Solution

// CPP to find result from target array
// for closest element
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

void findClosest(int a[], int b[], int n)
{
    // create a vector 
	vector<int> vect(a, a + n);

	// sort the vector.
	sort(vect.begin(), vect.end());

	// upper_bound iterator
	vector<int>::iterator up;

	// to store the result
	vector<int> c;

	
	for (int i = 0; i < n; i++) {

		// get upper bound
		up = upper_bound(vect.begin(), vect.end(), b[i]);

		// if no upper bound, push -1
		if (up == vect.end())
			c.push_back(-1);

		// Else push the element
		else
			c.push_back(*up);
	}

	cout << "Output = ";
	for (auto it = c.begin(); it != c.end(); it++)
		cout << *it << " ";
}

int main()
{
	int a[] = { 3, 7, 6, 8, 1 };
	int b[] = { 2, 4, 3, 6, 9 };
	int n = sizeof(a) / sizeof(a[0]);
	findClosest(a, b, n);
	return 0;
}

Output

Output = 3 6 6 7 -1