Fastest Solution Explaination

#1

Hi,

Can anybody explain the fastest solution explanation and time complexity please.?

#2

Time complexity is less than O(N)

int Solution::solve(vector &arr) {

map<int,int,greater<int>>m;

for(int i=0;i<arr.size();i++){
    m[arr[i]]++;
}


int n = m.size();
vector<int>DP(n+1);
int p=1;
bool flag = false;
for(auto it=m.begin();it!=m.end();it++){
    DP[p] = it->second + DP[p-1];
    if(it->first == DP[p-1]){
        flag = true;
        break;
    }
    p++;
}
if(flag == true){
    return 1;
}
return -1;

}

#3

class Solution:
# @param A : list of integers
# @return an integer
def solve(self, A):
A.sort()
n = len(A)
x=0
for i in range(n - 1):

		if A[i] == A[i + 1]: 
			continue
			
		# In case of duplicates we reach the last element here
		if A[i] == n - i - 1: 
			x+=1 
	
	if A[n - 1] == 0: 
		return(1) 
	if(x!=0):	
	    return x
	else:
	    return -1