Given an array A of size N, for each element A[i], I want to find all j such that A[j] > A[i]. Currently, I cannot think of a method better than O(i)(Traverse all 0 <= j < i and check). Is there an algorithm that achieves better time complexity than above? Space Complexity can be O(N)
Update 1
We can assume the array has distinct elements
Update 2
Let us consider array A = [4 6 7 1 2 3 5]. Let dom(i) = {j | 0 < j < i such that A[j] > A[i] }
- dom(0) = empty
- dom(1) = empty
- dom(2) = empty
- dom(3) = {0, 1, 2}
- dom(4) = {0, 1, 2}
- dom(5) = {0, 1, 2}
- dom(6) = {1, 2}
Also the space complexity of O(N) is meant to be per every iteration i
CodePudding user response：
Lower time complexity cannot be achieved, as, for example, if your array is all descending, all lists would have quadratic total length, so if your task is to get the lists, this is as fast as it can get. Your solution already achieves this O(N^2), so it already is optimal.
There are faster ways to calculate some things related to this, though. For example, if you are actually looking to get just the total count of all such pairs, it can be done in O(n ln n) time, see this post.