Problem Link : div1 , div2
Difficulty : easy
Pre requisites : difference array
Problem : Given an array c denoting radiation power of n caves(1 based indexing) such that for every value c[i] the radiation level increases in the caves (i-c[i]) to (i+c[i]) by 1 if they exist. Originally the radiation level was zero in all of them. Also you are given an array denoting health of n zombies. You need to check whether it is possible to put n zombies in n caves(exactly one in each cave) so that each zombie’s health equals the radiation level of the cave it is in.
Quick Explanation :
The major part of the question lies in generating the radiation level array and then we can sort the radiation level and health arrays and check for equality. For this we will use difference array to update the radiation levels in the caves. Geeks for Geeks article on range update query using difference array
Explanation :
Let us call our radiation level array as A initialized with zero for each cave.
For each i (1 <= i <= n) we need to add 1 to all caves with index lying between max(1,(i-c[i])) to min(n,(i+c[i])).
So here we use the difference array and increase only the max(1,(i-c[i])) by 1 and decrease min(n,(i+c[i]))+1 index value by 1 if it exists.
This array denotes the difference between radiation levels for two consecutive caves.
If our difference array is [4,0,-1,0,-1] {1-based indexed} the radiation level in cave 1 is diff_array[1]=4, cave 2 is A[1]+diff_array[2] = 4 , in cave 3 is A[2]+diff_array[3] = 3 and so on.
For the sample input
n=5
c=[1,2,3,4,5]
diff_array=[0,0,0,0,0] initially
Let’s update our difference array for all indexes one by one
Index=1 : max(1,(i-c[i]))=1 and min(n,(i+c[i]))+1=3
diff_array=[1,0,-1,0,0]
Index=2 : max(1,(i-c[i]))=1 and min(n,(i+c[i]))+1=5
diff_array=[2,0,-1,0,-1]
Index=3 : max(1,(i-c[i]))=1 and min(n,(i+c[i]))+1=6
diff_array=[3,0,-1,0,-1]
Index=4 : max(1,(i-c[i]))=1 and min(n,(i+c[i]))+1=6
diff_array=[4,0,-1,0,-1]
Index=5 : max(1,(i-c[i]))=1 and min(n,(i+c[i]))+1=6
diff_array=[5,0,-1,0,-1]
A=[5,5,4,4,3]
Now sort A and it becomes [3,4,4,5,5]
Now sort h and compare these two.
Complexity :
Time Complexity : All updates occur in O(1*n(for all updates)) time,the arrays are generated in O(n) time and the sorting occurs in O(n log(n)) time. So the overall time complexity is O(n log(n)).
Space Complexity : O(n)
Hope it helps! Feel free to share your approach and any feedback