Home » Technical Interview Questions » Array Interview Questions » Find Nearest Greater and Smaller Element

Find Nearest Greater and Smaller Element


Reading Time - 2 mins

In find the nearest greater and smaller element problem, we have given an unsorted array, you have to find two numbers from an array that are just smaller than a number X and just greater than a number X.

The Floor denotes the nearest smaller element and Ceil denotes the nearest greater element.

Input Format

First-line containing two integer values N and X.

Second-line containing an array of size N.

Output Format

Print two integers in two lines where the first integer denotes the nearest greater element and the second integer denotes the nearest smaller element. If there is no number greater than X then print “No floor of x found” in the position of the first integer. If there is no number smaller than X then print “No ceil of x found” in the position of the second integer.

Constraints

  • 1<=N<=100000
  • -1e9<=X<=1e9
  • -1e9<=a[i]<=1e9 where a[i] denotes the element of the given array.

Algorithm for Find Nearest Greater and Smaller Element

1. Initialize two variables just_greater and just_smaller with some very large and small value respectively.

2. Loop through the array as:

  • If the array element is greater than x but smaller than just_greater then just_greater = arr[i]
  • If the array element is smaller than x but larger than just_smaller then just_smaller = arr[i]

3. Print just greater element if exist for x else print “No floor of x found” and print just smaller element if exist for x else print “No ceil of x found”.

Note: It is simply the modification of finding the second minimum and maximum in an array with a variation of having a reference number with respect to which it is found.

READ  Degree of an array

C++ Program for Find Nearest Greater and Smaller Element

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,x;
  cin>>n>>x;
  long long int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int just_greater=INT_MAX,just_smaller=INT_MIN;
  for(int i=0; i<n; i++)
  {
    //if element is greater than x but smaller than present just_greater
    if(arr[i] > x and arr[i] < just_greater)
      just_greater = arr[i];
      
    //if element is Smaller than x but smaller than present just_smaller
    if(arr[i] < x and just_smaller < arr[i])
      just_smaller = arr[i];
  }   
  if(just_smaller !=INT_MIN)
    cout<<just_smaller<<endl;
  else
    cout<<"No floor of x found\n";
  if(just_greater != INT_MAX)
    cout<<just_greater<<endl;
  else
    cout<<"No Ceil of x found\n";
  return 0;
}
8 0
-3 -4 10 0 3 -2 15 3
-2
3

Complexity Analysis for Find Nearest Greater and Smaller Element

Time Complexity

O(N) where N is the size of the given array. We just traverse the whole array and store the nearest smaller and greater element of X.

Space Complexity

O(1) here we simply use the minimum and maximum conditions wisely.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions