Searching: Given two arrays, generate third array with the given constraints

Problem Statement:

You are given 2 arrays a and b.

You need to create a new array c, such that c[i], has the value from a[] which is greater than and is closest to b[i].

If there is no such element, then the value of c[i] is -1.

Example:

Input:

a[] = [3, 7, 6, 8, 0]
b[] = [2, 4, 3, 6, 9]

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

c[0] = 3 
c[1] = 6 not 7 because, 6 is greater than 4 and is closest
c[2] = 6
c[3] = 8
c[4] = -1. Because, there is no greater element

Solution Explanation:

Solution is very simple.

Sort the array a[].

And for each b[i], we apply binary search on the sorted array[].

We will use upper bound to get the closest greater element.

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

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


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

    sort(vect.begin(), vect.end());

    vector<int>::iterator up;

    vector<int> res;

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

        up = upper_bound(vect.begin(), vect.end(), b[i]);

        if (up == vect.end())
            res.push_back(-1);
        else
            res.push_back(*up);
    }

    cout << "Result = ";
    for (auto iter = res.begin(); iter != res.end(); iter++)
        cout << *iter << " ";
}

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

Output

Result = 3 6 6 7 -1