Tanziro and his Boxes

Moderate
0/80
profile
Contributed by
0 upvote

Problem statement

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}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 1
0 1 10
5 3
0 3 4
2 4 4
0 1 -7
Sample Output 1 :
10 10
-3 -3 8 8 4
Explanation For Sample Output 1 :
For the first example, after the first operation, the value on the boxes will be {0, 0} -> {10, 10}, Hence the answer is {10, 10}.

For the second example, after the first operation, the value on the boxes will be {0, 0, 0, 0, 0} -> {4, 4, 4, 4, 0}, after the second operation, the values will be {4, 4, 4, 4, 0} -> {4, 4, 8, 8, 4} and after the last operation the values are {4, 4, 8, 8, 4} -> {-3, -3, 8, 8, 4}. Hence the answer is {-3, -3, 8, 8, 4}.
Sample Input 2 :
2
3 2
0 2 -4
0 2 -8
5 3
1  3  2
2  4  3
0  2 -2
Sample Output 2 :
-12 -12 -12
-2 0 3 5 3
Hint

Iterate through all the operations and Update the array for every index.

Approaches (2)
Brute Force Approach

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:

  1. Take a vector ‘answer’ to store the final answer.
  2. 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]’.
  3. Return ‘answer’.
Time Complexity

O(N * K). Where N is the total number of boxes and K is the total number of operations.


As we are iterating through every operation and each operation in the worst case can have a range from 1st to the Nth box, resulting in ‘K’ * ‘N’ time complexity.

Hence, the time complexity is O(N * K).

Space Complexity

O( N ), Where N is the total number of boxes.


Since we are taking a vector of size N to store the answer. 

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Tanziro and his Boxes
Full screen
Console