Given an array of integers, find the closest greater or same element for every element. If all elements are smaller for an element, then print -1
Examples:
Input : arr[] = {10, 5, 11, 10, 20, 12}
Output : 10 10 12 10 -1 20
Note that there are multiple occurrences of 10, so ceiling of 10 is 10 itself.Input : arr[] = {6, 11, 7, 8, 20, 12}
Output : 7 12 8 11 -1 20
A simple solution is to run two nested loops. We pick an outer element one by one. For every picked element, we traverse remaining array and find closest greater element. Time complexity of this solution is O(n*n)
Algorithm:
- Create a vector to store the result.
- Loop through every element of the array from i = 0 to n-1.
a. Initialize the variable ‘closest’ as INT_MAXLoop through all elements of the array from j = 0 to n-1
i. If i and j are the same, continue to the next iteration of the loop
ii. If arr[j] is greater than or equal to arr[i], update the variable closest with minimum of closest and arr[j]
b. If closest is still INT_MAX, push -1 to the result vector else push closest
3. Return the result vector
4. In the main function:
Create an array of integers arr[] of size n
Initialize n as the size of the array arr[]
Call the closestGreaterOrSame function and store the result in a vector called ‘result’
Loop through the result vector and print the elements
Below is the implementation of the approach:
C++
// C++ program to find the closest greater or same element// for every element#include <bits/stdc++.h>using namespace std;// Function to find closest greater or same element for// every element of arrayvector<int> closestGreaterOrSame(int arr[], int n) { // Vector to store result vector<int> res; // Loop through every element of the array for (int i = 0; i < n; i++) { int closest = INT_MAX; // Loop through all elements to find closest // greater or same element for (int j = 0; j < n; j++) { // if same leave it and continue if(i == j) continue; // If a greater or same element is found, update // the closest variable as minimum if (arr[j] >= arr[i]) { closest = min(closest, arr[j]); } } // If no greater or same element is found, add -1 to the result vector if( closest == INT_MAX) res.push_back(-1); else // push the closest element to res for ith one res.push_back(closest); } // Return the result vector return res;}// Driver codeint main(){ // Sample input int arr[] = { 6, 11, 7, 8, 20, 12 }; int n = sizeof(arr) / sizeof(arr[0]); // Find closest greater or same element for every // element of the array vector<int> result = closestGreaterOrSame(arr, n); // Print the result for (int i = 0; i < result.size(); i++) cout << result[i] << " "; cout << endl; return 0;} |
Java
// Java program to find the closest greater or same element// for every elementimport java.util.*;public class GFG { // Function to find closest greater or same element for // every element of array public static ArrayList<Integer> closestGreaterOrSame(int arr[], int n) { // ArrayList to store result ArrayList<Integer> res = new ArrayList<Integer>(); // Loop through every element of the array for (int i = 0; i < n; i++) { int closest = Integer.MAX_VALUE; // Loop through all elements to find closest // greater or same element for (int j = 0; j < n; j++) { // if same leave it and continue if (i == j) continue; // If a greater or same element is found, // update the closest variable as minimum if (arr[j] >= arr[i]) { closest = Math.min(closest, arr[j]); } } // If no greater or same element is found, add // -1 to the result ArrayList if (closest == Integer.MAX_VALUE) res.add(-1); else // push the closest element to res for ith // one res.add(closest); } // Return the result ArrayList return res; } // Driver code public static void main(String[] args) { // Sample input int arr[] = { 6, 11, 7, 8, 20, 12 }; int n = arr.length; // Find closest greater or same element for every // element of the array ArrayList<Integer> result = closestGreaterOrSame(arr, n); // Print the result for (int i = 0; i < result.size(); i++) System.out.print(result.get(i) + " "); System.out.println(); }} |
Python3
# Function to find closest greater or# same element for every element of arraydef closestGreaterOrSame(arr): n = len(arr) # Array to store the result res = [] # Loop through every element of the array for i in range(n): closest = float('inf') # Loop through all elements to # find closest greater or same element for j in range(n): # if same, skip and continue to the next element if i == j: continue # If a greater or same element is found # update the closest variable as minimum if arr[j] >= arr[i]: closest = min(closest, arr[j]) # If no greater or same element is found # add -1 to the result array if closest == float('inf'): res.append(-1) else: # push the closest element to the result array for the ith element res.append(closest) # Return the result array return res# Sample inputarr = [6, 11, 7, 8, 20, 12]# Find closest greater or# same element for every element of the arrayresult = closestGreaterOrSame(arr)# Print the resultprint(" ".join(map(str, result)))# by phasing17 |
C#
// C# program to find the closest greater or same element// for every elementusing System;using System.Collections.Generic;class GFG { public static List<int> closestGreaterOrSame(int[] arr, int n) { // List to store result List<int> res = new List<int>(); // Loop through every element of the array for (int i = 0; i < n; i++) { int closest = int.MaxValue; // Loop through all elements to find closest // greater or same element for (int j = 0; j < n; j++) { // if same leave it and continue if (i == j) continue; // If a greater or same element is found, // update the closest variable as minimum if (arr[j] >= arr[i]) { closest = Math.Min(closest, arr[j]); } } // If no greater or same element is found, add // -1 to the result List if (closest == int.MaxValue) res.Add(-1); else // push the closest element to res for ith // one res.Add(closest); } // Return the result List return res; } // Driver code public static void Main(string[] args) { // Sample input int[] arr = { 6, 11, 7, 8, 20, 12 }; int n = arr.Length; // Find closest greater or same element for every // element of the array List<int> result = closestGreaterOrSame(arr, n); // Print the result for (int i = 0; i < result.Count; i++) Console.WriteLine(result[i] + " "); Console.WriteLine(); }} |
Javascript
// Function to find closest greater or // same element for every element of arrayfunction closestGreaterOrSame(arr) { const n = arr.length; // Array to store the result const res = []; // Loop through every element of the array for (let i = 0; i < n; i++) { let closest = Infinity; // Loop through all elements to // find closest greater or same element for (let j = 0; j < n; j++) { // if same, skip and continue to the next element if (i === j) continue; // If a greater or same element is found // update the closest variable as minimum if (arr[j] >= arr[i]) { closest = Math.min(closest, arr[j]); } } // If no greater or same element is found // add -1 to the result array if (closest === Infinity) res.push(-1); else // push the closest element to the result array for the ith element res.push(closest); } // Return the result array return res;}// Sample inputconst arr = [6, 11, 7, 8, 20, 12];// Find closest greater or // same element for every element of the arrayconst result = closestGreaterOrSame(arr);// Print the resultconsole.log(result.join(" ")); |
Output
7 12 8 11 -1 20
Time Complexity: O(N*N) as two nested loops are executing. Here, N is size of the input array.
Space Complexity: O(1) as no extra space has been used. Note here res vector space is ignored as it is the resultnt vector.
Another Approach using Hashing:
Solution is to store the answer for each element in a map (say res). And this can be done by using second map (say m) which will store frequency of elements and automatically sort it according to keys. Then traverse map m and find answer to each key and store answer in map res[key].
C++
// C++ implementation to find the closest smaller or same// element for every element.#include <bits/stdc++.h>using namespace std;map<int, int> m; // initialise two mapsmap<int, int> res;void printPrevGreater(int arr[], int n){ for (int i = 0; i < n; i++) { m[arr[i]]++; // Add elements to map to store count } int c = 0; int prev; int f = 0; for (auto i = m.begin(); i != m.end(); i++) { if (f == 1) { res[prev] = i->first;// check if previous element have // no similar element ,store next // element occurring in map in // res[previous_element] f = 0; c++; } if (i->second == 1) { // if current element count is // 1 then its greater value // will be map's next element f = 1; prev = i->first; } else if (i->second > 1) { // if current element count is // greater than 1, it means there are // similar elements res[i->first] = i->first; c++; f = 0; } } if (c < n) { res[prev] = -1; // checks whether the value for the last // element in map m is stores in res or // not. if not set value to -1 as no other // greater element is there. } for (int i = 0; i < n; i++) { // print the elements cout << res[arr[i]] << " "; }}int main(){ int arr[] = { 6, 11, 7, 8, 20, 12 }; int n = sizeof(arr) / sizeof(arr[0]); printPrevGreater(arr, n); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Java implementation to find the closest smaller or same// element for every element.static Map<Integer,Integer> m = new TreeMap<>(); // initialise two mapsstatic Map<Integer,Integer> res = new TreeMap<>();static void printPrevGreater(int arr[], int n){ for (int i = 0; i < n; i++) { if(m.containsKey(arr[i])){ m.put(arr[i], m.get(arr[i])+1); } else m.put(arr[i],1); // Add elements to map to store count } int c = 0; int prev = 0; int f = 0; for (Map.Entry<Integer, Integer>entry : m.entrySet()) { if (f == 1) { res.put(prev,entry.getKey());// check if previous element have // no similar element ,store next // element occurring in map in // res[previous_element] f = 0; c++; } if (entry.getValue() == 1) { // if current element count is // 1 then its greater value // will be map's next element f = 1; prev = entry.getKey(); } else if (entry.getValue() > 1) { // if current element count is // greater than 1, it means there are // similar elements res.put(entry.getKey() , entry.getKey()); c++; f = 0; } } if (c < n) { res.put(prev , -1); // checks whether the value for the last // element in map m is stores in res or // not. if not set value to -1 as no other // greater element is there. } for (int i = 0; i < n; i++) { // print the elements System.out.printf("%d ",res.get(arr[i])); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 6, 11, 7, 8, 20, 12 }; int n = arr.length; printPrevGreater(arr, n);}}// This code is contributed by shinjanpatra |
Python3
# Python3 implementation to find the closest smaller or# same element for every element.m = {}; # initialise two mapsres = {};def printPrevGreater(arr, n): for i in range(n): if arr[i] not in m: m[arr[i]] = 0 m[arr[i]] += 1 # Add elements to map to store count c = 0; f = 0; for i in sorted(m) : if (f == 1) : # check if previous element have # no similar element ,store next # element occurring in map in # res[previous_element] res[prev] = int(i) f = 0; c += 1; if (m[i] == 1): # if current element count is # 1 then its greater value # will be map's next element f = 1; prev = int(i); elif (m[i] > 1): # if current element count is # greater than 1, it means # there are similar elements res[int(i)] = int(i); c += 1 f = 0; if (c < n): res[prev] = -1; # checks whether the value for the last # element in map m is stores in res or # not. if not set value to -1 as no other # greater element is there. for i in range(n): # print the elements print(res[arr[i]], end = " ");# Driver Codearr = [ 6, 11, 7, 8, 20, 12 ];n = len(arr);printPrevGreater(arr, n);# This code is contributed by phasing17 |
C#
// C# implementation to find the closest smaller or same// element for every element.using System;using System.Collections.Generic;class GFG {// initialise two mapsstatic SortedDictionary<int, int> m = new SortedDictionary<int, int>();static SortedDictionary<int, int> res = new SortedDictionary<int, int>();static void printPrevGreater(int[] arr, int n){ for (int i = 0; i < n; i++) { if(m.ContainsKey(arr[i])){ m[arr[i]] += 1; } else m[arr[i]] = 1; // Add elements to map to store count } int c = 0; int prev = 0; int f = 0; foreach (var entry in m) { if (f == 1) { res[prev] = entry.Key;// check if previous element have // no similar element ,store next // element occurring in map in // res[previous_element] f = 0; c++; } if (entry.Value == 1) { // if current element count is // 1 then its greater value // will be map's next element f = 1; prev = entry.Key; } else if (entry.Value > 1) { // if current element count is // greater than 1, it means there are // similar elements res[entry.Key] = entry.Key; c++; f = 0; } } if (c < n) { res[prev] = -1; // checks whether the value for the last // element in map m is stores in res or // not. if not set value to -1 as no other // greater element is there. } for (int i = 0; i < n; i++) { // print the elements Console.Write(res[arr[i]] + " "); }}// Driver Codepublic static void Main(string[] args){ int[] arr = { 6, 11, 7, 8, 20, 12 }; int n = arr.Length; printPrevGreater(arr, n);}}// This code is contributed by phasing17 |
Javascript
// JavaScript implementation to find the closest smaller or// same element for every element.let m = {}; // initialise two mapslet res = {};function printPrevGreater(arr, n){ for (var i = 0; i < n; i++) { if (!m.hasOwnProperty(arr[i])) m[arr[i]] = 0; m[arr[i]]++; // Add elements to map to store count } let c = 0; let prev; let f = 0; for (const i in m) { if (f == 1) { res[prev] = parseInt( i); // check if previous element have // no similar element ,store next // element occurring in map in // res[previous_element] f = 0; c++; } if (m[i] == 1) { // if current element count is // 1 then its greater value // will be map's next element f = 1; prev = parseInt(i); } else if (m[i] > 1) { // if current element count is // greater than 1, it means // there are similar elements res[parseInt(i)] = parseInt(i); c++; f = 0; } } if (c < n) { res[prev] = -1; // checks whether the value for the last // element in map m is stores in res or // not. if not set value to -1 as no other // greater element is there. } for (var i = 0; i < n; i++) { // print the elements process.stdout.write(res[arr[i]] + " "); }}// Driver Codelet arr = [ 6, 11, 7, 8, 20, 12 ];let n = arr.length;printPrevGreater(arr, n);// This code is contributed by phasing17 |
Output
7 12 8 11 -1 20
Time Complexity: O(n log(n)).
Auxiliary Space: O(n)
A better solution is to sort the array and create a sorted copy, then do binary search for floor. We traverse the array, for every element we search for the first greater element. In C++ upper_bound() serves this purpose.
Below is the implementation of the above approach
C++
// C++ implementation of efficient algorithm to find// floor of every element#include <bits/stdc++.h>using namespace std;// Prints greater elements on left side of every elementvoid printPrevGreater(int arr[], int n){ if (n == 1) { cout << "-1"; return; } // Create a sorted copy of arr[] vector<int> v(arr, arr + n); sort(v.begin(), v.end()); // Traverse through arr[] and do binary search for // every element. for (int i = 0; i < n; i++) { // Find the first element that is greater than // the given element auto it = upper_bound(v.begin(), v.end(), arr[i]); // Since arr[i] also exists in array, *(it-1) // will be same as arr[i]. Let us check *(it-2) // is also same as arr[i]. If true, then arr[i] // exists twice in array, so ceiling is same // same as arr[i] if ((it - 1) != v.begin() && *(it - 2) == arr[i]) { // If next element is also same, then there // are multiple occurrences, so print it cout << arr[i] << " "; } else if (it != v.end()) cout << *it << " "; else cout << -1 << " "; }}/* Driver program to test insertion sort */int main(){ int arr[] = {10, 5, 11, 10, 20, 12}; int n = sizeof(arr) / sizeof(arr[0]); printPrevGreater(arr, n); return 0;} |
Java
// Java implementation of efficient algorithm to find// floor of every elementimport java.util.Arrays;class GFG { // Prints greater elements on left side of every element static void printPrevGreater(int arr[], int n) { if (n == 1) { System.out.println("-1"); return; } // Create a sorted copy of arr[] int v[] = Arrays.copyOf(arr, arr.length); Arrays.sort(v); // Traverse through arr[] and do binary search for // every element. for (int i = 0; i < n; i++) { // Find the first element that is greater than // the given element int it = Arrays.binarySearch(v,arr[i]); it++; // Since arr[i] also exists in array, *(it-1) // will be same as arr[i]. Let us check *(it-2) // is also same as arr[i]. If true, then arr[i] // exists twice in array, so ceiling is same // same as arr[i] if ((it - 1) != 0 && v[it - 2] == arr[i]) { // If next element is also same, then there // are multiple occurrences, so print it System.out.print(arr[i] + " "); } else if (it != v.length) System.out.print(v[it] + " "); else System.out.print(-1 + " "); } } // Driver code public static void main(String[] args) { int arr[] = {10, 5, 11, 10, 20, 12}; int n = arr.length; printPrevGreater(arr, n); }}// This code is contributed by// Rajnis09 |
Python3
# Python implementation of efficient algorithm# to find floor of every elementimport bisect# Prints greater elements on left side of every elementdef printPrevGreater(arr, n): if n == 1: print("-1") return # Create a sorted copy of arr[] v = list(arr) v.sort() # Traverse through arr[] and do binary search for # every element for i in range(n): # Find the location of first element that # is greater than the given element it = bisect.bisect_right(v, arr[i]) # Since arr[i] also exists in array, v[it-1] # will be same as arr[i]. Let us check v[it-2] # is also same as arr[i]. If true, then arr[i] # exists twice in array, so ceiling is same # same as arr[i] if (it-1) != 0 and v[it-2] == arr[i]: # If next element is also same, then there # are multiple occurrences, so print it print(arr[i], end=" ") elif it <= n-1: print(v[it], end=" ") else: print(-1, end=" ")# Driver codeif __name__ == "__main__": arr = [10, 5, 11, 10, 20, 12] n = len(arr) printPrevGreater(arr, n)# This code is contributed by # sanjeev2552 |
C#
// C# implementation of efficient algorithm // to find floor of every elementusing System; class GFG { // Prints greater elements on left side // of every element static void printPrevGreater(int []arr, int n) { if (n == 1) { Console.Write("-1"); return; } // Create a sorted copy of arr[] int []v = new int[arr.GetLength(0)]; Array.Copy(arr, v, arr.GetLength(0)); Array.Sort(v); // Traverse through arr[] and // do binary search for every element. for (int i = 0; i < n; i++) { // Find the first element that is // greater than the given element int it = Array.BinarySearch(v, arr[i]); it++; // Since arr[i] also exists in array, *(it-1) // will be same as arr[i]. Let us check *(it-2) // is also same as arr[i]. If true, then arr[i] // exists twice in array, so ceiling is same // same as arr[i] if ((it - 1) != 0 && v[it - 2] == arr[i]) { // If next element is also same, then there // are multiple occurrences, so print it Console.Write(arr[i] + " "); } else if (it != v.Length) Console.Write(v[it] + " "); else Console.Write(-1 + " "); } } // Driver code public static void Main(String[] args) { int []arr = {10, 5, 11, 10, 20, 12}; int n = arr.Length; printPrevGreater(arr, n); }}// This code is contributed by 29AjayKumar |
Javascript
// JavaScript implementation of efficient algorithm to find// floor of every element// Function to implement upper_boundfunction upper_bound(arr, N, X){ let mid; // Initialise starting index and // ending index let low = 0; let high = N; // Till low is less than high while (low < high) { // Find the middle index mid = low + Math.floor((high - low) / 2); // If X is greater than or equal // to arr[mid] then find // in right subarray if (X >= arr[mid]) { low = mid + 1; } // If X is less than arr[mid] // then find in left subarray else { high = mid - 1; } } // if X is greater than arr[n-1] if(low < N && arr[low] <= X) { low++; } // Return the upper_bound index return low;}// Prints greater elements on left side of every elementfunction printPrevGreater(arr, n){ if (n == 1) { process.stdout.write("-1"); return; } // Create a sorted copy of arr[] let v = [...arr]; v.sort(); // Traverse through arr[] and do binary search for // every element. for (var i = 0; i < n; i++) { // Find the first element that is greater than // the given element let it = upper_bound(v, n, arr[i]); // Since arr[i] also exists in array, *(it-1) // will be same as arr[i]. Let us check *(it-2) // is also same as arr[i]. If true, then arr[i] // exists twice in array, so ceiling is same // same as arr[i] if ((it - 1) != 0 && v[it - 2] === arr[i]) { // If next element is also same, then there // are multiple occurrences, so print it process.stdout.write(arr[i] + " "); } else if (it < n) process.stdout.write(v[it] + " "); else process.stdout.write("-1"); }}/* Driver program to test insertion sort */let arr = [10, 5, 11, 10, 20, 12];let n = arr.length;printPrevGreater(arr, n);// This code is contributed by phasing17 |
Output
10 10 12 10 -1 20
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!
