Given an array arr[] of size N, the task is for each array element is to find the nearest non-equal value present on its left in the array. If no such element is found, then print -1
Examples:
Input: arr[] = { 2, 1, 5, 8, 3 }
Output: -1 2 2 5 2
Explanation:
[2], it is the only number in this prefix. Hence, answer is -1.
[2, 1], the closest number to 1 is 2
[2, 1, 5], the closest number to 5 is 2
[2, 1, 5, 8], the closest number to 8 is 5
[2, 1, 5, 8, 3], the closest number to 3 is 2Input: arr[] = {3, 3, 2, 4, 6, 5, 5, 1}
Output: -1 -1 3 3 4 4 4 2
Explanation:
[3], it is the only number in this prefix. Hence, answer is -1.
[3, 3], it is the only number in this prefix. Hence, answer is -1
[3, 3, 2], the closest number to 2 is 3
[3, 3, 2, 4], the closest number to 4 is 3
[3, 3, 2, 4, 6], the closest number to 6 is 4
[3, 3, 2, 4, 6, 5], the closest number to 5 is 4
[3, 3, 2, 4, 6, 5, 5], the closest number to 5 is 4
[3, 3, 2, 4, 6, 5, 5, 1], the closest number to 1 is 2
Naive Approach: The simplest idea is to traverse the given array and for every ith element, find the closest element on the left side of index i which is not equal to arr[i].
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Efficient Approach:
The idea is to insert the elements of the given array in a Set such that the inserted numbers are sorted and then for an integer, find its position and compare its next value with the previous value, and print the closer value out of the two.
Follow the steps below to solve the problem:
- Initialize a Set of integers S to store the elements in sorted order.
- Traverse the array arr[] using the variable i.
- Now, find the nearest value smaller as well as greater than arr[i], say X and Y respectively.
- If X cannot be found, print Y.
- If Y cannot be found, print Z.
- If both X and Y cannot be found, print “-1”.
- After that, add arr[i] to the Set S and print X if abs(X – arr[i]) is smaller than abs(Y – arr[i]). Otherwise, print Y.
- Repeat the above steps for every element.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the closest number on// the left side of xvoid printClosest(set<int>& streamNumbers, int x){ // Insert the value in set and store // its position auto it = streamNumbers.insert(x).first; // If x is the smallest element in set if (it == streamNumbers.begin()) { // If count of elements in the set // equal to 1 if (next(it) == streamNumbers.end()) { cout << "-1 "; return; } // Otherwise, print its // immediate greater element int rightVal = *next(it); cout << rightVal << " "; return; } // Store its immediate smaller element int leftVal = *prev(it); // If immediate greater element does not // exists print it's immediate // smaller element if (next(it) == streamNumbers.end()) { cout << leftVal << " "; return; } // Store the immediate // greater element int rightVal = *next(it); // Print the closest number if (x - leftVal <= rightVal - x) cout << leftVal << " "; else cout << rightVal << " ";}// Driver Codeint main(){ // Given array vector<int> arr = { 3, 3, 2, 4, 6, 5, 5, 1 }; // Initialize set set<int> streamNumbers; // Print Answer for (int i = 0; i < arr.size(); i++) { // Function Call printClosest(streamNumbers, arr[i]); } return 0;} |
Java
import java.util.*;class Main { // Function to find the closest number on // the left side of x static void printClosest(SortedSet<Integer> streamNumbers, int x) { streamNumbers.add(x); int rightVal, leftVal; // Insert the value in set and store // its position List<Integer> it = new ArrayList<>(streamNumbers); it.sort(null); int i = it.indexOf(x); // If x is the smallest element in set if (it.get(i) == it.get(0)) { // If count of elements in the set // equal to 1 if (it.size() == 1) { System.out.print("-1 "); return; } // Otherwise, print its // immediate greater element rightVal = it.get(i + 1); System.out.print(rightVal + " "); return; } // Store its immediate smaller element leftVal = it.get(i - 1); // If immediate greater element does not // exists print it's immediate // smaller element if (i + 1 == it.size()) { System.out.print(leftVal + " "); return; } // Store the immediate // greater element rightVal = it.get(i + 1); // Print the closest number if (x - leftVal <= rightVal - x) System.out.print(leftVal + " "); else System.out.print(rightVal + " "); } // Driver Code public static void main(String[] args) { // Given array int[] arr = {3, 3, 2, 4, 6, 5, 5, 1}; // Initialize set SortedSet<Integer> streamNumbers = new TreeSet<>(); // Print Answer for (int i = 0; i < arr.length; i++) { // Function Call printClosest(streamNumbers, arr[i]); } }} |
Python3
# Python3 program for the above approach# Function to find the closest number on# the left side of xdef printClosest(streamNumbers, x): streamNumbers.add(x); # Insert the value in set and store # its position it =sorted(streamNumbers) i = it.index(x); # If x is the smallest element in set if (it[i] == it[0]): # If count of elements in the set # equal to 1 if ( len(it) == 1): print("-1", end = " "); return; # Otherwise, print its # immediate greater element rightVal = it[i + 1] print(rightVal, end = " "); return; # Store its immediate smaller element leftVal = it[i - 1] # If immediate greater element does not # exists print it's immediate # smaller element if (i + 1 == len(it) ): print(leftVal, end = " "); return; # Store the immediate # greater element rightVal = it[i + 1]; # Print the closest number if (x - leftVal <= rightVal - x): print(leftVal, end = " "); else: print(rightVal, end = " ");# Driver Code# Given arrayarr = [ 3, 3, 2, 4, 6, 5, 5, 1 ];# Initialize setstreamNumbers = set()# Print Answerfor i in range(len(arr)): # Function Call printClosest(streamNumbers, arr[i]);# This code is contributed by phasing17. |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG{ // Function to find the closest number on // the left side of x static void printClosest(SortedSet<int> streamNumbers, int x) { streamNumbers.Add(x); int rightVal, leftVal; // Insert the value in set and store // its position var it = streamNumbers.ToList(); it.Sort(); var i = it.IndexOf(x); // If x is the smallest element in set if (it[i] == it[0]) { // If count of elements in the set // equal to 1 if ( it.Count == 1) { Console.Write("-1 "); return; } // Otherwise, print its // immediate greater element rightVal = it[i + 1]; Console.Write(rightVal + " "); return; } // Store its immediate smaller element leftVal = it[i - 1]; // If immediate greater element does not // exists print it's immediate // smaller element if (i + 1 == it.Count ) { Console.Write(leftVal + " "); return; } // Store the immediate // greater element rightVal = it[i + 1]; // Print the closest number if (x - leftVal <= rightVal - x) Console.Write(leftVal + " "); else Console.Write(rightVal + " "); } // Driver Code public static void Main(string[] args) { // Given array int[] arr = { 3, 3, 2, 4, 6, 5, 5, 1 }; // Initialize set var streamNumbers = new SortedSet<int>(); // Print Answer for (var i = 0; i < arr.Length; i++) { // Function Call printClosest(streamNumbers, arr[i]); } }}// This code is contributed by phasing17. |
Javascript
// JS program for the above approach// Function to find the closest number on// the left side of xfunction printClosest(streamNumbers, x){ streamNumbers.add(x); // Insert the value in set and store // its position let it = Array.from(streamNumbers) it.sort(function(a, b) {return a - b}) let i = it.indexOf(x); // If x is the smallest element in set if (it[i] == it[0]) { // If count of elements in the set // equal to 1 if ( it.length == 1) { process.stdout.write("-1 "); return; } // Otherwise, print its // immediate greater element let rightVal = it[i + 1] process.stdout.write(rightVal + " "); return; } // Store its immediate smaller element let leftVal = it[i - 1] // If immediate greater element does not // exists print it's immediate // smaller element if (i + 1 == it.length ) { process.stdout.write(leftVal + " "); return; } // Store the immediate // greater element let rightVal = it[i + 1]; // Print the closest number if (x - leftVal <= rightVal - x) process.stdout.write(leftVal + " "); else process.stdout.write(rightVal + " ");}// Driver Code// Given arraylet arr = [ 3, 3, 2, 4, 6, 5, 5, 1 ];// Initialize setlet streamNumbers = new Set();// Print Answerfor (var i = 0; i < arr.length; i++) { // Function Call printClosest(streamNumbers, arr[i]);}// This code is contributed by phasing17. |
Output
-1 -1 3 3 4 4 4 2
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!
