You’re 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 i th ( 1 based index) element of the queue
Write a program to determine 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 the first segment.
Segment formation : You have 3 numbers 1, 2 and 3
The possible segments for 3 are , [3,2], [3,2,1]
The possible segments for 2 are , [2,1]
First line : Two space seperated integers N and K
Second line : N space seperated integers ( denoting the elements of the queue)
Next K lines is the value of X
N : represents the size of array
A : represents the array
K : represents the size of queries
Q : represents the queries
1 <= N,K <= 10^5
1 <= Each element of the queue <= 10^9
1 <= X <= N
Sample input 1
4 2 1 3
Sample output 1
Sample input 2
4 2 3 5 1
Sample output 2
I’ve solved this question by getting the number of consecutive smaller elements on the right and left side of the given index for each query.
But this approach takes O(N*K) time complexity and also 8/10 cases got TLE.
Can someone please suggest a better solution for this with lesser time complexity ?
public int solve(int N, int A, int K, int Q)
//Your solution here