Teaching Kids Programming – Line Sweeping Algorithm to Compute the Most Frequent Number in Intervals

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of list of integers intervals where each element contains the inclusive interval [start, end]. Return the most frequently occurring number in the intervals. If there are ties, return the smallest number.

Constraints
n ≤ 100,000 where n is the length of intervals

Example 1
Input

1 2 3 4 5 6

intervals = [     [1, 4],     [3, 5],     [6, 9],     [7, 9] ]

intervals = [
    [1, 4],
    [3, 5],
    [6, 9],
    [7, 9]
]

Output
3
Explanation
The most frequent numbers are [3, 4, 7, 8, 9] and they all occur twice but 3 is the smallest one.

Think of criteria for which an element will be maximum.i.e. how end points contribute it.

Compute the Most Frequent Number in Intervals via Line Sweeping Algorithm

We can process the intervals into a dictionary where keys are numbers (where) and the values are the change (offset). Then, we can scan/sweep from left to right, adapting to the changes. The accumulated value will be representing the number of numbers that are covered by intervals.

When we have a “most occuring” number, we update the answer and the counter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def mostFrequentNumberInIntervals(self, intervals):
        data = defaultdict(int)
        for i in intervals:
            data[i[0]] += 1
            data[i[1] + 1] -= 1
        c = most = 0
        ans = None
        for i in sorted(data.keys()):
            c += data[i]
            if c > most:
                most = c
                ans = i
        return ans

class Solution:
    def mostFrequentNumberInIntervals(self, intervals):
        data = defaultdict(int)
        for i in intervals:
            data[i[0]] += 1
            data[i[1] + 1] -= 1
        c = most = 0
        ans = None
        for i in sorted(data.keys()):
            c += data[i]
            if c > most:
                most = c
                ans = i
        return ans

The time complexity is O(NLogN) as we need to sort the keys of the dictionary which in worst case may be up to N keys. And the space complexity is also O(N) where we use a dictionary.

–EOF (The Ultimate Computing & Technology Blog) —