-3

I asked this question earlier and it was closed because it needed more clarification:

Performance: The solution of the problem is checked for correctness and performance, a 50% performance means that the algorithm is not that great and that it could be done in a better way.

If anything is not clear can you please let me know what I should fix.

If I am given an array of length T of length N, that contains all numbers from 1 to N, (The array should not have duplicates).

If at any given (i) position in the array. The number at position (k), is preceded by all its previous numbers for i < k, we increment a counter to count how many times did that happened. (if let's say there is a 3 at position 4, we must have encountered 1,2,3 earlier) if the array is equal to T = {2,1,5,3,4} it should return a 3 as as T[1] = 1, 1 doesn't have a predecessor, and T[3] = 3, Its predecessors are 2 and 1 and they appear before it. same thing for T[4] = 4

if the array is equal to T = {2,3,4,1,5} it should return a 2 as as T[3] = 1, and T[4] = 5

The obvious solution is O(n^2) whit a nested loops

A better solution is O(n) using the formula of the sum n(n+1)/2

But even with an O(n) the performance was still 50%.

Do you see any better way to solve it?

Also in the previous post, some people voted down because they said: The example "if lets say there is a 3 at position 4, we must have encountered 1,2,3 earlier" makes no sense, if a number can't be repeated.

Well to answer this here is an example: [2,1,4,3]

MohamedTa
  • 1
  • 1
  • Can someone explain me why it is voted down. Do I need to change something. What's unclear about it ? – MohamedTa Nov 07 '19 at 05:24
  • @HighPerformanceMark Realy I already solved it with O(n) what do you mean I did not attempt it? I asked if someone can think of any other way other than O(n) – MohamedTa Nov 09 '19 at 01:36

1 Answers1

1

Keep integer ranges, for example, in interval tree or in disjoint-set data structure, or in bitset. In the lasr cases every set (sequence of 1-bits) also should contain additional fields - min and max elements.

For every element:

When value K is met, try to join it to the set containing K-1.

If such set exists and has min element 1, you can increment counter. Now max element of this set is K. If there is no such set, form new one with single element.

Try to join the last set (either single-element, or large one) with the set containing K+1.

Edit: also look at hash table approach here

MBo
  • 77,366
  • 5
  • 53
  • 86