FastPrep
Problem · Array

Maximum Length-K Window Sum over Sparse Segments

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A very large array is represented by segments. Each row [start, end, value] assigns value to every integer index from start through end, inclusive. Indices not covered by any segment have value 0.

Return the maximum sum of any contiguous window containing exactly k indices. The expanded array may be too large to store, so process the sparse segments directly.

Function

maximumKWindowSum(segments: int[][], k: int) → long

Examples

Example 1

segments = [[1,3,4],[6,7,1]]k = 3return = 12

The window covering indices 1 through 3 contains [4,4,4] and has sum 12.

More Amazon problems

drafts saved locally
public long maximumKWindowSum(int[][] segments, int k) {
  // write your code here
}
segments[[1,3,4],[6,7,1]]
k3
expected12
checking account