CODEWITHSUNDEEP
c++algorithmmemory-managementstl
yobro97
yobro97

Reputation: 1145

More memory efficient algorithm for finding overlap in ranges

In this question, the answer included an algorithm to find overlap of a list of ranges on a given range. But in my situation I have a list of n integers, which when grouped into n^2 pairs form ranges. For example if we take array[i] and array[j] from the integer array, (array[i]-array[j],array[i]+array[j]) make a range. But in order to implement the suggested algorithm, the solution is of O(n^2) memory complexity. Can it be optimized (in terms of memory) further?

Example: I have a larger range (l,r), and I have to find how many integers in (l,r) lie in at least any one of the list of ranges.For example, the given integer array is {1,2,3}. So all possible ranges are (2-1,1+2), (3-1,1+3), (3-2,3+2). Suppose (l,r) is (2,7). Then since (2,5) exist in at least one of them 4 is the answer.

Upvotes: 1

Views: 170

Answers (1)

user3386109
user3386109

Reputation: 34829

Start by sorting the array (if it isn't already sorted). Then note that the only ranges worth considering are those where j == i-1.

To understand why consider the following array:

{2,3,5,8}

Then the possible ranges are:

i=3 j=2 ==> (8-5,8+5) = (3,13)
i=3 j=1 ==> (8-3,8+3) = (5,11)
i=3 j=0 ==> (8-2,8+2) = (6,10)

i=2 j=1 ==> (5-3,5+3) = (2,8)
i=2 j=0 ==> (5-2,5+2) = (3,7)

i=1 j=0 ==> (3-2,3+2) = (1,5)

Notice that the ranges for j < i-1 are always strict subsets of the range where j == i-1, so those ranges don't need to be considered. So you only need to consider O(n) ranges.

Upvotes: 2

Related Questions