chari407's blog

By chari407, history, 7 years ago, In English

The problem is as follows: Given an array A1,A2....An, the array is called special if there is any Ai which satisfies either of the following cases: 1. Ai is the median of the subarray [A0,Ai-1], or 2. Ai is the median of the subarray [Ai+1,An-1].

If it is special, print 1, else print 0.

Example: Array is 3,6,8,4. This is special because 6 is the median of [8,4].

How to solve this problem?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just do a running median twice(once forward and once backward) and do a check.