Circular Array

/*
 * Problem description: https://ibb.co/N2cnXG1
 */
/*
 * 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;
}