Performance Optimization with Unordered Maps in C++

Hello there! In this unit, we're offering an engaging coding lesson that highlights the performance efficiencies offered by the utilization of std::unordered_map in C++. We'll address a vector-based problem that requires us to make an optimal choice to minimize the size of our vector. Excited? So am I! Let's get started.

In this unit's task, we'll manipulate a vector of integers. You are required to construct a C++ function titled minimal_max_block(). This function should accept a vector as an input and compute an intriguing property related to contiguous blocks within the vector.

More specifically, you must select a particular integer, k, from the vector. Once you've selected k, the function should remove all occurrences of k from the vector, thereby splitting it into several contiguous blocks or remaining sub-vectors. A unique feature of k is that it is chosen such that the maximum length among these blocks is minimized.

For instance, consider the vector {1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5}. If we eliminate all instances of 2 (our k), the remaining blocks would be {1}, {3, 1, 4, 4, 4, 1}, {5}, with the longest containing 6 elements. Now, if we instead remove all instances of 1, the new remaining blocks would be {2, 2, 3}, {4, 4, 4}, {2, 5}, the longest of which contains 3 elements. As such, the function should return 1 in this case, as it leads to a minimally maximal block length.

An initial way to approach this problem can be through a brute force method. Each possible value in the vector could be tested in turn by removing it from the vector and then checking the resulting sub-vector sizes. This approach entails iteratively stepping through the vector for each possible value in the vector.

#include <vector>
#include <unordered_set>
#include <limits>
#include <algorithm>

int minimal_max_block_bruteforce(const std::vector<int>& vec) {
    int min_max_block_size = std::numeric_limits<int>::max();
    int min_num = -1;

    std::unordered_set<int> unique_elements(vec.begin(), vec.end());

    for (int num : unique_elements) {  // Avoid duplicates.
        std::vector<int> indices;
        for (size_t i = 0; i < vec.size(); ++i) {
            if (vec[i] == num) {
                indices.push_back(i);
            }
        }
        indices.insert(indices.begin(), -1);
        indices.push_back(vec.size());

        int max_block_size = 0;
        for (size_t i = 1; i < indices.size(); ++i) {
            max_block_size = std::max(max_block_size, indices[i] - indices[i - 1] - 1);
        }

        if (max_block_size < min_max_block_size) {
            min_max_block_size = max_block_size;
            min_num = num;
        }
    }

    return min_num;
}

This method has a time complexity of O(n^2), as it involves two nested loops: the outer loop cycling through each potential k value and the inner loop sweeping through the vector for each of these k values.

However, this approach becomes increasingly inefficient as the size n of the vector grows, due to its quadratic time complexity. For larger vectors or multiple invocations, the computation time can noticeably increase, demonstrating the need for a more efficient solution.