Ceiling of every element of array on their right side elements in C++

Problem statement

Given an array of integers, determine the ceiling (the closest element that is greater than or equal to that element) on the elements present on the right side of that element. If there is no such element present on the right side of any element then print “-1”.

Example:

Given array: 100, 100, 200, 1000, 1

ceiling array:100, 200, 1000, -1, -1

explanation: 1 st element = 100 : elements present on the right side of this element : 100, 200, 1000, 1  :ceiling of 100 is 100.

2nd element =100: elements present on the right side of this element:  200, 1000, 1:ceiling of 100 is 200.

3rd element = 200: elements present on the right side of this element: 1000, 1:ceiling of 200 is 1000.

4th element = 1000: Since there is no such element present on the right side of 1000 that is greater than or equal to 1000 so, -1.

The last element = 1, Since no element is present on the right side of 1 so, -1.

Given array: 10, 2, 6, 2

ceiling array: -1, 2, -1, -1

Naive approach:

Make an integer variable, ceil to keep track of Ceiling elements. Iterate through every element in the outer loop and initialize ceil variable to -1, then in the inner loop iterate through all the elements present on the right side of that element and update ceil with the element that is closest to the element in the outer loop.

 c++ code for naive approach

#include<bits/stdc++.h>
using namespace std;
void ceiling(int *a, int n)
{
    int ceil;
    for(int i=0; i<n; ++i)
    {
        ceil=-1;
        int diff=INT_MAX;
        for(int j=i+1; j<n; ++j)
        {
            if(a[j]>=a[i] && diff>a[j]-a[i])
            {
                diff=a[j]-a[i];
                ceil=a[j];
            }
        }
        a[i]=ceil;
    }
}
int main()
{
    int n; 
    cin>>n;
    int a[100000];
    for(int i=0; i<n; ++i)
    {
        cin>>a[i];
    }
    ceiling(a,n);
    for(int i=0; i<5; ++i)
    {
        cout<<a[i]<<' ';
    }
    return 0;
}

Time – complexity: O(n^2)

Space- complexity : O(1)

---

Efficient approach

To solve this problem in linear time complexity, we’ll use a set container available in C++ STL. Iterate array elements from the last index, find the ceiling of that element from elements already present in the set, and then insert that element into the set.

C++ code for efficient approach

#include<bits/stdc++.h>
using namespace std;
void ceiling(int *a, int n)
{
    set<int>s;
    int ceil;
    for(int i=n-1; i>=0; --i)
    {
        ceil=-1;
        set<int>::iterator it = s.lower_bound(a[i]);
        if(it!=s.end())
        {
            ceil=*it;
        }
        s.insert(a[i]);
        a[i]=ceil;
    }
}
int main()
{
    int n; 
    cin>>n;
    int a[100000];
    for(int i=0; i<n; ++i)
    {
        cin>>a[i];
    }
    ceiling(a,n);
    for(int i=0; i<5; ++i)
    {
        cout<<a[i]<<' ';
    }
    return 0;
}

Time – complexity: O(n)

Space- complexity: O(n)

---

If you enjoyed learning this concept then please share your valuable feedback in the comment section. Thank you!