CODEWITHSUNDEEP
javaarraystreesetsliding-window
remif
remif

Reputation: 33

Consecutive group with size K in an array

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

Question: There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array named flowers consist of numbers from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Given K, find the last day on which there is at least one group of bloomed flowers of size K. Return -1 if no such day is found

Example :
array : [3,1,5,4,2] ; k = 1
day1 ：0 0 1 0 0
day2 ：1 0 1 0 0
day3 ：1 0 1 0 1
day4 ：1 0 1 1 1 >>> Last day on which you can see a group of size k=1
day5 ：1 1 1 1 1

The answer is day 4 (flower: 1).

If k = 2 or 4
The answer is -1.

If k = 3
The answer is day 4 (flowers : 3,4,5).

If k = 5
The answer is day 5 (flowers : 1,2,3,4,5).

Edit 1:
I was able to solve it in O(n^2). But the interviewer was expecting O(nlogn) complexity

For those who use leetcode, this is a variation of the following question : https://leetcode.com/problems/k-empty-slots/description/ (can only access with leetcode paid subscription)

Thanks!!

Upvotes: 1

Views: 867

Answers (1)

Ian Mc
Ian Mc

Reputation: 5829

This problem can be solved in O(nlogn) by implementing Union-Find (with Union by Rank and path compression).

Initially (at day=0), each flower slot represents a distinct set of size=0. There will be N such sets at this time.
The variable k-sets represents how many sets have a size of exactly k. This is initialized to zero. The variable answer represents the last iteration (day) which has at least one set of size k; and is initialized to -1;

Processing the array (N iterations): When a flower blooms, the following events occur at slot index:

  1. The size of the set at position index now has a size of 1. If k==1 then k-sets increases by 1
  2. Union Right (set at index+1): If you are not at position N (i.e. you can't union right at the boundary position N) then call UNION(index, index+1). The union will only occur if the set size at index+1 is greater than zero.
  3. Union Left (set at index-1): If you are not at position 0, then call UNION(index, index-1). Again, a union only occurs if the left set is not empty.
  4. If k-sets > 0, then answer = day (i.e. where day is the n-th iteration of the array)

When a union occurs (call them A and B), three updates concerning k-sets must be done:

  1. If the size of A is k, then k-sets--
  2. If the size of B is k, then k-sets--
  3. If the size of the union of A, B is k, then k-sets++

At the end of the iteration, print answer

Runtime: There are N days, and the cost of each day is linear with O(logn), so the run time is O(NlogN)

Proof of O(logn) time of Union-Find

Upvotes: 1

Related Questions