Given two arrays a[] and b[], we need to build an array c[] such that every element c[i] of c[] 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. All arrays are of same size.
Examples:
Input : a[] = [ 2, 6, 5, 7, 0]
b[] = [1, 3, 2, 5, 8]
Output : c[] = [2, 5, 5, 7, -1]
Input : a[] = [ 2, 6, 5, 7, 0]
b[] = [0, 2, 3, 5, 1]
Output : c[] = [2, 5, 5, 6, 2]
Naive Approach : For each element in b[], we traverse the whole of a[] and try to find the closest greater element, and save the result for each search. This will cost time complexity of O(n^2).
Efficient Approach : Sort the array a[], and for each b[i], apply binary search in sorted array a[]. For this method our time complexity will be O(nlogn).
Note: For closest greater element we can use upper_bound().
Below is the implementation.
C++
// CPP to find result from target array// for closest element#include <bits/stdc++.h>using namespace std;// Function for printing resultant arrayvoid closestResult(int a[], int b[], int n){ // change arr[] to vector vector<int> vect(a, a + n); // sort vector for ease sort(vect.begin(), vect.end()); // iterator for upper_bound vector<int>::iterator up; // vector for result vector<int> c; // calculate resultant array for (int i = 0; i < n; i++) { // check upper bound element up = upper_bound(vect.begin(), vect.end(), b[i]); // if no element found push -1 if (up == vect.end()) c.push_back(-1); // Else push the element else c.push_back(*up); // add to resultant } cout << "Result = "; for (auto it = c.begin(); it != c.end(); it++) cout << *it << " ";}// driver programint main(){ int a[] = { 2, 5, 6, 1, 8, 9 }; int b[] = { 2, 1, 0, 5, 4, 9 }; int n = sizeof(a) / sizeof(a[0]); closestResult(a, b, n); return 0;} |
Java
// Java to find result from target array // for closest elementimport java.util.*;class GFG { // Function for printing resultant array static void closestResult(Integer[] a, int[] b, int n) { // change arr[] to Set TreeSet<Integer> vect = new TreeSet<>(Arrays.asList(a)); // vector for result Vector<Integer> c = new Vector<>(); // calculate resultant array for (int i = 0; i < n; i++) { // check upper bound element Integer up = vect.higher(b[i]); // if no element found push -1 if (up == null) c.add(-1); // Else push the element else c.add(up); // add to resultant } System.out.print("Result = "); for (int i : c) System.out.print(i + " "); } // Driver Code public static void main(String[] args) { Integer[] a = { 2, 5, 6, 1, 8, 9 }; int[] b = { 2, 1, 0, 5, 4, 9 }; int n = a.length; closestResult(a, b, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Python implementation to find result# from target array for closest elementimport bisect# Function for printing resultant arraydef closestResult(a, b, n): # sort list for ease a.sort() # list for result c = [] # calculate resultant array for i in range(n): # check location of upper bound element up = bisect.bisect_right(a, b[i]) # if no element found push -1 if up == n: c.append(-1) # else push the element else: c.append(a[up]) # add to resultant print("Result = ", end = "") for i in c: print(i, end = " ")# Driver codeif __name__ == "__main__": a = [2,5,6,1,8,9] b = [2,1,0,5,4,9] n = len(a) closestResult(a, b, n)# This code is contributed by# sanjeev2552 |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# to find result from target array// for closest elementclass HelloWorld { // Function for printing resultant array public static void closestResult(int[] a, int[] b, int n) { HashSet<int> vect = new HashSet<int>(); for(int i = 0; i < n; i++){ vect.Add(a[i]); } // array for result List<int> c = new List<int>(); // calculate resultant array for (int i = 0; i < n; i++) { // check upper bound element int up = -1; foreach(int elem in vect){ if(elem > b[i] && (up == -1 || elem < up)){ up = elem; } } // if no element found push -1 if (up == -1) c.Add(-1); // Else push the element else c.Add(up); // add to resultant } Console.Write("Result = "); foreach(var i in c){ Console.Write(i + " "); } } static void Main() { int[] a = { 2, 5, 6, 1, 8, 9 }; int[] b = { 2, 1, 0, 5, 4, 9 }; int n = a.Length; closestResult(a, b, n); }}// The code is contributed by Nidhi goel. |
Javascript
// JavaScript to find result from target array// for closest elementfunction closestResult(a, b, n) {// change a[] to Setlet vect = new Set(a);// array for resultlet c = [];// calculate resultant arrayfor (let i = 0; i < n; i++) {// check upper bound elementlet up = null;vect.forEach((elem) => {if (elem > b[i] && (up == null || elem < up)) {up = elem;}});// if no element found push -1if (up == null) c.push(-1);// Else push the elementelse c.push(up); // add to resultant}console.log("Result =", c.join(" "));}// Driver Codelet a = [2, 5, 6, 1, 8, 9];let b = [2, 1, 0, 5, 4, 9];let n = a.length;closestResult(a, b, n); |
Output:
Result = 5 2 1 6 5 -1
Time Complexity: O(n log2(n))
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
