Lack of Count Occurrences Algorithm

[ialimz]

Brief Intro

Algorithm doesn't work if occurrences are in different indexes

More Details

for example consider using this array:
let a = [ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11, 3]

In this case, the algorithm returns 4 yet.
This is because finding difference between upper and lower bounds only works if occurrences pushed continuously

[KartikSatoskar]

@ialimz
To work this solution effectively our array should be sorted. Hence, we can apply binary search to find left/right boundaries of given element in sorted array. As per input mentioned above, binary search can't be applied(since array is not sorted).

To solve this problem of unsorted array we have following approaches:

• Every time when new element gets added into array, blindly sort the array for safer side. But that would cost us extra O(NlogN) time complexity for every new element.

• Find correct insertion position for new element. That would cost us O(logN + N) time complexity.

Hope this clarifies your doubt.