Find earliest time for k empty group

user_1754982 0
Viewed 7180

I was asked this question in an interview recently, I still cannot come up with a solution.

There are N slots in a river. An array P is given where each index denotes the time at which the stone at that position will appear. I have to come up with an algorithm to find the earliest time at which there will be K contiguous empty slots. For E.G.

N = 5

P = [2,5,1,4,3]

K = 2

Initially: [0,0,0,0,0] 

All the slots are empty.

Now at:

Time t = 1, second stone will appear --> [0,1,0,0,0]

Time t = 2, fifth stone will appear --> [0,1,**0,0**,1]

Time t = 3, first stone will appear --> [1,1,0,0,1]

Time t = 4, fourth stone will appear --> [1,1,0,1,1]

Time t = 5, third stone will appear --> [1,1,1,1,1]

So the answer for above case is 2, because at time 2 there are (k = 2) continuous empty slots.

algorithm
4 Answers

Every time you add a stone you're basically dividing a sequence of contiguous empty slots (zeros) in two parts. You can use this idea to construct a binary tree where each node represents an interval (of zeros and ones - stones and empty spaces) and each leaf node represents an interval of zeros only.

To add a stone you find the appropriate leaf node (corresponding interval must include the position for your new stone) and add new leaf nodes - for the intervals on the left and on the right vs the stone you add. At this moment you can check the length of those new intervals and stop if you found one with required length.

The only problem here is that the tree may become unbalanced so to get O(nlogn) worst case you should apply some technics to balance the tree as it grows - red-black tree or something like that - https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

user_71323000

I finally found the O(n) time complexity and O(n) space complexity solution on leetcode. To explain briefly:

The idea is to use an array days[] to record each position flower's blooming day. That means days[i] is the blooming day of the flower in position i+1. We just need to find a subarray days[left, left+1,...,left+k-1, right] which satisfies: for any i = left+1,..., left+k-1, we can have days[left] < days[i] && days[right] < days[i]. Then, the result is max(days[left], days[right]).

Here is the link to the exact solution: https://discuss.leetcode.com/topic/104771/java-c-simple-o-n-solution

user_17549820

Note, in inner loop P items to the right of i position can be safely omitted. However, this is still O(n^2)

    int K = 2;
    int[] P = { 2, 5, 1, 4, 3 };
    int N = P.Length;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (Math.Abs(P[j] - P[i] + 1) == K)
            {
                return i + 1; //+1 because we iterate from 0 | this is the ans (time) 
            }

        }
    }
user_79583070

You could use BIT tree to solve this problem. You want exactly k slots to be empty so let's assume that occurred at the time i.

a=p[i]-k-1;
b=p[i]+k+1;

Array T tells whether stone is at index i or not.

Now all entries between index a and p[i] or b and p[i] in array T should be zero. This can be checked by making use of range queries I prefer BIT tree but segment tree can also be used.

user_74404900
Related