Count segments where A[i] is rightmost or leftmost and is max

user_5785172 0
Viewed 1813

You are given an array containing N integers and you have to answer K queries. Each query contains an integer X which is the index of the (1 based index) element of the array.
Calculate the following for each query:

The number of segments containing the index X as the leftmost or the 
rightmost element and the number at the index `X` is `>=` each element
of that segment.

Segment formation example:
You have array {1, 2, 3}. The possible segments for 3 are [2,3] and [1,2,3] and [3].
The possible segments for 2 are [2] and [1,2]
I got solution by brute force. Worst case Time Complexity is O(n * k)

Input: Array[] = {4,2,1,3}, Queries[] = {1,4}
Output:  
4  
3

Explanation: 
For first query 1 all possible valid segments are [4], [4,2] , [4,2,1] and [4,2,1,3] 
hence answer is 4.  
For second query 4 all possible valid segments are [3], [1,3] and [2,1,3]
hence answer is 3.
data-structures algorithm
2 Answers

Preprocess two arrays in O(n), where the elements are the indexes of the next larger element for each element in the original array (one to the right and one to the left). Then answer each query in O(1).

user_20347870

For each query, follow steps:

  1. process from 0 to index (-1 as your query is 1 index based)in query
  2. process from index(-1) in query to N-1

While processing sub-arrays, check that the element at an index, say i should be less than or equal to element at index in your query. If yes, then you are safe to print it.

user_59649710
Related