How to find the count of the number of subarrays whose max=k ?

general
,
1

I do have a nice solution which works in O(N),I want to know the ideas of other people on it?
Thanks!:slight_smile:

2

I can think of two ways -

Let the array of elements be A, and its size N

  1. We can count sub arrays, based on the sub array’s starting index -

    For every sub array A[i, j], for its max element to be k, all elements A[p]<=k, i<=p<=j and atleast one element shoud be k, so let us calculate two values i1 and i2 for each index i, such that i1,i2 >= i and
    `

**i1 = least value not less than i, such that A[i1]=k**, and 


**i2 = least value not less than i, such that A[i2]>k**


clearly every for subarray A[i, j] starting at index i, j < i2 and j >=i1 is the necessary and sufficient condition

`hence the no of subarrays starting at index i with max=k are i2-i1, and we can calculate these values i1, i2 for all i in O(N) by traversing the array from right to left.

  1. We can solve it by divide and conquer approach, in which we divide the array into two equal parts , count no of subarrays for which max=k in each of the two parts and combine those two to also count the no of subarrays which have max=k and their start index in the first part and end index in the second part.

    To do that for each slice of array A[i,j] we calculate four values - pre_maxk, suf_maxk, pre_nmaxk, suf_nmaxk, which are -

    pre_maxk - length of maximum prefix whose max element = k, similarly for suf_maxk, except we use suffix.
    pre_nmaxk - length of maximum prefix whose max element < k, similarly for suf_nmaxk.

    So while merging two slices of array we count the no of subarrays whose start index is in left slice and end index in right slice, we do it like this -

    count += (left.suf_maxk) * (right.pre_maxk) - (left.suf_nmaxk) * (right.pre_nmaxk)

    and the values of these four variables for the merged slice can also be calculated from the values of the left and right slices. So this dividing and combining part requires O(1) time, hence if divide left and right slices are of equal length then the complexity of this approach would be O(N).

1 Like
3

Divide and Conquer seems very complicated and doubtful in this case… … .
Thanks, anyways!:slight_smile: