Python Algorithm For Area Contained In Array (Graph)

Question

Setup:

Visualize a large array of numbers where each number represents a height of a bar on a bar graph.

Ex: [5, 4, 3, 7, 2, 3, 1, 12]

       █
       █
       █
       █
       █
   █   █
   █   █
█  █   █
██ █   █
████ █ █
██████ █
████████

Analyze:

This is the bar graph of the previous numbers. What I need to find is the area containted in the graph in number of open (or unfilled) units.

Solution (Pt.1):

To go about this I made an algorithm to calculate all the peaks in the array.

This returns : [5, 7, 3, 12] as well as another list with the indices of each entry, [0,3,5,7]

To us, there are only three important peaks to find the area. The 5, the 7, and the 12. We can then break it down like this.

The amount of open area in between the 5 and 7 is (general rule):

(([Index Of Larger] - [Index Of Smaller] - [1])*[SmallerValue]) - [Values Of All In B/W]

So the area of the first section would be (2*5) - (4+3) or 10-7 or 3. THis makes sense because if you look at the graph you see there is an empty L shaped section that you could fit 3 units of say, water in without it overflowing. If you repeat this with the second section you get its correct area as well.

My issue is developing an algorithm to go from ALL PEAKS to the IMPORTANT PEAKS.

Misleading:

In this case it is extremely easy to see how that could be done. You simply write an algo to find that the 3 is smaller than the 7 and the 12 so get rid of it and return a refined version of the peaks.

However it is not always that simple.

More Difficult Example:

I have an array:

[5, 4, 3, 7, 2, 3, 1, 12, 9, 10, 5, 3, 6, 8, 5, 6, 4, 7, 6, 9, 4, 11, 11, 4, 1, 2, 1]

Running it through a basic custom peak finding algorithm O(N) It returns:

[5, 7, 3, 12, 10, 8, 6, 7, 9, 11, 11, 4, 2]

In this example, we see the same problem in the first part of this question, however, after the 12 in this peak list, a human can easily see that the next most important peak to look at are the two 11s, the 4, and 2. So I need a way to go from:

[5, 7, 3, 12, 10, 8, 6, 7, 9, 11, 11, 4, 2]

To:

[5, 7, 12, 11, 11, 4, 2]

The above array is a list of the 'important' peaks that are necessary to find the area and again visualize the open blocks as if they'd contain water or something so that they are limited to the lowest immediate peak before overflowing.

To better visualize this more full, second example I have a picture of the graph and all of its peaks and data points here.

Thank you.

Answer 1

You could solve this problem by considering two values:

1. Max peak so far, starting from the left
2. Max peak so far, starting from the right

And don't accept a peak if it is inferior to both, because it will be under water.

Answer 2

I think this handles all conditions but all the maximum calculations will slow it down for large data sets. I used IPython Notebook to graph it. It is basically @Rémi's idea:

For any data point:

1. Take the maximum point to the left and the maximum point to the right. a. If at the ends assume zero.
2. Take the minimum of the two maximum points.
3. If the datapoint is below that minimum, it is underwater and return the difference else zero.

It could be optimized by computing the left maximum as it scans to the right, and computing the right maximums for each position ahead of time in a single pass from right to left.

The algorithm as is took about 4.1 seconds to do 10,000 data points on my system.

The unfilled area (yellow) will be sum(C):

%matplotlib inline
import matplotlib.pyplot as plt
import random

def contribution(L,i):
    max_left = 0 if i==0 else max(L[:i])
    max_right = 0 if i==len(L)-1 else max(L[i+1:])
    lower = min(max_left,max_right)
    return 0 if lower < L[i] else lower - L[i]

N = [random.randint(0,12) for i in range(50)]
C = [contribution(N,i) for i in range(len(N))]

ind = list(range(len(N))) # the x locations for the groups
width = 1                 # the width of the bars: can also be len(x) sequence

p1 = plt.bar(ind, N, width, color='r')
p2 = plt.bar(ind, C, width, color='y',bottom=N)

Edit

Here's a faster version that implements the optimization I mentioned above. It computes one million datapoints in 1.33 seconds, but uses a smaller amount for graphing below. I don't see how it could be done in one pass, given that a cell needs to know the maximum to its left and right and there could be multiple points equal to the maximum in either direction.

%matplotlib inline
import matplotlib.pyplot as plt
import random

def right_maximums(L):
    '''Given list L, compute [max(L[i+1:] for i in range(len(L)-1)]+[0] more efficiently.
    
    This gives the maximum cell to the right of the current cell.
    Example: [1,2,3,4,5,4,3,2,1] -> [5,5,5,5,4,3,2,1,0]
    '''
    N = [0]
    for i,v in enumerate(L[:0:-1]):
        N.append(max(N[i],v))
    return N[::-1]

def contribution(N):
    '''In a bar graph of data N, compute how much "water" a data valley, assuming water
    spills off the sides of the bar graph.
    '''
    rmaxs = right_maximums(N) # compute maximums to the right of a data point in advance.
    lmax = 0 # compute maximums to the left as we go.
    C = []
    for i,v in enumerate(N):
         # find the lower of the left and right maximum.
        lower = min(lmax,rmaxs[i])
        # if the data point is higher than the maximums, it won't hold water,
        # else it holds the difference between the lower maximum and its value.
        C.append(0 if lower < v else lower - v)
        lmax = max(lmax,v)
    return C

N = [random.randrange(0,50) for i in range(50)]
C = contribution(N)

ind = list(range(len(N))) # the x locations for the groups
width = 1                 # the width of the bars: can also be len(x) sequence

p1 = plt.bar(ind, N, width, color='r')
p2 = plt.bar(ind, C, width, color='y',bottom=N)

Answer 3

It can be done in 3 passes:

  public static int areaContained(int[] arr) {
    int[] maxL = new int[arr.length];
    int[] maxR = new int[arr.length];

    int max = 0;
    for (int i = 0; i < arr.length; i++) {
      max = Math.max(arr[i], max);
      maxL[i] = max;
    }

    max = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
      max = Math.max(arr[i], max);
      maxR[i] = max;
    }

    int total = 0;
    for (int i = 0; i < arr.length; i++) {
      int areaI = Math.min(maxL[i], maxR[i]) - arr[i];
      if (areaI > 0)
        total += areaI;
    }

    return total;
  }

The main idea is that the contribution of bar i is determined by the combination of arr[i], max value after i, and max value before i.