O(n) C++ Bucket Sort Easy To Understand


  • 0
    G

    We form buckets with length of k + 1, and cover all the positions.
    Within each bucket, there cannot be an answer, because the maximum position difference can only be k-1.
    The two flowers must be blooming in adjacent buckets.
    Update max/min flower position of each bucket and check its adjacent bucket.

    class Solution {
    public:
        int kEmptySlots(vector<int>& flowers, int k) {
            int N = flowers.size();
            int n = N / (k+1) + 1;
            vector<vector<int>> bucket(n, {INT_MAX, INT_MIN});
            for(int i = 0; i < N; i ++){
                int f = flowers[i];
                int idx = f/(k+1);
                if(f < bucket[idx][0]){
                    bucket[idx][0] = f;
                    if(idx - 1 >= 0 && (f - bucket[idx-1][1]) == k + 1)
                        return i + 1;
                }
                if(f > bucket[idx][1]){
                    bucket[idx][1] =  f;
                    if(idx + 1 < n && (bucket[idx+1][0] - f == k + 1))
                        return i + 1;
                }
            }
            return -1;
        }
    };
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.