Table of Contents

## Problem Statement

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_greaterandjust_smallerwith some very large and small value respectively.2. Loop through the array as:

- If the array element is greater than
xbut smaller thanjust_greaterthenjust_greater = arr[i]

- If the array element is smaller than
xbut larger thanjust_smallerthenjust_smaller = arr[i]3. Print just greater element if exist for

xelse print“No floor of x found”and print just smaller element if exist forxelse 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.

## Implementation

### 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; }

### Java Program for Find Nearest Greater and Smaller Element

import java.util.Scanner; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); int n = sr.nextInt(); int x = sr.nextInt(); int arr[] = new int[n-1]; for(int i=0;i<n-1;i++) { arr[i] = sr.nextInt(); } int just_greater=10000000,just_smaller=-10000000; for(int i=0; i<n; i++) { //if element is greater than x but smaller than present just_greater if(arr[i] > x && arr[i] < just_greater) just_greater = arr[i]; //if element is Smaller than x but smaller than present just_smaller if(arr[i] < x && just_smaller < arr[i]) just_smaller = arr[i]; } if(just_smaller != -10000000) System.out.println(just_smaller); else System.out.println("No floor of x found"); if(just_greater != 10000000) System.out.println(just_greater); else System.out.println("No Ceil of x found"); } }

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.