Paypal | Online Coding | SE1 question set

help
1

Query on Queues

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.

Example
Segment formation : You have 3 numbers 1, 2 and 3
The possible segments for 3 are [3], [3,2], [3,2,1]
The possible segments for 2 are [2], [2,1]

Input Format

  • 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

Function description

  • N : represents the size of array
  • A : represents the array
  • K : represents the size of queries
  • Q : represents the queries

Constrains

  • 1 <= N,K <= 10^5
  • 1 <= Each element of the queue <= 10^9
  • 1 <= X <= N

Sample Input

Sample input 1
4 2
4 2 1 3
1
4

Sample output 1
4
3

Sample input 2
5 2
4 2 3 5 1
1
3

Sample output 2
3
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
}
1 Like
2

I could not even get what the question says. Can you write in a more simplified way ?

1 Like
3

Check for this:

You can get the previous greater element in O(n) time for all the elements, using stacks as in article above. Then each query can be done in O(n) time.

Code needs some modification for next greater as well. Which can be done by making an array with reverse ordered elements.

4

@adibiit I too have tried with the similar thing. But all the test cases were not passed with this approach for my code. Could you please help me with the pseudocode ?

5

Sure, please share it and I will have a look.

6

@adibiit Could you please share your email ID. I will send it in a mail.

7

adityabiit52@gmail.com

8

okay , the exact question is asked here algorithm - Count segments where A[i] is rightmost or leftmost and is max - Stack Overflow

9

here you go , let me know if it is failing any test cases.

public class Paypal {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	int[] input = { 4,2,1,3 };
	int[] index = { 1, 4};
	int[] nxe = findNextGreaterElement(input, input.length);
	int[] nxeLeft = findNextGreaterElementFromRight(input, input.length);
	int[] result = solve(input, index, nxe, nxeLeft);
	System.out.println(Arrays.toString(result));
}

private static int[] solve(int[] input, int[] index, int[] nxe, int[] nxeLeft) {
	int i = 0;
	int[] result = new int[input.length];
	for (int in : index) {
		int leftseg = 0;
		int rigntseg = 0;
		in = --in;
		if (nxeLeft[in] == -1) {
			leftseg = in+1;

		} else {
			leftseg = in - nxeLeft[in];
		}
		if (nxe[in] == -1) {
			rigntseg = input.length-in;

		} else {
			rigntseg = nxe[in] - in;
		}
		result[i] = leftseg + rigntseg-1;
		i++;

	}

	// TODO Auto-generated method stub
	return result;
}

private static int[] findNextGreaterElementFromRight(int[] a, int n) {
	int[] ans = new int[n];
	Arrays.fill(ans, -1);
	LinkedList<Integer> st = new LinkedList();
	for (int i = a.length - 1; i >= 0; i--) {
		while (!st.isEmpty() && a[st.peek()] < a[i]) {
			ans[st.peek()] = i;
			st.pop();
		}
		st.push(i);
	}
	return ans;
}

static int[] findNextGreaterElement(int a[], int n) {
	int[] ans = new int[n];
	Arrays.fill(ans, -1);
	LinkedList<Integer> st = new LinkedList();
	for (int i = 0; i < a.length; i++) {
		while (!st.isEmpty() && a[st.peek()] < a[i]) {
			ans[st.peek()] = i;
			st.pop();
		}
		st.push(i);
	}
	return ans;
}

}

10

(this is the link for ur question read the editorial)