Solution to most visited node in a circular array in O(n)

circular_array.cpp

#include <vector>
#include <iostream>
#include <map>
#include <tuple>
#include <unordered_map>

using namespace std;

/*
 * Problem description: https://ibb.co/N2cnXG1
 * This is basically my thought flow from BruteForce->Solution1->Solution2->Solution3->Solution4
 */

/*
 * It's a circular array, for each pair [endNode[i],endNode[i+1]] 0 < i < m-1 we
 * visit all nodes from endNode[i] to endNode[i+1] by incrementing count inclusive.
 * If endNode[i+1] < endNode[i] it means it a circular path so we traverse so
 * we visit both [endNode[i], n] and [1, to endNode[i+1]]
 * Finally we iterate from 1 to n to find the most visited node also it needs to be smallest
 *
 * Time Complexity O(|n|*m), Space Complexity O(|n|)
 */
int circularArrayBruteForce(int n, vector<int> endNode) {
    vector<int> count(n + 1);
    for (int i = 0; i < endNode.size() - 1; i++) {
        int start = endNode[i];
        int end = endNode[i + 1];

        //if the range is in middle of the array
        if (start <= end) {
            for (int j = start; j <= end; j++)
                count[j]++;
        } else {  // if the range is composed of the tail and head
            for (int j = start; j <= n; j++)
                count[j]++;
            for (int j = 1; j <= end; j++)
                count[j]++;
        }
    }

    int max = 0, most = 0;
    for (int i = 1; i <= n; i++) {
        if (max < count[i]) {
            max = count[i];
            most = i;
        }
    }
    return most;
}

/*
 * We turn endNode into ranges keeping track of starts and ends separately.
 * We can think split circular ranges into two ranges [i, j] i>j -> [i,n][1,j]
 * the same way as brute force approach.
 *
 * Then we look for most deepest overlapping range. We use two pointer left and right.
 * When starts[right] <= ends[left] it implies that we hit an overlap otherwise we increment left
 * The window size just grows so when starts[right] <= ends[left] it means that we have hit the
 * deepest overlap so 'most' 1. the most visited node 2. the smallest node in the most visited nodes
 *
 * Time Complexity O(m*log(m)), Space Complexity O(m)
 */
int circularArray1(int n, vector<int> endNode) {
    int m = endNode.size();
    vector<int> starts, ends;
    for (int i = 0; i < m - 1; i++) {
        auto start = endNode[i];
        auto end = endNode[i + 1];
        starts.push_back(start);
        ends.push_back(end);
        if (start > end) {
            starts.push_back(1);
            ends.push_back(n);
        }
    }

    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int most = 0;
    for (int left = 0, right = 0; right < starts.size(); right++) {
        if (starts[right] <= ends[left]) {
            most = starts[right];
        } else {
            left++;
        }
    }

    return most;
}
/*
 * The same as solution1 except:
 * 1. We do not need to add n to ends, if n is end range, n will never be selected
 * 2. We do not need to add 1 to start but we should set most=1 as default value
 */
int circularArray2(int n, vector<int> endNode) {
    int m = endNode.size();
    vector<int> starts, ends;
    for (int i = 0; i < m - 1; i++) {
        auto start = endNode[i];
        auto end = endNode[i + 1];
        starts.push_back(start);
        ends.push_back(end);
    }

    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int most = 1;
    for (int left = 0, right = 0; right < starts.size(); right++) {
        if (starts[right] <= ends[left]) {
            most = starts[right];
        } else {
            left++;
        }
    }

    return most;
}
/*
 * We do not need two extra arrays since starts as these two arrays are almost the same
 * except in two elements, 'starts' misses nodeList[m - 1] and 'ends' misses nodeList[0]. We can use
 * a single array (or even endNode itself) to perform the same algorithm but we need to take care
 * of missing elements. In case of endNode[right] == end we ignore the iteration only once and
 * in case of endNode[left] = start we increment last by one once. We should be careful to ignore
 * start and end only once as there might be duplicates of start and end in the array.
 *
 * Time Complexity O(m*log(m)), Space Complexity O(1)
 */
int circularArray3(int n, vector<int> endNode) {
    int m = endNode.size();
    int start = endNode[0], end = endNode[m - 1];

    sort(endNode.begin(), endNode.end());

    int most = 1;
    bool skipStartOnce = false, skipEndOnce = false;
    for (int right = 0, left = 0; right < endNode.size(); right++) {
        // ignore start on the left side
        if (!skipEndOnce && endNode[left] == start) {
            skipEndOnce = true;
            left++;
        }
        // ignore end on the right side
        if (!skipStartOnce && endNode[right] == end) {
            skipStartOnce = true;
            continue;
        }
        if (endNode[right] <= endNode[left]) {
            most = endNode[right];
        } else {
            left++;
        }
    }
    return most;
}

/*
 * If we look at this code snippet from solution3 code
 *   for (int right = 0, left = 0; right < endNode.size(); right++) {
 *      ...
 *      if (endNode[right] <= endNode[left]) {
 *           most = endNode[right];
 *       } else {
 *           left++;
 *       }
 *   }
 *   We notice that we are basically selecting the most frequent item here.
 *   So similar results can be achieved with maps and counting without sorting in O(n)
 *   But there are two problems:
 *   1. if (!skipEndOnce && endNode[left] == start) {
 *           skipEndOnce = true;
 *           left++;
 *      }
 *
 *       Which basically shrinks the window once we hit endNode[left] == start.
 *
 *       endNode ASAAAAAAA             ASAAAAAAA
 *       window   <---->      =>         <--->
 *       (A: some element, S: start, the element one the left side that we want to ignore)
 *       As you can see we have expanded the window by 1 so that means that every element after
 *       appearance of S the gets one score more to be selected as the most frequent item.
 *       In the counting approach we can increment all the items that appear after start by 1
 *
 *
 *
 *  2.   if (!skipStartOnce && endNode[right] == end) {
 *           skipStartOnce = true;
 *           continue;
 *       }
 *       Which basically expands the window for values larger or equal to end os we increment
 *       the count map by one the same way.
 *
 *       endNode AAAAAAEAA             AAAAAAEAA
 *       window   <---->      =>         <----->
 *       (A: some element, S: start, the element one the left side that we want to ignore)
 *       As you can see we have shrinked the window by 1 so that means that every element after
 *       appearance of S the gets one score less to be selected as the most frequent item.
 *       In the counting approach we can decrement all the items that appear after start by 1
 *
 * Time Complexity O(m), Space Complexity O(m)
 */
int circularArray4(int n, vector<int> endNode) {
    int m = endNode.size();
    unordered_map<int, int> count;
    int start = endNode[0], end = endNode[m - 1];

    for (auto &e: endNode)
        count[e]++;

    for (auto &[k, _]: count) {
        if (k >= end)
            count[k]--;
        if (k > start)
            count[k]++;
    }

    int max = 0, most = 1;
    for (auto &[k, v]: count) {
        // we are dealing with unsorted map so we need to
        // make sure we select the smallest item in the group
        if (max < v || max == v && most > k) {
            max = v;
            most = k;
        }
    }
    return most;
}

/*
 * Random test case generator
 */
tuple<int, vector<int>> randomTestCase(int upper) {
    int n = random() % upper + 1;
    int m = random() % upper + 2;

    vector<int> endNode;
    for (int i = 0; i < m; i++) {
        endNode.push_back(random() % n + 1);
    }

    return make_tuple(n, endNode);
}

int main() {
    vector<tuple<int, vector<int>>> testCases{
            {2,        {1, 2}},
            {3,        {1, 3, 2,  3}},
            {3,        {2, 1}},
            {3,        {1, 3, 2}},
            {4,        {2, 4, 3}},
            {5,        {2, 5, 3,  4}},
            {5,        {5, 4, 3,  2}},
            {5,        {2, 3, 4,  5}},
            {10,       {3, 6, 9,  2}},
            {3,        {3, 2}},
            {5,        {3, 4, 1}},
            {10,       {1, 5, 10, 5}},
            {10,       {1, 2, 3,  5, 2, 3, 2, 3, 2}},
            {100,      {1, 2, 3,  5, 2, 3, 2, 3, 2}},
            {5,        {1, 2, 3,  5, 2, 3, 2, 3, 2}},
            {5,        {1, 2}},
            {5,        {1, 2, 4}},
            {99999999, {1, 2, 1,  2, 1, 2, 1, 2, 1}},
            {10,       {1, 4, 5,  6, 7}},
            {10,       {1, 4, 5,  6, 7, 1}},
            {
             10,       {1, 4, 5,  6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5,
                               6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1,
                               1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1, 1, 4, 5, 6, 7, 1}
            }

    };

    vector<tuple<string, int (*)(int, vector<int>)>> solutions{
            {"BruteForce", circularArrayBruteForce},
            {"Solution1", circularArray1},
            {"Solution2", circularArray2},
            {"Solution3", circularArray3},
            {"Solution4", circularArray4},
    };

    int w = 10;
    for (auto &[name, _]: solutions) {
        cout.width(w);
        cout << name;
        cout.width(w);
        cout << "Time";
    }

    cout.width(w);
    cout << "N";
    cout.width(w + 4);
    cout << "endNode";
    cout << endl;

    for (auto &[n, endNode]: testCases) {
        int last_result = -1;
        for (auto &[name, solution]: solutions) {
            auto t1 = std::chrono::high_resolution_clock::now();
            int result = solution(n, endNode);
            auto t2 = std::chrono::high_resolution_clock::now();

            if (last_result != -1)
                assert(result == last_result);
            last_result = result;

            cout.width(w);
            cout << result;
            cout.width(w);
            cout << chrono::duration_cast<chrono::microseconds>(t2 - t1).count();;
        }
        cout.width(w);
        cout << n;
        cout.width(4);
        for (auto &n: endNode)
            cout << n << ",";
        cout << endl;
    }
    cout << "Testing random test cases. ";
    for (int i = 0; i < 100; i++) {
        auto [n, endNode] = randomTestCase(10000);
        int lastResult = -1;
        for (auto &[name, solution]: solutions) {
            int result = solution(n, endNode);
            if (lastResult != -1) {
                assert(lastResult == result);
            }
            lastResult = result;
        }
    }
    cout << "Passed" << endl;
}

Very good solution and explanation

Thank you so much