CODEWITHSUNDEEP
python-3.xsortingdata-structures
staceyask
staceyask

Reputation: 45

Efficient Way to find count of value in list within an upper and lower bound

Given a large unordered list with duplicates, how do I find the the count of values in the list that lie between the lower and upper bound, inclusive with a good time and space complexity? Will be great if there's an explanation in python. Looking for a O(nlog(n)) approach

Sample input
5 # number of elements in unordered list
2 4 98 3 100 # unordered list. values in list from 1 to 10 ^7
4 # number of subsequent bounds as input
99 101 # left is lower bound right is upper bound
1 5
100 100
2 2

Sample output
1 # 1 number in list between 99 and 101 inclusive
3 # 3 numbers in list between 1 and 5 inclusive
1
1

Upvotes: 0

Views: 464

Answers (2)

staceyask
staceyask

Reputation: 45

Solved it in python

  • Merged sort the list
  • Used binary search (bisect library)

Upvotes: 0

Olivolja
Olivolja

Reputation: 51

Unsure if this is what you are looking for but in order to find the count, in a interval of a list you could do something similar to the following:

list[start:stop].count(element)

Upvotes: 1

Related Questions