Suppose you have a row of N cats, numbered from 0 to N - 1. Initially, all the cats are painted black. You are asked to perform Q operations of the following two types, in random order.
1.Painting Cats: Given a range a to b(inclusive), cats within the range are painted with a new color. Example input:
Type of operation | Start index | End index | Color
1 0 10 blue
No output (void)
2.Query Cat: Given a particular number a, return the color of the cat numbered a. Example input:
Type of operation | number
2 10
Example output:
blue
It is guaranteed that 1 ≤ N ≤ 1,000,000,000 and 1≤Q ≤ 300,000. Create a time and space efficient solution.
I could not answer this question without a hint given by my classmate. Not a difficult question to understand, so feel free to think of a solution if you can, before reading on.
Question Analysis
The difficulty lies in the time and space complexity requirements. Let's ignore them for a while and come up with a naive solution.
Naive approach
One possible way to solve the problem is to simply do as told. Initialize an N sized array and assign every slot to be of the color blue. When handling paint-cat operation, simply loop over the array from the starting index to the end index, updating the existing color to the new color. During query-cat operation, simply index to the slot in the array and output the color in that slot.
There are a few issues with the above naive approach. One being that N could be too large to handle. This means our array will take out substantial space to solve this problem. Besides, the time complexity of the paint-cat operation is O(N) because we touch every cat within range per operation. The upside to this solution is that the query-cat operation is O(1) thanks to the array indexing. In summary:
Space:
Time:
- O(N) per paint-cat, worst case O(QN), Q operations of paint-cat
- O(1) per query-cat, worst case O(Q), Q operations of query-cat
Getting better
Looking at the limiting factors, realize that we cannot represent every single cat, or else we will have trouble making it space-efficient. As for the two operations, we need sublinear time complexity for both.
There are a few choices, in terms of data structure, that can achieve sublinear complexity:
ADTs:
Map (implemented by Hashtable):
O(1) insert, O(1) update, O(1) query
Priority Queue (implemented by Binary Heap)
O(logn) insert, O(n) update, O(logn) query
Ordered Map (implemented by Balanced Binary Search Tree)
O(logn) insert, O(logn) update, O(logn) query
Binary Heap is out since it requires O(n) update in its standard implementation, although it could achieve O(logn) update with an additional Hashtable to keep track of positions.
Both Hashtable and bBST are possible. If we need to maintain some sort of order, we have to go with bBST.
Range Update, Point Query
The question, in effect, can be summarized by the above subheading. The key then is to represent the range and find out how we can query points from the new representation.
I thought about it for a long time. Certainly, we are employing a strategy just like using cones to mark out boundaries in a football field. A range of cats can be represented by the starting index and the ending index. To query a cat, we will look towards its left or right, till we find a demarcating cat. The approach is in the right direction. What puzzled me was how to update cats so that the boundaries are set correctly and point-query can be done properly.
Suppose we update the color of the starting index and the ending index cat. A few runs of operations are described as follows:
(10 cats)
starts with default color: Cat 0 => red, Cat 9 => red
Type of operation | Start index | End index | Color
1 2 5 blue
Cat 0 => red, Cat 2 => blue, Cat 5 => blue, Cat 9 => red
Now, if I employ the strategy where querying the cat will look for the nearest cat on its left that is colored, I can get away with the following queries
2 1 // Cat 0's color is red, hence Cat 1 is red
2 4 // Cat 2's color is blue, hence Cat 4 is blue
However, querying cats 6,7,8 will result in wrong output
2 7 // Cat 5's color is blue, hence Cat 7 is blue (WRONG)
There is also another issue with updating ranges that are overlapping:
// continuing the example above
1 1 3 green
Cat 0 => red, Cat 1 => green, Cat 2 => blue, Cat 3 => green, Cat 5 => blue, Cat 9 => red
Now that is a mess.
Solution
In the end, I needed two intuitions to fix the above issues.
- When querying, always look at the nearest colored cat on its left.
- When updating, ensure that the cats are painted in such a way that statement one will always return the correct output. In particular, updating a range also breaks down any previous ranges into separate ranges.
Breaking down the steps:
- Initialize an ordered map implemented by AVL tree (or any other balanced binary tree), in Java, use TreeMap.
- Insert index 0 and color red to mean all cats started with red.
- Per query, retrieve the successor of the given index in O(logn) and output the color.
- Per update, query(end index + 1) and insert end+1 index with the returned color. Clear the items in the tree that is within the updating range. Insert the starting index with the new color.
Instead of updating both the start index and the end index, we update the start index(new color) and end+1 index(marking the start of an existing color range). Also, we remove colored cats if they are within the new updated range. This way,
Space:
- O(Q) worst case, all operations are paint-cat, bBST
Time (n being the maximum number of cats in the bBST):
- O(logn) per paint-cat, worst case O(Qlogn), Q operations of paint-cat
- O(logn) per query-cat, worst case O(Qlogn), Q operations of query-cat
Sample Java solution as follows
import java.util.*;
public class PaintCats {
public static void main(String[] args) {
// custom fast io
Kattio k = new Kattio(System.in,System.out);
// read input
int numCat = k.getInt();
int numQ = k.getInt();
// init DS
TreeMap<Integer,String> cats = new TreeMap<>();
// predefined all cats to be Red
cats.put(0,'Red');
// read input
for (int i=0;i<numQ;i++){
int queryType = k.getInt();
if (queryType == 1){ // change color operations
int start = k.getInt();
int end = k.getInt();
String color = k.getWord();
if (end != numCat){ // if it is the last cat, no need to add in lower limit
// get color by looking at the lowerbound,since all the correct lowerbound + color will be
// in the treeMap
char endColor = cats.floorEntry(end+1).getValue();
cats.put(end+1,endColor);
}
// remove to save space + speed up look up, safe since start - end is updated here
cats.subMap(start,end).clear();
// put in new start
cats.put(start,color);
} else { // query color operations
int catNo = k.getInt();
// look for the color by checking the lowerbound since all lowerbound are correctly updated
k.println(cats.floorEntry(catNo).getValue());
}
}
k.close();
}
}
Visualization
Quick self-reminder:
You cannot target id of only digits such as #1, #2 in CSS.
In CSS, identifiers (including element names, classes, and IDs in selectors) can contain only the characters [a-zA-Z0-9] and ISO 10646 characters U+00A0 and higher, plus the hyphen (-) and the underscore (_); they cannot start with a digit, two hyphens, or a hyphen followed by a digit.
P.S. Behind the scene, the visualization does not work exactly as described in the efficient solution above. It is quite a challenge to visualize Balanced Binary Search Tree 😂
Further P.S. Having a hard time making this mobile friendly, view it on wider display, Chrome or FireFox, if you can.
See it on codepen
