Zero Array Transformation I - Leetcode 424 Solution

 

Approach:

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:

If you have any query just comment down below👇