Bruteforce Approach:It is a simple approach if you are change the nums array for each query it will give you the Time Limit Exceeded.
Efficient Approach:Using the difference array you can solve the problem in an efficient manner.
1.Create differnce array of size n+1.The idea behind the difference array is that instead of updating all elements in a range directly, we just mark the start and the end+1 of the range, and the cumulative sum of this array will give us the final effect.
2.In difference array set the start index to -1 and end+1 to +1.
3.Repeat the step 2 after all queries had finished.
4.Now check the cumulative sum of the difference array at any point of time cumulative value is less than the current nums[i] value (as it means you cannot reduce nums[i] to zero)just simply returns false.
5.otherwise the answer is true.
Code:
Amazingly !! explained
ReplyDelete