Logic is Right, but TLE :(


#1
int Solution::solve(vector<int> &A) {
    int N = A.size(), flag = 0;
    if (N == 0) return -1;
    sort(A.begin(),A.end());
    if(A[N-1]==0) return 1; //0000
    int i = 0,j = 0;
    for(i = 0; i<N; i++){
        int count = 0;
        for(j = i+1; j<N;j++){
            if(A[j]>A[i]) count++;
        }
        if(count == A[i]) {
            flag = 1;
            break;
        }
    }
    if(flag == 1) return 1;
    else return -1;
    
    
}

Obvio its like this cuz I’m using nested loops…but I got partial marks for the right solution. Now how to improve this?


#2

int Solution::solve(vector &A) {
sort(A.begin(),A.end());
if(A[A.size()-1]==0)
return 1;
int i=A.size()-2;
int cnt=1;
while(i>=0)
{

 if(A[i]==A[i+1])
  {i--;
  cnt++;}
  else
  {
      if(A[i]==cnt)
      {
          return 1;
      }
      else{
           cnt++;
           i--;
          }
  }

}
return -1;

}

hope my solution can help you-------------------


#3

Nice one! After that comment, I made a better implementation :slight_smile:

int Solution::solve(vector<int> &A) {
        int N = A.size(), flag = 0;
        if (N == 0) return -1;
        sort(A.begin(),A.end());
        if(A[N-1]==0) return 1; //0000
        int i = 0,j = 0;
        for(i = 0; i<N-1; i++){
            if(A[i]==N-1-i && A[i]!=A[i+1]) return 1;
                      
        }
        // if(flag == 1) return 1;
         return -1;
        
        
    }

#4

Why should we need to add A[i]!=A[i+1] here in if case?


#5

Strictly greater only should be considered. That’s why I did it like that :slight_smile:


#6

Hi, this question is fairly simple but the only trick is to handle duplicates.

    def solve(self, A):
        """
            1. Number of elements > current element == element, return element
            2. if not return -1
            
            Intuition:-
            
            1. Sort array.
            2. Check end - curr_pos == element
            
            [1,2,3,3]
            [1,3,3,3,3]
        """
        A.sort()
        
        start = 0
        
        while start < len((A)):
            while start < len(A) - 1 and A[start] == A[start  + 1]:
                start += 1
            
            element = A[start]
            if element == len(A) - 1 - start:
                return 1
            
            start += 1
        
        return -1

#7

Thanks for sharing :slight_smile: