Count spread in O(n)

October 12, 2017

This is not hard but still interesting.

A spread of an array of numbers is the difference between its maximum and minimum. Given an array of numbers x1,…,xnx1,…,xn, compute the sum of spreads of all of its continuous subarrays in O(n)O(n) time.

Solution:
If we could compute the sum of maximum of all continuous subarrays then it's easy. To do this, suppose we know this sum for x1,…,xn−1x1,…,xn−1. When xnxn comes in, we want to add to this sum the sum of maximums of (x1,…,xn),(x2,…,xn),…,(xn−1,xn),(xn)(x1,…,xn),(x2,…,xn),…,(xn−1,xn),(xn), or y1+y2+…+yny1+y2+…+yn, where ykyk is the maximum between xkxk and the last number. Clearly yy never goes up, so we could use a stack of triple (value,right,area)(value,right,area) to store info we need. (value,right,area)(value,right,area) is such that for rightk−1+1≤i≤rightkrightk−1+1≤i≤rightk, yi=valuekyi=valuek, and the cumulative area of yy curve from the beginning to rightkrightk is areakareak.

After xnxn comes in, (value,right,area)(value,right,area) is updated as this. Pop out all entries where value<xnvalue<xn. Now if the top of the stack has value=xnvalue=xn, update its areaarea and rightright accordingly. Otherwise push a new entry with value=xnvalue=xn and right=nright=n. Its areaarea should be the preceding areaarea plus xn×δxn×δ where δδ is nn minus the preceding rightright.

After (value,right,area)(value,right,area) is updated, add the last areaarea to the sum. The poppop takes amortized O(1)O(1) per element, and the rest takes a fixed O(1)O(1).

post by Shen-Fu Tsai