CODEWITHSUNDEEP
algorithmsearchoptimizationdata-structures
Gregory
Gregory

Reputation: 21

Best data structure to efficiently find high density interval

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?

Upvotes: 2

Views: 132

Answers (2)

skele
skele

Reputation: 93

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).

Upvotes: 0

orlp
orlp

Reputation: 117991

  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.

Upvotes: 2

Related Questions