Last Updated: 28 Oct, 2021
Tanziro and his Boxes
Moderate
Tanziro has ‘N’ boxes numbered from 0 to ‘N’ - 1. Initially, these boxes have values equal to zero. Nezuko wants to perform K operations and for each operation, she wants to update the value of some boxes by some value ‘X’. She gave Tanziro a 2D array ‘value’ of size ‘K’ * 3, Where the first element of the ith index in this array denotes the starting index of the box, the second element denotes the ending index of the box and the third element denotes the value to be given to the boxes in between these indexes. Now after the completion of all the ‘K’ operations Nezuko wants to know the value of all of these boxes. Help Tanziro in calculating the final values. All the indices are zero-based indexes.
For Example :
‘N’ = 4, ‘K’ = 3, ‘coins’ = {0, 2, 3}, {1, 3, -5}, {0, 0, 7}.
Now in this example, after the first operation, the value on the boxes will be {0, 0, 0, 0} -> {3, 3, 3, 0}, after the second operation, the values will be {3, 3, 3, 0} -> {3, -2, -2, -5} and after the last operation the values are {3, -2, -2, 5} -> {10, -2, -2, 5}. Hence the answer is {10, -2, -2, 5}.
Input Format :
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.
The first line of each test case contains two integers ‘N’ and ‘K’, denoting the number of boxes Tanziro has and the number of operations Nezuko wants to perform, respectively.
The next ‘K’ lines of the test case contain 3 integers, the starting index of the box, the ending index, and the value to be updated.
Output Format :
For each test case, print an array denoting the final values on the boxes.
Output for every query will be printed in a separate line.
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.
Constraints :
1 <= T <= 10
1 <= ‘N’ <= 5000
1 <= ‘K’ <= 5000
0 <= ‘value[i][0]’, ‘value[i][1]’ <= N - 1
-5000 <= ‘value[i][2]’ <= 5000
Time Limit: 1 second
Approaches
The approach is simple, we will iterate through all the operations from 1 to K and for each operation, we will iterate through the starting index and go to the ending index and update every value by the given value.
The steps are as follows:
- Take a vector ‘answer’ to store the final answer.
- Iterate through the loop from 0 to ‘K’ - 1(say iterator be i):
- For each element in ‘value[i]’ iterate through the loop from ‘value[i][0]’ to ‘value[i][1]’(say iterator be j):
- Update the value of ‘answer[j]’ equal to ‘answer[j]’ + ‘value[i][2]’.
- For each element in ‘value[i]’ iterate through the loop from ‘value[i][0]’ to ‘value[i][1]’(say iterator be j):
- Return ‘answer’.
Let’s look at the problem in a different way. We will not update the whole array, we will just update ‘answer’ at starting index with a positive value of ‘value[i][2]’ and the ending index with a negative value, and when all the operations are finished then we will iterate through the ‘answer’ array and we will apply cumulative sum operation on the whole array i.e. we will update ‘answer[i]’ with ‘answer[i]’ + ‘answer[i - 1]’.
The steps are as follows:
- Take a vector ‘answer’ of size ‘N’ + 1 to store the final answer.
- Iterate through the loop from 0 to ‘K’ - 1(say iterator be i):
- Take two integers ‘start’ and ‘end’ where ‘start’ equals to ‘value[i][0]’ and ‘end’ equals to ‘value[i][1]’.
- Update the value of ‘answer[start]’ equal to ‘answer[start]’ + ‘value[i][2]’.
- Update the value of ‘answer[end + 1]’ equal to ‘answer[end + 1]’ - ‘value[i][2]’.
- Iterate through the array ‘answer’ from 1 to ‘N’ - 1(say iterator be i):
- Update the value of ‘answer[i]’ with ‘answer[i]’ + ‘answer[i - 1]’.
- Return ‘answer’.
Similar problems