30 Days of Code [Day 15]

28 Aug 2021

QUESTION : 215. Kth Largest Element in an Array

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        map<int, int> m1,m2;
        int c = 0, mx = INT_MIN;
        fv(nums){
            if(it < 0) m2[abs(it)]++;
            else m1[it]++;
            mx = max(mx, it);
        }
        for(int i=mx; i >= 0; --i){
            if(m1[i] >= 1){
                c += m1[i];
                if(c >= k) return i;
            }
        }
        fo(i,1,m2.size()){
            if(m2[i] > 0){
                c += m2[i];
                if(c >= k) return -1*i;
            }
        }
        return -1;
    }
};