C++ Solution with O(n) and O(nlog(n)^2)


  • 0
    Z

    first solution is to do the reverse operation from the end of the day and update the left and right of the flower x. This is O(n)

    class Solution {
    public:
        int kEmptySlots(vector<int>& flowers, int k) {
            int n = flowers.size();
            vector<int> vec;
            for (auto v : flowers) vec.push_back(v);
            sort(vec.begin(), vec.end());
            vector<int> day(n + 1);
            for (int i = 1; i <= flowers.size(); i++) {
                day[flowers[i - 1]] = i;
            }
            int res = n + 1;
            if (k == 0) res = n;
            vector<int> left(n + 1, -1), right(n + 1, -1);
            for (int i = 1; i <= n; i++) {
                if (i > 1) left[i] = i - 1;
                if (i < n) right[i] = i + 1;
            }
    
            for (int i = n - 1; i >= 0; i--) {
                int v = flowers[i];
                if (left[v] != -1 && right[v] != -1) {
                    if (k == right[v] - left[v] - 1) {
                        res = min(res, max(day[right[v]], day[left[v]]));
                    }
                    if (right[v] - v - 1 == k) {
                        res = min(res, i + 1);
                    }
                    
                    if (v - left[v] - 1 == k) {
                        res = min(res, i + 1);
                    }
                }
                if (left[v] != -1) right[left[v]] = right[v];
                if (right[v] != -1) left[right[v]] = left[v];
            }
            if (res == n + 1) res = -1;
            return res;
    
        }
    };
    
    

    second solution is use binary indexed tree and binary search to find the left and right flower, this is O(nlog(n)^2)

    class Solution {
    public:
        int kEmptySlots(vector<int>& flowers, int k) {
            n = flowers.size();
            c.resize(n + 10, 0);
            for (int i = 1; i <= flowers.size(); i++) {
                int v = flowers[i - 1];
                add(v, 1);
                
                int left = getLeft(v);
                int right = getRight(v);
                
                if (left != -1 && v - left - 1 == k) return  i;
                if (right != -1 && right - v - 1== k) return i;
               
            }
            return -1;
        }
    private:
        int n;
        vector<int> c;
        void add(int pos, int val) {
            for (int i = pos; i <= n; i += i & -i) 
                c[i] += val;
        }
        
        int sum(int pos) {
            int res = 0;
            for (int i = pos; i; i -= i & -i) 
                res += c[i];
            return res;
        }
        
        int getLeft(int v) {
            int one = sum(v - 1);
            if (one <= 0) return -1;
            int l = 1, r = v - 1;
            int left;
            while (l <= r) {
                int m = l + r >> 1;
                int t = sum(m);
                if (t < one) l = m + 1;
                else {
                    if (sum(m) - sum(m - 1) == 1) {
                        left = m;
                    }
                    r = m - 1;
                }
            }
            return left;
        }
        
        int getRight(int v) {
            int one = sum(n) - sum(v);
            if (one <= 0) return -1;
            int l = v + 1, r = n;
            int right;
            while (l <= r) {
                int m = l + r >> 1;
                int t = sum(m) - sum(v);
                if (t > 1) r = m - 1;
                else if (t == 0) {
                    l = m + 1;
                } else{
                    if (sum(m) - sum(m - 1) == 1) {
                        right = m;
                    }
                    r = m - 1;
                }
            }
            return right;
        }
    };
    

Log in to reply
 

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