The Lucky Employee · Coding Gym

See the original problem on HackerRank.

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them?

Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation.

The lottery will work this way:

Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \),
a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges,
if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time

You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm.

Input Format

The first line contains \( N \), denoting the number of ranges,
each of the following \( N \) lines contains two numbers \( L_i \) and \( R_i \), denoting the beginning and the ending of the range.

Note: range endings are inclusive (e.g. \( [1, 5] \) means \( 1, 2, 3, 4, 5 \)).

Constraints

\( 1 \leq N \leq 1'000'000 \)
\( 0 \leq L_i < 99'998 \)
\( L_i < R_i \leq 100'000 \)

Output Format

A single integer, denoting the most frequent id in all the ranges.

Solutions

The naive solution consists in calculating the frequencies of all the elements by traversing every interval from \( L_i \) to \( R_i \). Afterwards we just calculate the maximum frequency. In the worst case the time complexity of this algorithm is \( O(N*MaxDomain) \). If \( MaxDomain=N \) the algorithm is quadratic.

Linear solution with \( O(MaxDomain) \) extra space

The idea of calculating the frequencies of all the elements is not bad, we need to calculate them efficiently though. We should “compress” the information contained into a range and “expand” it later.

Suppose we keep track of the frequencies into a static array of \( MaxDomain \) (e.g. 100'000) elements:

1

array<int, MaxDomain> freq{}; // or int freq[MaxDomain]{};

\( freq[i] \) is the number of times \( i \) appears.

For instance:

The first 10 (0 is included) elements of \( freq \) are:

1
2
3


0 1 2 3 4 5 6 7 8 9
___________________
0 2 3 3 2 1 0 0 1 1

Reading \( 1,5 \) we just need to save the information that all the numbers from \( 1 \) to \( 5 \) are included, without dumping all such numbers into \( freq \). We just need to “save” that \( 1 \) starts the range and that \( 5 \) ends it.

We need some imagination.

Intuitively, every \( L \) adds \( +1 \) to the frequency of the next elements until the end is reached, that is \( R+1 \) (because \( R \) is included). On the other hand, the frequency of the numbers following \( R+1 \) mustn’t be affected by such increment. Mathematically, we roll-back \( +1 \) with \( -1 \).

Maybe you already see the point:

we iterate over all the pairs \( L_i, R_i \)
we add \( 1 \) to \( freq[L_i] \) and we subtract \( 1 \) to \( freq[R_i+1] \)

We have compressed the information contained in all the ranges. Then it’s time to “expand” it to calculate the most frequent element.

Conceptually, it’s just the matter of “propagating” all the \( +1 \) and \( -1 \) that we have accumulated. This is a prefix sum, or the cumulative sum of the elements.

Applying the idea to our test case above:

First step:

1
2
3


0  1  2  3  4  5  6  7  8  9  10
________________________________
0  2  1  0  -1 -1 -1 0  1  0  -1

Second step:

1
2
3


0  1  2  3  4  5  6  7  8  9  10
________________________________
0  2  3  3  2  1  0  0  1  1  0

This array contains the frequencies of all the elements! The third step is simply to calculate the maximum.

Actually, we can merge the second and the third step into one, by accumulating the maximum along the way.

In code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


constexpr size_t MaxDomain = 1'000'000;

int main()
{
    int N, L, R; cin >> N;
    array<int, MaxDomain + 1> freq{};

    for (auto i=0; i<N; ++i)
    {
        cin >> L >> R;
        freq[L] += 1;
        freq[R + 1] -= 1;
    }

    int maxSum = freq[0];
    size_t mostFrequent = 0;
    for (auto i=1u; i<freq.size(); ++i)
	{
        freq[i] += freq[i - 1];
        if (maxSum < freq[i])
        {
            maxSum = freq[i];
            mostFrequent = i;
        }
    }

    cout << mostFrequent;
}

Just for completeness, here is a version written in terms of the patterns found: prefix sum and maximum:

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


constexpr size_t MaxDomain = 1'000'000;

int main()
{
    int N, L, R; cin >> N;
    array<int, MaxDomain + 1> freq{}; // 0 1'000'000 included

    for (auto i=0; i<N; ++i)
    {
        cin >> L >> R;
        freq[L] += 1;
        freq[R + 1] -= 1;
    }

    partial_sum(begin(freq), end(freq), begin(freq));
    cout << distance(begin(freq), max_element(begin(freq), end(freq)));
}

Although the latter solution performs the prefix sum and the maximum in two different iterations, the algorithm is parallelizable by design (for completeness: in C++17 we can just pass an additional first parameter to let the library run partial_sum and max_element in parallel/vectorized mode).

Pros of this solution:

if we need the complete ranking of numbers, we have it;
if we need to calculate the biggest maximum, it’s just the matter of reversing the iteration when we call max_element.

Cons of this solution:

it does not scale well if MaxDomain grows too much, since a full allocation is needed;
it’s very likely we end up having a bunch of zeros in freq, that we cannot ignore.

The next solution takes the cons into account, even if the final solution is computationally slower.

Amortized extra space

You have probably observed that the most occurent element is always at the boundaries of a particular range, haven’t you? This means we could tecnically ignore all the elements in the middle. They are redundant.

The algorithm is not so different from the first one we have showed before. Instead of using an array as big as MaxDomain, we use a (sorted) map - e.g. std::map or Java’s TreeMap. The sorting property is crucial.

The first step of the algorithm is the same as before. The second is slightly different just because we do not perform a true prefix sum, instead we just calculate the cumulative sum and the maximum along the way by adding the frequency of the current element at every step. The C++ code can be easily translated into other languages:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


int main()
{
    int N, L, R; cin >> N;
    map<int, int> freq;

    for (auto i=0; i<N; ++i)
    {
        cin >> L >> R;
        freq[L]++;
        freq[R + 1]--;
    }

    int maxSum = 0, mostFrequent, running=0;
    for (const auto& elem : freq)
    {
        running += elem.second;
        if (maxSum < running)
        {
            maxSum = running;
            mostFrequent = elem.first;
        }
    }

    cout << mostFrequent;
}

From a computational point of view we pay:

\( O(N \cdot logN) \) to fill the frequency table
\( O(N) \) for cumulative sum/maximum

The latter point is amortized in space but it could be slower than the algorithm using an array because of the nature of the data structure: ordered maps are generally binary trees which are less memory (and cache) friendly than arrays. Iterating over trees is generally less efficient than iterating on arrays. So, don’t be surprised if you measure that this code is very slower than the other, even if the map size is smaller!

Anyway, this can be a good compromise if you cannot afford the memory usage of the first algorithm.

Other data structures can be investigated - e.g. flat map.

Sort-based solution

Another interesting solution based on sorting has been proposed by Antonio D’Angelico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


int main()
{
    int N, l, r;
    vector<int> L, R, A;

    cin >> N;
    for (int i = 0;i < N; ++i)
    {
        cin >> l >> r;
        L.push_back(l);
        A.push_back(1);
        R.push_back(r);
    }
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    int j = 0;
    for (int i = 1;i < N; ++i)
    {
        A[i] += A[i - 1];
        while (R[j] < L[i])
        {
            A[i]--;
            if (j < N)
                j++;
        }
    }
    j = max_element(A.begin(), A.end()) - A.begin();
    cout << L[j];
}

Another solution based on sort, using only two arrays, as proposed by nigro_fra:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        final int n = Integer.parseInt(scan.nextLine());
        int max = 0;
        int id = 0;
        int[] begin = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            final String[] pairs = scan.nextLine().split(" ");
            final int b = Integer.parseInt(pairs[0]);
            final int e = Integer.parseInt(pairs[1]);
            begin[i] = b;
            end[i] = e;
        }

        Arrays.sort(begin);
        Arrays.sort(end);

        for (int i = 0, j = 0; i < begin.length; i++) {
            if (end[j] < begin[i]) {
                while (end[j] < begin[i]) {
                    j++;
                }
                j--;
            }

            int sum = i - j;
            if (sum > max) {
                max = sum;
                id = begin[i];
            }
        }

        System.out.println(id);
    }
}