How this can be solved faster than O(N^2) without using Binary indexed tree (O(NlogN), but Memory Out Limit)
arr = [6, 2, 3, 5, 1, 6], l = 5, h = 7
Find number of pairs i, j such that i < j && (arr[i] arr[j] >= l && arr[i] arr[j] <= r)
O(N^2) solution is very straight-forward, but TLE.
What I tried:
- Using Binary Indexed Tree, but get Memory Limit Exceeded.
Anyone has ideas?
CodePudding user response：
Sort the array in ascending order and, for each i, binary search (in (i , n]) the first j for which the first condition is true. Let it be j1. Then, binary search (again in (i, n]) the last j for which the second condition is true. Let it be j2. If everything is ok, add |j2 - j1 1| to the answer.
The overall time complexity is O(n * log n) and the memory complexity is O(n).