Introduction
Problem:
Given an integer ‘N’ and an array ‘arr[]’ of length ‘N’ consisting of nonnegative integers, find the largest integer ‘K’ for every index ‘i’ such that at least ‘K’ integers are greater than or equal to ‘K’ in the subarray from 0 to ‘i’.
Let’s understand the problem with the help of an example:
Input: N = 5, arr = [ 3, 1, 4, 1, 5 ]
Output: 1 1 2 2 3
Explanation:
 For ‘i’=0, the answer is 1, as only one prefix greater than or equal to one, i.e., 3.
 For ‘i’=1, the answer is 1. Here, there is a total of two prefixes  3 and 1, but we can’t choose ‘K’=2 as there is only one prefix greater than or equal to two. So, the answer is still 1.
 For ‘i’=2, there are a total of three prefixes  3, 1, and 4. If we choose ‘K’=2, there are two prefixes greater than or equal to K. For K=3, there are only two prefixes greater than or equal to K, so the answer can’t be 3.
 For ‘i’=3, there are four prefixes  3,1,4 and 1. For ‘K’=2, there are two prefixes greater than or equal two. So, it is a valid answer. For ‘K’=3, there are only two prefixes greater than or equal to K, so the answer is 2.
 For ‘i’=4, there are a total of five prefixes  3,1,4,1,5. For ‘K’ = 3, there are three prefixes greater than or equal to K. For ‘K’=4, there are only two prefixes greater than or equal to K. So the answer is 3.
Approach
One approach is to iterate over every ‘K’ for every index ‘i’ and check if it is valid or not. A particular ‘K’ is valid if at least ‘K’ prefixes greater than or equal to K. We can check this by simply iterating and maintaining a ‘count’ variable that stores the number of prefixes greater than or equal to K. If the current ‘K’ is valid, we update the answer. Else we break the loop.
C++ Code

Output:
1 1 2 2 3
Time Complexity = O(N ^ 3)
For every index ‘i’ from 0 to ‘N’, we use a nested loop for ‘K’ from 1 to ‘N’ and for ‘j’ from 0 to ‘i’. So the time taken for a single index is O(N^2). Therefore the total time complexity of the approach is O(N^3).
Space Complexity = O(1)
We have just created some variables in our above approach. Therefore the space complexity of our approach is O(1).