FastPrepTriangular Range Increments

Triangular Range Increments

IMC Trading logoIMC Trading● MediumFULLTIMEOA
Learn

Problem statement

You are given initial values and queries [i,v], using zero-based indices.

Each query adds max(v - abs(j-i), 0) to every valid position j. The contribution decreases by one per step away from i; each side stops at its boundary or at a zero contribution.

Return the final array after all queries. Use signed 64-bit values for the result.

Function

applyTriangularUpdates(values: int[], queries: int[][]) → long[]

Examples

Example 1

values = [0,0,0,0,0,0,0,0,0]queries = [[3,5]]return = [2,3,4,5,4,3,2,1,0]

The corrected source pattern adds [2,3,4,5,4,3,2,1,0].

Example 2

values = [2,0,1]queries = [[0,2],[2,3]]return = [5,3,4]

Both triangular contributions are added independently and clipped at the array boundaries.

Constraints

  • 1 <= values.length <= 10^5
  • 0 <= queries.length <= 10^5
  • 0 <= values[j] <= 10^9
  • Each query contains [i,v], with 0 <= i < values.length and 1 <= v <= 10^9.

More IMC Trading problems

See IMC Trading hiring insights
public long[] applyTriangularUpdates(int[] values, int[][] queries) {
    // Write your solution here.
}
values[0,0,0,0,0,0,0,0,0]
queries[[3,5]]
expected[2,3,4,5,4,3,2,1,0]
Checking account…