Array Manipulation

Easy

0/40

0 upvote

Asked in companies

Problem statement

You are given a 0-indexed array of size n, initially filled with zeros. You have to perform m operations on this array.

Each operation is defined by a triplet (a, b, k), which instructs you to add the value k to every element of the array from index a to index b, inclusive.

After performing all m operations, your task is to find and return the maximum value in the final array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains two space-separated integers, n and m.

The next m lines each contain three space-separated integers, a, b, and k.

Output Format:

Print a single integer representing the maximum value in the array after all operations are complete.

Note:

A naive solution of actually performing the additions for each query would be O(m * n), which is too slow for the given constraints.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

Using the difference array method:
1.  Initial difference array of size `n+1`: `{0, 0, 0, 0, 0, 0}`
2.  `0 1 100`: Add 100 at index 0, subtract 100 at index 2. Array: `{100, 0, -100, 0, 0, 0}`
3.  `1 4 100`: Add 100 at index 1, subtract 100 at index 5. Array: `{100, 100, -100, 0, 0, -100}`
4.  `2 3 100`: Add 100 at index 2, subtract 100 at index 4. Array: `{100, 100, 0, 0, -100, -100}`
5.  Now, calculate the prefix sum to get the final array:
  - `A[0] = 100`. Max = 100.
  - `A[1] = 100 + 100 = 200`. Max = 200.
  - `A[2] = 200 + 0 = 200`. Max = 200.
  - `A[3] = 200 + 0 = 200`. Max = 200.
  - `A[4] = 200 - 100 = 100`.
The maximum value found is 200.

Expected Time Complexity:

The expected time complexity is O(n + m).

Constraints:

1 <= n <= 10^7
1 <= m <= 10^5
0 <= a <= b < n
1 <= k <= 10^9

Time limit: 2 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Array Manipulation

Console