Best data structure to efficiently find high density interval

user_14036226 0
Viewed 78

I have an unsorted set of integers and an interval length. I need to find the largest subset of elements included in a given interval

Example 1:

Set: [11, 1, 2, 100, 12, 14, 99]

Interval: 4

Result: [11, 12, 14]

Example 2:

Set: [1, 100, 55, 2, 88, 3]

Interval: 10

Result: [1, 2, 3]

In practice, there are many more elements in the set

What is the efficient data structure and algorithm for solving this problem?

data-structures search optimization algorithm
2 Answers

  1. Sort the set of integers into an array A and let w be the width of our interval.

  2. Initialize i = j = best_start = best_n = 0.

  3. Increment j as long as A[j] < A[i] + w (or <= depending on how you define an interval).

  4. If j - i > best_n set best_start = i and best_n = j - i.

  5. Increment i = i + 1 and if i, j < length(A) go back to 2.

Total complexity is dominated by the initial sorting complexity, O(n log n). After the sorting notice that complexity must be linear since j < n can only increase and we do a constant amount of stuff at each step.

user_5656350

You should first sort the array( O(N) * log(N)), then traverse the array from the begin keeping the interval. if the current number exceeds the interval, store that array. you can update the storage if you find bigger subset.

The time complexity of this algorithm will be O(N)* log(N) + O(N), roughly 2 * O(N). The space complexity will be O(N).

user_139670550
Related