FastPrep
Problem · Array

Cumulative Unique Bytes

Learn this problem
● MediumHudson River Trading logoHudson River TradingINTERNNEW GRADOA

Problem statement

A team of astronauts is receiving a file from Earth in a sequence of data segments. Each segments[i] contains two 64-bit integers: the 1-based index of the first byte and the 1-based index of the last byte in that segment. Both endpoints are inclusive.

After each segment is received, calculate the total number of unique byte indices covered by all segments received so far. Segments may overlap or completely duplicate earlier segments, and each byte must be counted only once.

Return an array where result[i] is the cumulative number of unique bytes received after processing segments[i].

Function

solution(segments: long[][]) → long[]

Examples

Example 1

segments = [[1,1],[2,2],[3,3]]return = [1,2,3]

The first segment contributes byte 1. The second contributes byte 2, and the third contributes byte 3, so the cumulative totals are [1, 2, 3].

Example 2

segments = [[1,1],[2,2],[3,5]]return = [1,2,5]

The first two segments cover bytes 1 and 2. The final segment adds bytes 3 through 5, increasing the cumulative total to 5.

Example 3

segments = [[1,9],[1,3],[8,15],[6,9],[2,5]]return = [9,9,15,15,15]

The first segment covers bytes 1 through 9. The second segment is already covered. The third extends the covered range through byte 15, and the remaining segments add no new bytes.

Example 4

segments = [[7,9],[1,3],[8,15],[6,9],[2,4]]return = [3,6,12,13,14]

The cumulative covered intervals evolve from [7, 9], to [1, 3] and [7, 9], then to [1, 3] and [7, 15]. The fourth segment adds byte 6, and the fifth adds byte 4, producing totals [3, 6, 12, 13, 14].

Constraints

  • 1 <= segments.length <= 1000
  • segments[i].length = 2
  • 1 <= segments[i][0] <= segments[i][1] <= 10^12

More Hudson River Trading problems

drafts saved locally
public long[] solution(long[][] segments) {
    // write your code here
}
segments[[1,1],[2,2],[3,3]]
expected[1,2,3]
checking account