Welcome! In this lesson, we're going to explore the performance efficiencies offered by utilizing Ruby's Hash. We will tackle an array-based problem requiring us to choose an optimal strategy to minimize the size of our array. Excited to dive in? Let's get started!

Our task is to manipulate an array of integers. You are required to construct a Ruby method titled minimal_max_block. This method should accept an array as input and examine an interesting property related to contiguous blocks within that array.

Specifically, you have to select a particular integer, k, from the array. Once you've selected k, the method should remove all occurrences of k from the array, resulting in multiple contiguous blocks, or sub-arrays. The unique feature of k is that it is chosen such that the maximum length among these blocks is minimized.

For example, consider the array [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], with the longest containing 3 elements. Hence, the method should return 1 in this case, as it leads to a minimal maximum block length.

A straightforward way to address this problem is via a brute force method. Each value in the array can be tested by removing it and examining the sizes of the resulting sub-arrays.

def minimal_max_block_bruteforce(arr)
  min_max_block_size = Float::INFINITY
  min_num = nil

  arr.uniq.each do |num|  # Avoid duplicates.
    indices = arr.each_index.select { |i| arr[i] == num }  # Indices where 'num' appears.
    indices.unshift(-1).push(arr.length)  # Add artificial indices at the ends.
    max_block_size = indices.each_cons(2).map { |x, y| y - x - 1 }.max  # Calculate max block size.

    if max_block_size < min_max_block_size
      min_max_block_size = max_block_size
      min_num = num
    end
  end

  min_num
end

This approach is $O(n^2)$ in time complexity because it involves two nested loops: one iterating through each potential k value and another scanning the array for each of these k values. As n increases, this approach becomes impractical for large datasets, demonstrating a need for optimization.