Walmart came in our college for hiring and there was only one coding problem in the first round which took place on Hackerearth. I wasn't able to sove the question, but I am really curious about how to solve this question. So, here goes the question:
TIME LIMIT PER TEXT CASE: 1 sec. You are given a 1-indexed array A with N integers. Find the index i such that 1 < i < N and difference between the number of integers greater than A[i] in the range 1 to i-1 and the number of integers lesser than A[i] in the range i+1 to N is maximum.
INPUT: First line contains a number N as input. Next line contains N space seperated integers.
OUTPUT: In the output you need to print the maximum absolute difference that is obtained.
CONSTRAINT: 3 <= N <= 10^5; 1 <= A[i] <= 10^9
SAMPLE INPUT 1: 4 1 4 2 7
SAMPLE OUTPUT 1: 1
EXPLANATION: If we choose value 2 i.e. the index 3 then total elements greater than 2 to its left side is 1 and total elements lesser than 2 to es nget e 0 so the difference is 1 which is the maximum in the array.
NOTE: I have written the exact question which was provided to us.
It can be solved by maintaining a multiset and adding element index by index and using lower or upper bound the number of elements greater or lesser can be appropriately calculated. Similarly, do the same in a new multiset by iterating the array in reverse order. Thus we know will have the the number of elements in greater/lesser for each index. Time Complexity is O(NlogN).
multiset doesn't come with random access iterators, that's why the time complexity will be O(n^2)
If in this way lower bound is used it takes O(logN) set1.lower_bound(val).
https://codeforces.net/blog/entry/48793
You are right that lower_bound will take O(logn).But we need to find the "position"(rank) of the iterator. you will have to use distance(set.begin(),it) which will make it O(n) .
Do you have any idea of what you are saying? Yes, lower_bound takes logn time but how would u use lower_bound to find number of elements greater/smaller than. It will just return the iterator. You can't do it — set.begin(), as unlike vectors/array the iterators are random.
Ever heard of ordered_set of policy-based data structures. You can easily find the number of elements greater/smaller than a particular number in logn time. Alternatively, you can also use a segment tree but coding it during a test won't be that easy.
Links to ordered_set(PBDS) if you don't know: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ , https://codeforces.net/blog/entry/11080
You can easily use a segment tree to count inversions. While the elements can be as large as 1e9, there are only 1e5 elements at max so you can use coordinate compression. The problem reduces to counting inversions for each element and taking the best result of the difference.
EDIT: I think you can also use two ordered sets, sweep the array from left to right while inserting elements into one ordered set. You can easily binary search to find the number of elements greater than or smaller than the element you're at. Then you can again sweep in the opposite direction, i.e from right to left and do the same for each element. Take the best difference.
Since the given array might contain duplicates, insert elements into the ordered set as pairs with different second values.
Note: I'm using zero-based indexing.
For a fixed index $$$i$$$ we have:
So, we need to sort the array of pairs $$$(A[i], i)$$$. The second term is equal to position of the corresponding pair in the sorted array. No data structures needed :)
you are in which college?
Looks like you can use two segment tree with coordinate compression, called 'left_seg' and 'right_seg'. As you iterate from 1 to N, update the 'left_seg' with everything to the left of i and 'right_seg' with everything to the right of i. You can do this in O(N) by deleting from 'right_seg' and adding to 'left_seg' while iterating. Then, you can simply query for sum of everything smaller/larger in O(logN), giving a complexity of O(NlogN).