Given an array of integers, find the closest smaller or same element for every element. If all elements are greater for an element, then print -1. We may assume that the array has at least two elements.
Examples:
Input : arr[] = {10, 5, 11, 10, 20, 12}
Output : 10 -1 10 10 12 11
Note that there are multiple occurrences of 10, so floor of 10 is 10 itself.Input : arr[] = {6, 11, 7, 8, 20, 12}
Output : -1 8 6 7 12 11
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_MIN.
b. Loop 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 smaller than or equal to arr[i], update the variable closest with maximum of closest and arr[j]
c. If closest is still INT_MIN, 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 closestSmallerOrSame 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 smaller or same element// for every element#include <bits/stdc++.h>using namespace std;// Function to find closest smaller or same element for// every element of arrayvector<int> closestSmallerOrSame(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_MIN; // Loop through all elements to find closest // smaller or same element for (int j = 0; j < n; j++) { // if same leave it and continue if(i == j) continue; // If a smaller or same element is found, update // the closest variable as maximum if (arr[j] <= arr[i]) { closest = max(closest, arr[j]); } } // If no smaller or same element is found, add -1 to the result vector if( closest == INT_MIN) 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 smaller or same element for every // element of the array vector<int> result = closestSmallerOrSame(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 smaller or same element// for every elementimport java.util.*;public class GFG{ // Function to find closest smaller or same element for // every element of array public static List<Integer> closestSmallerOrSame(int[] arr, int n) { // List to store result List<Integer> res = new ArrayList<>(); // Loop through every element of the array for (int i = 0; i < n; i++) { int closest = Integer.MIN_VALUE; // Loop through all elements to find closest // smaller or same element for (int j = 0; j < n; j++) { // if same leave it and continue if(i == j) continue; // If a smaller or same element is found, update // the closest variable as maximum if (arr[j] <= arr[i]) { closest = Math.max(closest, arr[j]); } } // If no smaller or same element is found, add -1 to the result list if( closest == Integer.MIN_VALUE) 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 smaller or same element for every // element of the array List<Integer> result = closestSmallerOrSame(arr, n); // Print the result for (int i = 0; i < result.size(); i++) System.out.print(result.get(i) + " "); System.out.println(); }} |
Python
def closest_smaller_or_same(arr): n = len(arr) res = [] # Loop through every element of the array for i in range(n): closest = float('-inf') # Loop through all elements to find closest smaller or same element for j in range(n): if i == j: # if same, continue continue # If a smaller or same element is found, update the closest variable if arr[j] <= arr[i]: closest = max(closest, arr[j]) # If no smaller or same element is found, append -1 to the result list if closest == float('-inf'): res.append(-1) else: # append the closest element to res for the current one res.append(closest) # Return the result list return res# Sample inputarr = [6, 11, 7, 8, 20, 12]# Find closest smaller or same element for every element of the arrayresult = closest_smaller_or_same(arr)# Print the resultprint ' '.join(map(str, result)) #This Code Is Contributed By Shubham Tiwari |
C#
using System;using System.Collections.Generic;public class Program { // Function to find the closest smaller or same element // for every element of the array public static List<int> ClosestSmallerOrSame(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.MinValue; // Loop through all elements to find closest // smaller or same element for (int j = 0; j < n; j++) { // if same leave it and continue if (i == j) continue; // If a smaller or same element is found, // update the closest variable as maximum if (arr[j] <= arr[i]) { closest = Math.Max(closest, arr[j]); } } // If no smaller or same element is found, add // -1 to the result list if (closest == int.MinValue) res.Add(-1); else // push the closest element to res for ith // one res.Add(closest); } return res; } // Driver code public static void Main() { int[] arr = { 6, 11, 7, 8, 20, 12 }; int n = arr.Length; // Find closest smaller or same element for every // element of the array List<int> result = ClosestSmallerOrSame(arr, n); foreach(var item in result) { Console.Write(item + " "); } Console.WriteLine(); // This Code Is Contributed By Shubham Tiwari. }} |
Javascript
// Function to find closest smaller or same element for every // element of arrayfunction closestSmallerOrSame(arr) { const n = arr.length; const res = []; // Loop through every element of the array for (let i = 0; i < n; i++) { let closest = Number.MIN_SAFE_INTEGER; // Loop through all elements to find closest smaller or // same element for (let j = 0; j < n; j++) { // If same element, skip and continue to the next element if (i === j) { continue; } // If a smaller or same element is found, update the // closest variable if (arr[j] <= arr[i]) { closest = Math.max(closest, arr[j]); } } // If no smaller or same element is found, add -1 to the // result vector if (closest === Number.MIN_SAFE_INTEGER) { res.push(-1); } else { // Push the closest element to res for the ith element res.push(closest); } } // Return the result vector return res;}// Driver codeconst arr = [6, 11, 7, 8, 20, 12];const result = closestSmallerOrSame(arr);// Print the resultconsole.log(result.join(" ")); |
Output
-1 8 6 7 12 11
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.
A better solution is to sort the array and create a sorted copy, then do a binary search for floor. We traverse the array, for every element we search for the first occurrence of an element that is greater than or equal to given element. Once we find such an element, we check if the next of it is also the same, if yes, then there are multiple occurrences of the element, so we print the same element as output. Otherwise, we print previous element in the sorted array. In C++, lower_bound() returns iterator to the first greater or equal element in a sorted array.
Implementation:
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){ // 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++) { // Floor of first element is -1 if there is only // one occurrence of it. if (arr[i] == v[0]) { (arr[i] == v[1]) ? cout << arr[i] : cout << -1; cout << " "; continue; } // Find the first element that is greater than or // or equal to given element auto it = lower_bound(v.begin(), v.end(), arr[i]); // If next element is also same, then there // are multiple occurrences, so print it if (it != v.end() && *(it + 1) == arr[i]) cout << arr[i] << " "; // Otherwise print previous element else cout << *(it - 1) << " "; }}/* Driver program to test insertion sort */int main(){ int arr[] = { 6, 11, 7, 8, 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.io.*;import java.util.*;class GFG { // Function to count the occurences of a target number. static int count(int[] arr, int target) { int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { count++; } } return count; } // Function to find index of an element static int index(int[] arr, int target) { int index = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return index; } // Prints greater elements on left // side of every element static void printPrevGreater(int[] arr, int n) { // Create a sorted copy of arr int[] v = new int[n]; for (int i = 0; i < n; i++) { v[i] = arr[i]; } Arrays.sort(v); int it = 0; // Traverse through arr[] and do // binary search for every element. for (int i = 0; i < n; i++) { // Floor of first element is -1 if // there is only one occurrence of it. if (arr[i] == v[0]) { System.out.print( ((arr[i] == v[1]) ? arr[i] : -1) + " "); continue; } // Find the first element that is greater // than or or equal to given element if (count(arr, arr[i]) > 0) { it = v[index(v, arr[i])]; } else { it = v[n - 1]; } // If next element is also same, then there // are multiple occurrences, so print it if (it != v[n - 1] && v[index(v, it) + 1] == arr[i]) { System.out.print(arr[i] + " "); } // Otherwise print previous element else { System.out.print(v[index(v, it) - 1] + " "); } } } public 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 lokeshmvs21. |
Python3
# Python3 implementation of efficient # algorithm to find floor of every element # Prints greater elements on left # side of every element def printPrevGreater(arr, n) : # Create a sorted copy of arr v = arr.copy() v.sort() # Traverse through arr[] and do # binary search for every element. for i in range(n) : # Floor of first element is -1 if # there is only one occurrence of it. if (arr[i] == v[0]) : if (arr[i] == v[1]) : print(arr[i], end = " ") else : print(-1, end = " ") continue # Find the first element that is greater # than or or equal to given element if v.count(arr[i]) > 0: it = v[v.index(arr[i])] else : it = v[n - 1] # If next element is also same, then there # are multiple occurrences, so print it if (it != v[n - 1] and v[v.index(it) + 1] == arr[i]) : print(arr[i], end = " ") # Otherwise print previous element else : print(v[v.index(it) - 1], end = " ") # Driver Codeif __name__ == "__main__" : arr = [ 6, 11, 7, 8, 20, 12 ] n = len(arr) printPrevGreater(arr, n) # This code is contributed by Ryuga |
C#
// C# implementation of efficient algorithm to find floor// of every elementusing System;using System.Collections;public class GFG { // Function to count the occurences of a target number. static int count(int[] arr, int target) { int count = 0; for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { count++; } } return count; } // Function to find index of an element static int index(int[] arr, int target) { int index = -1; for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { return i; } } return index; } // Prints greater elements on left // side of every element static void printPrevGreater(int[] arr, int n) { // Create a sorted copy of arr int[] v = new int[n]; for (int i = 0; i < n; i++) { v[i] = arr[i]; } Array.Sort(v); int it = 0; // Traverse through arr[] and do // binary search for every element. for (int i = 0; i < n; i++) { // Floor of first element is -1 if // there is only one occurrence of it. if (arr[i] == v[0]) { Console.Write( ((arr[i] == v[1]) ? arr[i] : -1) + " "); continue; } // Find the first element that is greater // than or equal to given element if (count(arr, arr[i]) > 0) { it = v[index(v, arr[i])]; } else { it = v[n - 1]; } // If next element is also same, then there // are multiple occurrences, so print it if (it != v[n - 1] && v[index(v, it) + 1] == arr[i]) { Console.Write(arr[i] + " "); } // Otherwise print previous element else { Console.Write(v[index(v, it) - 1] + " "); } } } static public void Main() { // Code int[] arr = { 6, 11, 7, 8, 20, 12 }; int n = arr.Length; printPrevGreater(arr, n); }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// JavaScript implementation of efficient algorithm to find// floor of every element// Prints greater elements on left side of every elementfunction printPrevGreater(arr, n){ // Create a sorted copy of arr[] let v = [...arr] v.sort((a, b) => a - b); // Traverse through arr[] and do binary search for // every element. for (let i = 0; i < n; i++) { // Floor of first element is -1 if there is only // one occurrence of it. if (arr[i] == v[0]) { (arr[i] == v[1]) ? document.write(arr[i]) : document.write(-1); document.write(" "); continue; } // Find the first element that is greater than or // or equal to given element if (v.includes(arr[i])) it = v[v.indexOf(arr[i])] else it = v[n - 1] // If next element is also same, then there // are multiple occurrences, so print it if (it != v[n - 1] && (v[v.indexOf(it) + 1] == arr[i])) document.write(arr[i] + " "); // Otherwise print previous element else document.write(v[v.indexOf(it) - 1] + " "); }}function lower_bound(arr, val){ }/* Driver program to test insertion sort */ let arr = [ 6, 11, 7, 8, 20, 12 ]; let n = arr.length; printPrevGreater(arr, n);// This code is contributed by _saurabh_jaiswal</script> |
Output
-1 8 6 7 12 11
Complexity Analysis:
- 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!
