Start from day = n, and find the last day satisfying the condition. O(n)


  • 0
    Y

    Disclaimer: this solution is not AC, but based on the problem's description, I think it should be. I might be wrong. please please comment if you think otherwise.
    Nevertheless, I hope this solution provides a different thinking process at least.

    Based on the description,
    "Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming. ",
    My understanding is that any day satisfying this should be fine.

    Here is the algorithm. Declare three vectors of size n, "space", "left" and "right".
    "space" is the number of non-blossomed flowers consecutive to i and including i. Initially, at day=n, all space are 0 as all flowers are blossomed.

    "left" and "right' tracks the leftmost blossomed and rightmost blossomed flowers. Initially, at day=n, left and right are just the neighbors of i, which are i-1 and i+1 respectively.

    At each day (iterating "flowers" backward), we let that flower "wither", and free a space. Note that, this freed space might connect the adjacent spaces as well, and make a larger space. If so, we need to update the "left" of the right flower and the "right" of the left flower. Once we find a space that is "k", we are done.

    Given the following test case (where k=1):
    [3,9,2,8,1,6,10,5,4,7]
    1

    This solution will find the 9th day, as it is the last time a 1-space exists.
    However, the forward solution will find the 6th day, as it is the first time a 1-space is created.

    Here is the code:

    class Solution {
      public:
        int kEmptySlots(vector<int>& flowers, int k) {
          int n = flowers.size();
          if( n <= 1 || k >= n-1 ) return -1;
          vi space(n,0), left(n,-1), right(n,n);
          forall(i,1,n){ left[i] = i-1; }
          forall(i,0,n-1){ right[i] = i+1; }
          for( int i = n; i > 0; --i ){
            int pos = flowers[i-1] -1;
            if( pos > 0 && pos < n-1 ){
              space[pos] = 1 + space[pos-1] + space[pos+1];
              if( space[pos-1] != 0 ){
                left[pos] = left[pos-1];
                space[left[pos]+1] = space[pos];
              }
              if( space[pos+1] != 0 ){
                right[pos] = right[pos+1];
                space[right[pos]-1] = space[pos];
              }
              if( space[pos] == k && left[pos] != -1 && right[pos] != n ){
                return i-1;
              }
            }else if( pos == 0 ){
              space[pos] = 1 + space[pos+1];
              right[pos] = right[pos+1];
              space[right[pos]-1] = space[pos];
            }else if( pos == n-1 ){
              space[pos] = 1 + space[pos-1];
              left[pos] = left[pos-1];
              space[left[pos]+1] = space[pos];
            }
          }
          return -1;
        }
    };
    

Log in to reply
 

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