See the original problem on HackerRank.
Consider an array of integers A = [a1, a2, …, aN]. We can perform two types of queries on A:
1 k: For query type 1, find and print an integer denoting the index of the kth zero in array A on a new line; if no such index exists (i.e., there is no zero), print NO instead.
p x: For query type 2, replace the element positioned at index p with integer x (i.e., set A[p] = x).
Given A’s initial state and queries, perform each query in order. For each query of type 1, print the query’s answer on a new line.
The first line contains two space-separated integers describing the respective values of n (the size of the array) and m (the number of queries). he second line contains space-separated integers describing the respective elements of array A (e.g. a0, a1, …, aN).
Each of the m subsequent lines describes a query in one of the following forms:
1 k, where 1 is the query type and k denotes the kth zero you must locate an index for in the array.
2 p x, where 2 is the query type, p is the index (position) you must update, and x denotes the new value to store at A[p].
For each query of type 1, print a single integer on a new line denoting the index where the kth zero is located in A; if no such index exists (i.e., there is no zero), print NO instead.
The naïve solution is to create the array just as it defined and do a linear search for each query.
Although update is fast (\( O(1) \)), the search is slow, because we need to search linearly the kth zero (\( O(N) \)).
In this Problem, we have two types of queries that are to be performed on the array. One is called as Kth Zero over a range and other is a Point update Query. For this class of problems, the suitable data structure is a Segment Tree.
Thus, the quickest solution uses such a data structure (credits to HackerRank):
Build the tree. Node value is the count of zeroes in the range.
Find 2nd zero
Change value at position 1 to 5
More info about segment trees:
Segment tree (C)
Segment tree (C++)
Collection of zero’s indexes
However, the space cost is 4-times the problem dimension. A possible solution which allocates at most N elements but is ~4-times slower than the previous one consists in keeping track only of the zeros updates:
Note: we used a
std::deque that is, basically, a paged array. Replacing it
std::vector is twice as slower.
Same algorithm but in Rust courtesy of Alessandro and Edoardo: