Closest greater element for every array element from another array

0 0 4 minutes read

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 array
void 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 program
int 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 element
import 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 element
 
import bisect
 
# Function for printing resultant array
def 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 code
if __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 element
class 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 element
function closestResult(a, b, n) {
// change a[] to Set
let vect = new Set(a);
// array for result
let c = [];
 
// calculate resultant array
for (let i = 0; i < n; i++) {
// check upper bound element
let up = null;
vect.forEach((elem) => {
if (elem > b[i] && (up == null || elem < up)) {
up = elem;
}
});
// if no element found push -1
if (up == null) c.push(-1);
// Else push the element
else c.push(up); // add to resultant
}
 
console.log("Result =", c.join(" "));
}
 
// Driver Code
let 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 log₂(n))
Auxiliary Space: O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!