This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Assume you have an array of length ** n** initialized with all

Each operation is represented as a triplet: **[startIndex, endIndex, inc]** which increments each element of subarray **A[startIndex ... endIndex]** (startIndex and endIndex inclusive) with **inc**.

Return the modified array after all ** k** operations were executed.

**Example:**

Given: length = 5, updates = [ [1, 3, 2], [2, 4, 3], [0, 2, -2] ] Output: [-2, 0, 3, 5, 3]

**Explanation:**

Initial state: [ 0, 0, 0, 0, 0 ] After applying operation [1, 3, 2]: [ 0, 2, 2, 2, 0 ] After applying operation [2, 4, 3]: [ 0, 2, 5, 5, 3 ] After applying operation [0, 2, -2]: [-2, 0, 3, 5, 3 ]

**Credits:**

Special thanks to @vinod23 for adding this problem and creating all test cases.

b'

\n## Solution

\n

\n#### Approach #1 Na\xc3\xafve Approach [Time Limit Exceeded]

\n\n

\n#### Approach #2 Range Caching [Accepted]

\n\n

\n## Further Thoughts

\n

\n

'
\n\n

\n\n

**Algorithm**

The algorithm is trivial. For each update query, we iterate over the required update range and update each element individually.

\n**C++**

Each query of `updates`

is a tuple of 3 integers: (the start and end indexes for the update range) and (the amount by which each array element in this range must be incremented).

vector<int> getModifiedArray(int length, vector<vector<int> > updates)\n{\n vector<int> result(length, 0);\n\n for (auto& tuple : updates) {\n int start = tuple[0], end = tuple[1], val = tuple[2];\n\n for (int i = start; i <= end; i++) {\n result[i] += val;\n }\n }\n\n return result;\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : (worst case) where is the number of update queries and is the length of the array. Each of the update operations take up time (worst case, when all updates are over the entire range).

\n \n - \n
Space complexity : . No extra space required.

\n \n

\n

**Intuition**

- \n
- \n
There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant.

\n \n - \n
Cumulative sums or

\n`partial_sum`

operations apply the effects of past elements to the future elements in the sequence. \n

**Algorithm**

The algorithm makes use of the above intuition to simply store changes at the *borders* of the update ranges (instead of processing the entire range). Finally a single post processing operation is carried out over the entire output array.

The two steps that are required are as follows:

\n- \n
- \n
For each update query on the array , we need to do

\n*only*two operations:- \n
- Update boundary of the range: \n

\n\n

\n- \n
- Update just beyond the boundary of the range: \n

\n\n

\n \n - \n
Final Transformation. The cumulative sum of the entire array is taken (

\n`0`

- based indexing)\n\n

\n \n

**C++**

vector<int> getModifiedArray(int length, vector<vector<int> > updates)\n{\n vector<int> result(length, 0);\n\n for (auto& tuple : updates) {\n int start = tuple[0], end = tuple[1], val = tuple[2];\n\n result[start] += val;\n if (end < length - 1)\n result[end + 1] -= val;\n }\n\n // partial_sum applies the following operation (by default) for the parameters {x[0], x[n], y[0]}:\n // y[0] = x[0]\n // y[1] = y[0] + x[1]\n // y[2] = y[1] + x[2]\n // ... ... ...\n // y[n] = y[n-1] + x[n]\n\n partial_sum(result.begin(), result.end(), result.begin());\n\n return result;\n}\n

**Formal Explanation**

For each update query on the array , the goal is to achieve the result:

\n\n\n

\nApplying the final transformation, ensures two things:

\n- \n
- It carries over the increment over to every element . \n
- It carries over the increment (equivalently, a decrement) over to every element . \n

The net result is that:

\n\n\n

\nwhich meets our end goal. It is easy to see that the updates over a range did not carry over beyond it due to the compensating effect of the increment over the increment.

\nIt is good to note that this works for multiple update queries because the particular binary operations here (namely addition and subtraction):

\n- \n
- \n
are

\n*closed*over the entire domain of`Integer`

s. (A counter example is division which is not closed over all`Integer`

s). \n - \n
are

\n*complementary*operations. (As a counter example multiplication and division are not always complimentary due to possible loss of precision when dividing`Integer`

s). \n

**Complexity Analysis**

- \n
- \n
Time complexity : . Each of the update operations is done in constant time. The final cumulative sum transformation takes time always.

\n \n - \n
Space complexity : . No extra space required.

\n \n

\n

An extension of this problem is to apply such updates on an array where all elements are **not** the same.

In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of .

\n@StefanPochmann suggested another method which does not require extra space, but requires an extra linear pass over the entire array. The idea is to apply *reverse* `partial_sum`

operation on the array (for example, array transforms to ) as an initialization step and then proceed with the second method as usual.

\n

Another general, more complex version of this problem comprises of multiple read and update queries over *ranges*. Such problems can be solved quite efficiently with Segment Trees by applying a popular trick called **Lazy Propogation**.

Analysis written by @babhishek21.

\n