K Empty Slots

Given N flowers. One flower blooms per day. Array flowers[i] gives the flower position (1-based) blooms at i + 1th day. Find the first day where there are k not bloomed flowers between two flowers already bloomed.

[Optimal]Two Pointers/Sliding Window Solution

Put in another word, we need to find two flowers such that all the k flowers in between bloom in a later day.

The idea is to build another array days where days[i] represents which day (1-based) a flower at position i + 1 bloom. Therefore, we can initialize a window [0, k + 1]. While we iterating the days, as long as days[i] is greater than days[left] and days[right], meaning it blooms after two boundaries and can be in between, we can continue. However, if days[i] < days[left] or days[i] < days[right], meaning we found a middle flower that blooms earlier. It cannot in the window. So we shift the window such that left = i and right = left + k + 1. If all days between left and right are later, we found a solution.

Time: O(n)

Space: O(n), extra space to store days each flower blooms.

	public class Solution {
	/**
	* @param flowers:
	* the place where the flower will open in that day
	* @param k:
	* an integer
	* @return: in which day meet the requirements
	*/
	public int kEmptySlots(int[] flowers, int k) {
	int n = flowers.length;
	int[] pos = new int[n];
	for (int i = 0; i < n; i++) {
	int day = i + 1;
	int idx = flowers[i] – 1;
	pos[idx] = day;
	}
	int l = 0, r = k + 1;
	int result = n + 1;
	while (r < n) {
	int i = l + 1;
	while (i < r && pos[i] > pos[l] && pos[i] > pos[r]) {
	i++;
	}
	if (i == r) // !!! Do not return here. This is *one* solution, but may not be the first day !!!
	result = Math.min(result, Math.max(pos[l], pos[r]));
	l = i;
	r = i + k + 1;
	}
	return result == n + 1 ? -1 : result;
	}
	}

view raw

KEmptySlots.java

hosted with ❤ by GitHub

TreeSet Solution

The idea was to walk through the flowers array (positions) and insert positions into BST (simulate day-after-day). Meanwhile, for each in coming position pos, check before (pos – k – 1) and after (pos + k + 1) whether those flowers already inserted. Leverage higher()/lower() methods from TreeSet. If set, meaning there’s a solution, return the current day. Because positions are inserted while the checking happens, so it implies the flowers in between haven’t bloom yet. Otherwise, insert current position into BST and continue.

Consider using TreeSet when need efficient ceiling/floor kind of operations.

Time: O(nlogn), higher/lower operations O(logn), in a loop perform at most n times;

Space: O(n), store all flower positions in BST.

	import java.util.TreeSet;
	class Solution {
	public int kEmptySlots(int[] flowers, int k) {
	// Store flower position in a tree set
	// so we can quickly get the flower k distance apart
	// (either before or after) very quickly
	TreeSet<Integer> ts = new TreeSet<>();
	for (int i = 0; i < flowers.length; i++) {
	int pos = flowers[i];
	// Check if right (i + k + 1) is set and nothing in between
	// higher() already imply that nothing is in between,
	// otherwise there will be something
	Integer after = ts.higher(pos);
	if (after != null && after == pos + k + 1) {
	return i + 1;
	}
	// Check if left (i – k – 1) is set and nothing in between
	// lower() already imply that nothing is in between
	// otherwise there will be something
	Integer before = ts.lower(pos);
	if (before != null && before == pos – k – 1) {
	return i + 1;
	}
	ts.add(pos);
	}
	// Cannot find a solution
	return -1;
	}
	}

view raw

KEmptySlotsBST.java

hosted with ❤ by GitHub

Binary Index Tree Solution

This the the binary index tree solution. Let’s first brush up on BIT.

Binary Index Tree

Let’s say you have an array of integers, you can create a separate BIT to quickly find the sum between the beginning and any given index in O(logn) time. BIT index is 1-based. A node removes its last 1-bit gives its parent. 0110 –> 0100. Each node stores sum in segment (parent, child].

BIT has two methods:

• update(int val, int index)
  • Insert an element to the BIT at given index.
  • It also updates all nodes “covers” current node.
  • Time: O(logn).
  • index += index & (-index) to get next node to update. Keep shifting last 1 bit to the left, and clear other 1 bits along the way. 
• read(int index)
  • Read the prefix sum at given index;
  • Time: O(logn).
  • index -= index & (-index). Keep trace back through parents and add the sum.

The idea to use BIT in this problem is we going through day by day and insert value 1 and flower position into BIT. This forms a BIT for an arrays of 1s. (1 means bloom and 0 means not bloom). Meanwhile, after each insert at position i, first read prefix sum at i and i + k + 1 from BIT. If diff is 1, then we found a solution, which is to its right. Otherwise, read prefix sum at i - k - 1 and i. If diff is 1, then we found a solution to its left.

Time: O(nlogn), worst case insert each element in BIT.

Space: O(n), binary index tree.

	class Solution {
	// Binary index tree is 1 indexed
	private int[] bitree;
	public int kEmptySlots(int[] flowers, int k) {
	int len = flowers.length;
	bitree = new int[len + 1];
	for (int i = 0; i < len; i++) {
	update(1, flowers[i]);
	// Compare the flower k distance apart to its right
	if (flowers[i] + k + 1 <= len) {
	if (read(flowers[i] + k + 1) – read(flowers[i]) == 1) {
	return i + 1;
	}
	}
	// Compare the flower k distance apart to its left
	if (flowers[i] – k – 1 >= 1) {
	if (read(flowers[i]) – read(flowers[i] – k – 1) == 1) {
	return i + 1;
	}
	}
	}
	return -1;
	}
	/*
	* Binary index tree update method.
	* It adds given value to the given node and all
	* the nodes that "cover" it.
	*/
	private void update(int val, int index) {
	while (index < bitree.length) {
	bitree[index] += val;
	index += index & (-index);
	}
	}
	/*
	* Binary index tree read method.
	* It returns the prefix sum of a given index.
	*/
	private int read(int index) {
	int sum = 0;
	while (index > 0) {
	sum += bitree[index];
	index -= index & (-index);
	}
	return sum;
	}
	}

view raw

KEmptySlotsBIT.java

hosted with ❤ by GitHub

K Consecutive Slots

This is a follow up question. Instead of finding two flowers with k empty slots in between, this problem is regarding find the last day where exact k consecutive flowers bloom.

The solution is very similar to the first problem using two pointers and sliding window. The idea is to maintain a sliding window [l, r] where [l + 1, r – 1] all bloom in earlier days than [l] and [r]. Therefore, need to build an array “days” where days[i] means at position i, which position flower bloom. Note that “sliding window” needs to work on physical positions, thus need to convert from temporal array to spatial array. 

Because the consecutive blooms can at the edge. Add one padding on each end of days array can simplify the processing. Initialize with Integer.MAX_VALUE pretend never bloom. 

Time: O(n), sliding window move one direction.

Space: O(n), extra space for days array.

	class Solution {
	public int kEmptySlots(int[] flowers, int k) {
	// Build a days array to store which day a position flower bloom
	// Create an extra slot at the beginning and end make it easy to
	// process
	int[] days = new int[flowers.length + 2];
	days[0] = Integer.MAX_VALUE;
	days[days.length – 1] = Integer.MAX_VALUE;
	for (int i = 0; i < flowers.length; i++) {
	int day = i + 1;
	int pos = flowers[i];
	days[pos] = day;
	}
	// Two pointers of the window
	// Our goal is to find [l + 1, r – 1] that all bloom
	// but l and r do not not bloom.
	// a.k.a [l + 1, r – 1] must have smaller days than l and r.
	int l = 0;
	int r = k + 1;
	for (int i = 1; i < days.length; i++) {
	if (i == r || i == days.length – 1) {
	// Found a solution, go through the days in the window
	// and find the largest day
	int max = Integer.MIN_VALUE;
	for (int j = l + 1; j < i; j++) {
	max = Math.max(max, days[j]);
	}
	return max;
	} else {
	if (days[i] >= days[l] || days[i] >= days[r]) {
	// Found flower i in the window that bloom later than two ends
	// thus flower i cannot be in the window
	// Advance left pointer to i
	l = i;
	r = l + k + 1;
	if (r >= days.length) {
	// Cannot find a solution
	break;
	}
	}
	}
	}
	return -1;
	}
	}

view raw

KConsecutiveSlots.java

hosted with ❤ by GitHub