Daily Dose of DSA - Day 2

#include<bits/stdc++.h>
using namespace std;

/*Naive method - First we will traverse every element of the array
then for each element we will traverse right of it and search for the
next greater element */

void printceiling(int arr[], int n)
{
    for (int i = 0; i < n; i++) // traverse the array elements
    {
        int diff = INT_MAX;    // def the max diff to use min function
        for (int j = i + 1; j < n; j++)  //right traversal
            if (arr[j] >= arr[i])
                diff = min(diff, arr[j] - arr[i]); //update the diff
       if (diff == INT_MAX)             // no ceiling found
            cout << -1 << " ";

      else
            cout << (arr[i] + diff) << " "; // print the ceiling
    }
}

/*efficient solution -  First we are going to traverse the array from
right side , then we are going to input the elements
into a set , meanwhile for every element present in the set we are going to return the
lower bound of the array element while traversing
*/

void printceilingright(int arr[], int n)
{
    set<int> s;                      // using a tree set
    int res[n];                      // using extra array
    for (int i = n - 1; i >= 0; i--) // traversing the array from right side
    {
        auto it = s.lower_bound(arr[i]); /* O(logn) time
for every element we call the lower bound function ,
it gives you the iterator to the first element which is greater than equal to the element*/
        if (it == s.end())              
            res[i] = -1;             // no ceiling
        else
            res[i] = *it; // for getting the value from the iterator
        s.insert(arr[i]); // inseting elements into the set O(logn) time
    }
    for (int i = 0; i < n; i++)
        cout << res[i] << " ";      // print the res
}
int main()
{
    int arr[] = {100, 50, 30, 60, 55, 32}, n = 6;
    printceilingright(arr, n); //tree set method O(nlogn) time complexity
    cout << endl;
    printceiling(arr, n); //naive method θ(n²) time complexity
}