Hello there! In this unit, we're presenting an exciting coding lesson that demonstrates the performance efficiencies offered by HashMap in Kotlin. We'll address a list-based problem that requires an optimal choice to minimize the size of our list. Excited? So am I! Let's dive in.

In this unit's task, we'll manipulate a list of integers. You are tasked with constructing a Kotlin function named minimalMaxBlock(). This function should accept a list as input and compute an intriguing property related to contiguous blocks within the list.

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

For example, consider the list listOf(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 listOf(1), listOf(3, 1, 4, 4, 4, 1), listOf(5), with the longest containing 6 elements. If we instead remove all instances of 1, the new remaining blocks would be listOf(2, 2, 3), listOf(4, 4, 4), listOf(2, 5), the longest of which contains 3 elements. Thus, the function should return 1 in this case, as it leads to a minimally maximal block length.

A straightforward way to tackle this problem is through a brute-force method. Test each possible value in the list by removing it and checking the resulting sub-list sizes. This approach involves iteratively stepping through the list for every possible value.

Kotlin
Copy to clipboard
1fun minimalMaxBlockBruteforce(list: List<Int>): Int {
2    var minMaxBlockSize = Int.MAX_VALUE
3    var minNum = -1
4
5    val uniqueElements = list.toSet()
6
7    for (num in uniqueElements) {  // Avoid duplicates
8        val indices = mutableListOf<Int>()
9        for (i in list.indices) {
10            if (list[i] == num) {
11                indices.add(i)
12            }
13        }
14        indices.add(0, -1)
15        indices.add(list.size)
16
17        var maxBlockSize = 0
18        for (i in 1 until indices.size) {
19            maxBlockSize = maxOf(maxBlockSize, indices[i] - indices[i - 1] - 1)
20        }
21
22        if (maxBlockSize < minMaxBlockSize) {
23            minMaxBlockSize = maxBlockSize
24            minNum = num
25        }
26    }
27
28    return minNum
29}

This method has a time complexity of O(n²) due to two nested loops: the outer loop cycling through each potential k value and the inner loop going over the list for each k value.

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

Before we delve into the steps of the optimized HashMap solution, let's understand its benefits in terms of time and space complexity compared to the brute-force approach.

1. Time Complexity: The HashMap solution requires only a single traversal of the list, with a linear time complexity of O(n), where n is the number of elements in the list. This is notably more efficient than the O(n²) complexity of the brute-force approach, where the list is traversed for each distinct number.

2. Space Complexity: The brute-force approach maintains a set of unique elements and an indices list for each element. While the indices list can have up to n elements for certain elements, the total space required for all indices combined is still n, leading to O(n) space complexity. Similarly, the HashMap solution maintains two maps for storing the last occurrence and maximum block size for each number. In a worst-case scenario with all unique elements, the space complexity is also O(n).

Let's proceed to the step-by-step implementation of the solution.

To find the number that, when removed from the list, would create several contiguous blocks minimizing the longest block length, we need to track each position of the same elements, determine the block size upon removal of each element, and note the maximum of these blocks.

Essentially, we don't store all positions — only the last occurrence is necessary, as we're interested in blocks between two adjacent identical elements, from the start of the list to the first occurrence, and between the last occurrence and the list's end.

Here's our plan:

• Initialize two maps: lastOccurrence will store the last index of each number, while maxBlockSizes will map each number to the maximum size of blocks formed when it is removed.

• Traverse the list from left to right and for each number:

  • If it's the first encounter, consider the block from the list's start up to its current position and store this size in maxBlockSizes.
  • If it has appeared before, calculate the block size formed (excluding itself) by subtracting the previous occurrence's index from the current index and subtracting 1. Update maxBlockSizes if this size exceeds the current maximum.
  • Store the current index as the last occurrence of this number.

• Post traversal, calculate the "tail block" size (i.e., the block from the last occurrence of a number to the list's end) and update maxBlockSizes if necessary.

• Identify the number yielding the smallest maximum block size and return it.

To initialize the HashMap structures in Kotlin, you can use mutableMapOf().

Kotlin
Copy to clipboard
1fun minimalMaxBlock(list: List<Int>): Int {
2    val lastOccurrence = mutableMapOf<Int, Int>()
3    val maxBlockSizes = mutableMapOf<Int, Int>()

Use Kotlin's list functionalities to iterate and process each number in the sequence.

Kotlin
Copy to clipboard
1    for ((i, num) in list.withIndex()) {
2        if (!lastOccurrence.containsKey(num)) {
3            maxBlockSizes[num] = i
4        } else {
5            val blockSize = i - lastOccurrence[num]!! - 1
6            maxBlockSizes[num] = maxOf(maxBlockSizes[num]!!, blockSize)
7        }
8        lastOccurrence[num] = i
9    }

For each element managed during traversal, ensure you measure the size of the "tail block."

Kotlin
Copy to clipboard
1    for ((num, pos) in lastOccurrence) {
2        val blockSize = list.size - pos - 1
3        maxBlockSizes[num] = maxOf(maxBlockSizes[num]!!, blockSize)
4    }

Finally, identify the number with the smallest maximum block size within maxBlockSizes and return it.

Kotlin
Copy to clipboard
1    var minNum = -1
2    var minBlockSize = Int.MAX_VALUE
3    for ((num, blockSize) in maxBlockSizes) {
4        if (blockSize < minBlockSize) {
5            minBlockSize = blockSize
6            minNum = num
7        }
8    }
9    return minNum
10}

Here's the combined solution using Kotlin:

Kotlin
Copy to clipboard
1fun minimalMaxBlockBruteforce(list: List<Int>): Int {
2    var minMaxBlockSize = Int.MAX_VALUE
3    var minNum = -1
4
5    val uniqueElements = list.toSet()
6
7    for (num in uniqueElements) { 
8        val indices = mutableListOf<Int>()
9        for (i in list.indices) {
10            if (list[i] == num) {
11                indices.add(i)
12            }
13        }
14        indices.add(0, -1)
15        indices.add(list.size)
16
17        var maxBlockSize = 0
18        for (i in 1 until indices.size) {
19            maxBlockSize = maxOf(maxBlockSize, indices[i] - indices[i - 1] - 1)
20        }
21
22        if (maxBlockSize < minMaxBlockSize) {
23            minMaxBlockSize = maxBlockSize
24            minNum = num
25        }
26    }
27    return minNum
28}
29
30fun minimalMaxBlock(list: List<Int>): Int {
31    val lastOccurrence = mutableMapOf<Int, Int>()
32    val maxBlockSizes = mutableMapOf<Int, Int>()
33
34    for ((i, num) in list.withIndex()) {
35        if (!lastOccurrence.containsKey(num)) {
36            maxBlockSizes[num] = i
37        } else {
38            val blockSize = i - lastOccurrence[num]!! - 1
39            maxBlockSizes[num] = maxOf(maxBlockSizes[num]!!, blockSize)
40        }
41        lastOccurrence[num] = i
42    }
43
44    for ((num, pos) in lastOccurrence) {
45        val blockSize = list.size - pos - 1
46        maxBlockSizes[num] = maxOf(maxBlockSizes[num]!!, blockSize)
47    }
48
49    var minNum = -1
50    var minBlockSize = Int.MAX_VALUE
51    for ((num, blockSize) in maxBlockSizes) {
52        if (blockSize < minBlockSize) {
53            minBlockSize = blockSize
54            minNum = num
55        }
56    }
57    return minNum
58}
59
60fun main() {
61    val list = listOf(1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5)
62
63    // Timing brute force method
64    val startTimeBruteForce = System.nanoTime()
65    val bruteForceResult = minimalMaxBlockBruteforce(list)
66    val endTimeBruteForce = System.nanoTime()
67    val durationBruteForce = endTimeBruteForce - startTimeBruteForce
68
69    // Timing optimized method
70    val startTimeOptimized = System.nanoTime()
71    val optimizedResult = minimalMaxBlock(list)
72    val endTimeOptimized = System.nanoTime()
73    val durationOptimized = endTimeOptimized - startTimeOptimized
74
75    // Output results
76    println("Brute Force Result: $bruteForceResult")
77    println("Brute Force Time: $durationBruteForce nanoseconds")
78
79    println("Optimized Result: $optimizedResult")
80    println("Optimized Time: $durationOptimized nanoseconds")
81}

Great job! This lesson provided a comprehensive overview — we revisited the concept of HashMap, explored how they optimize program performance, and constructed a function to discover a specific number in a list that minimizes the maximum block size upon removal.

Having mastered the basics, the logical next step is to apply your newly acquired skills. In the upcoming practice session, you'll face intriguing challenges that delve further into HashMap, list manipulation, and innovative optimizations using Kotlin. Prepare yourself and let’s dive in!