1

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] }

  1. dom(0) = empty
  2. dom(1) = empty
  3. dom(2) = empty
  4. dom(3) = {0, 1, 2}
  5. dom(4) = {0, 1, 2}
  6. dom(5) = {0, 1, 2}
  7. dom(6) = {1, 2}

Also the space complexity of O(N) is meant to be per every iteration i

punter147
  • 302
  • 2
  • 7
  • 1
    If you have a sorted list (ascending) then for each A[i] you will have the set of j in [i+1...N]. That means the output size is O(N²), and space complexity of O(N) is impossible. Please clarify. It would be good to provide an example with input and expected output. – trincot Feb 11 '22 at 19:52
  • @trincot Apologies for not being clear. It is updated now. A is not necessarily sorted. – punter147 Feb 11 '22 at 20:20
  • So are you looking for a function that takes two inputs: `A` and `i`, and produces a set, or are you looking for a function that takes one input: `A` and produces all sets for all possible `i`? If the latter, it is odd that you speak of a space complexity per iteration, as that is irrelevant. Space complexity should be about the complete task. – trincot Feb 11 '22 at 20:28
  • 1
    @trincot apologies again. The space complexity of the algorithm for all possible i (basically, for the whole problem) should be O(N^2). And i am looking for the latter function. – punter147 Feb 11 '22 at 20:45
  • 1
    I think the O(n) extra space is for an array of indexes, e.g. `B = [0 1 2 3 4 5 6]`. Or you can convert A to an array of tuples, e.g. `A = [(4,0) (6,1) (7,2) (1,3) ...]` Then you can treat the problem just like an insertion sort. That might make the algorithm run a little faster on average, but the time complexity is still O(n^2), because the output size is O(n^2). – user3386109 Feb 11 '22 at 21:50
  • @user3386109 Thanks for the tip! I guess there is no better way than O(N^2) in terms of time and space complexity. – punter147 Feb 12 '22 at 04:39

1 Answers1

2

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.

Roman Svistunov
  • 1,069
  • 6
  • 11