Given an array of integers, find the closest greater element for every element. If there is no greater element then print -1
Examples:
Input : arr[] = {10, 5, 11, 10, 20, 12}
Output : 10 10 12 12 -1 -1Input : arr[] = {50, 20, 200, 100, 30}
Output : 100 30 -1 -1 -1
A simple solution is to run two nested loops. We pick an outer element one by one. For every picked element, we traverse the right side array and find the closest greater or equal element. Time complexity of this solution is O(n*n)
A better solution is to use sorting. We sort all elements, then for every element, traverse toward the right until we find a greater element (Note that there can be multiple occurrences of an element).
An efficient solution is to use Self Balancing BST (Implemented as set in C++ and TreeSet in Java). In a Self Balancing BST, we can do both insert and ceiling operations in O(Log n) time.
Implementation:
C++
// C++ program to find ceiling on right side for// every element.#include <bits/stdc++.h>using namespace std;void closestGreater(int arr[], int n){ set<int> s; vector<int> ceilings; // Find smallest greater or equal element // for every array element for (int i = n - 1; i >= 0; i--) { auto greater = s.lower_bound(arr[i]); if (greater == s.end()) ceilings.push_back(-1); else ceilings.push_back(*greater); s.insert(arr[i]); } for (int i = n - 1; i >= 0; i--) cout << ceilings[i] << " ";}int main(){ int arr[] = { 50, 20, 200, 100, 30 }; closestGreater(arr, 5); return 0;} |
Java
// Java program to find ceiling on right side for// every element.import java.util.*;class TreeSetDemo { public static void closestGreater(int[] arr) { int n = arr.length; TreeSet<Integer> ts = new TreeSet<Integer>(); ArrayList<Integer> ceilings = new ArrayList<Integer>(n); // Find smallest greater or equal element // for every array element for (int i = n - 1; i >= 0; i--) { Integer greater = ts.ceiling(arr[i]); if (greater == null) ceilings.add(-1); else ceilings.add(greater); ts.add(arr[i]); } for (int i = n - 1; i >= 0; i--) System.out.print(ceilings.get(i) + " "); } public static void main(String[] args) { int[] arr = { 50, 20, 200, 100, 30 }; closestGreater(arr); }} |
Python3
# Python program to find ceiling on right side for# every element.import bisectdef closestGreater(arr, n): s = [] ceilings = [] # Find smallest greater or equal element # for every array element for i in range(n - 1, -1, -1): greater = bisect.bisect_left(s, arr[i]) if greater == len(s): ceilings.append(-1) else: ceilings.append(s[greater]) s.insert(greater, arr[i]) for i in range(n - 1, -1, -1): print(ceilings[i], end=" ")arr = [50, 20, 200, 100, 30]closestGreater(arr, 5)# This code is contributed by codebraxnzt |
C#
// C# program to find ceiling on right side for// every element.using System;using System.Collections.Generic;public class TreeSetDemo { public static void closestGreater(int[] arr) { int n = arr.Length; SortedSet<int> ts = new SortedSet<int>(); List<int> ceilings = new List<int>(n); // Find smallest greater or equal element // for every array element for (int i = n - 1; i >= 0; i--) { int greater = lower_bound(ts, arr[i]); if (greater == -1) ceilings.Add(-1); else ceilings.Add(greater); ts.Add(arr[i]); } ceilings.Sort((a,b)=>a-b); for (int i = n - 1; i >= 0; i--) Console.Write(ceilings[i] + " "); } public static int lower_bound(SortedSet<int> s, int val) { List<int> temp = new List<int>(); temp.AddRange(s); temp.Sort(); temp.Reverse(); if (temp.IndexOf(val) + 1 == temp.Count) return -1; else if(temp[temp.IndexOf(val) +1]>val) return -1; else return temp[temp.IndexOf(val) +1]; } public static void Main(String[] args) { int[] arr = { 50, 20, 200, 100, 30 }; closestGreater(arr); }}// This code is contributed by Rajput-Ji |
Javascript
// JavaScript code for the above approachfunction closestGreater(arr, n) { let s = []; let ceilings = []; // Find smallest greater or equal element // for every array element for (let i = n - 1; i >= 0; i--) { let greater = bisect_left(s, arr[i]); if (greater == s.length) { ceilings.push(-1); } else { ceilings.push(s[greater]); } s.splice(greater, 0, arr[i]); } let temp = []; for (let i = n - 1; i >= 0; i--) { temp.push(ceilings[i]); } console.log(temp.join(" "));}function bisect_left(s, x) { let lo = 0; let hi = s.length; while (lo < hi) { let mid = Math.floor((lo + hi) / 2); if (s[mid] < x) { lo = mid + 1; } else { hi = mid; } } return lo;}let arr = [50, 20, 200, 100, 30];closestGreater(arr, 5);// This code is contributed by Prince Kumar |
Output
100 30 -1 -1 -1
Time Complexity: O(n Log 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!
