You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

asked 01 Feb, 13:41

karangreat234's gravatar image

5★karangreat234
-8639
accept rate: 0%


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.

  2. 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).

link
This answer is marked "community wiki".

answered 01 Feb, 18:38

hemanthvhr's gravatar image

2★hemanthvhr
11
accept rate: 100%

1

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

(02 Feb, 11:26) karangreat2345★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×43
×3

question asked: 01 Feb, 13:41

question was seen: 99 times

last updated: 02 Feb, 11:26