FastPrep
Problem · Heap

Running Delivery Time Medians

● MediumAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Given an array deliveryTimes, process the values from left to right. After each new delivery time arrives, output the median of all delivery times seen so far.

When the number of seen values is even, use the lower median, meaning the larger value in the lower half after sorting.

Return an array containing the median after each insertion.

Examples
01 · Example 1
deliveryTimes = [5,17,100,11]
return = [5,5,17,11]

The sorted prefixes are [5], [5,17], [5,17,100], and [5,11,17,100]. Their lower medians are 5, 5, 17, and 11.

Constraints
  • 1 <= deliveryTimes.length <= 2 * 10^5
  • 0 <= deliveryTimes[i] <= 10^9
More Amazon problems
drafts saved locally
public int[] runningDeliveryMedians(int[] deliveryTimes) {
  // write your code here
}
deliveryTimes[5,17,100,11]
expected[5,5,17,11]
sign in to submit