Using HashMap for Optimal List Manipulation and Analysis in Java

Introduction

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

Task Statement

In this unit's task, we'll manipulate a list of integers. You are required to construct a Java function titled minimalMaxBlock() . This function should accept a list as an 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 instance, consider the list {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.

Brute Force Approach

O(n^2)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Java

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlockBruteforce(List<Integer> list) {
        int minMaxBlockSize = Integer.MAX_VALUE;
        int minNum = -1;

        Set<Integer> uniqueElements = new HashSet<>(list);

        for (int num : uniqueElements) {  // Avoid duplicates.
            List<Integer> indices = new ArrayList<>();
            for (int i = 0; i < list.size(); ++i) {
                if (list.get(i) == num) {
                    indices.add(i);
                }
            }
            indices.add(0, -1);
            indices.add(list.size());

            int maxBlockSize = 0;
            for (int i = 1; i < indices.size(); ++i) {
                maxBlockSize = Math.max(maxBlockSize, indices.get(i) - indices.get(i - 1) - 1);
            }

            if (maxBlockSize < minMaxBlockSize) {
                minMaxBlockSize = maxBlockSize;
                minNum = num;
            }
        }

        return minNum;
    }
}

Java

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

Java

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

Java

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

Java

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }
}

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }
}

Java

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlockBruteforce(List<Integer> list) {
        int minMaxBlockSize = Integer.MAX_VALUE;
        int minNum = -1;

        Set<Integer> uniqueElements = new HashSet<>(list);

        for (int num : uniqueElements) {
            List<Integer> indices = new ArrayList<>();
            for (int i = 0; i < list.size(); ++i) {
                if (list.get(i) == num) {
                    indices.add(i);
                }
            }
            indices.add(0, -1);
            indices.add(list.size());

            int maxBlockSize = 0;
            for (int i = 1; i < indices.size(); ++i) {
                maxBlockSize = Math.max(maxBlockSize, indices.get(i) - indices.get(i - 1) - 1);
            }

            if (maxBlockSize < minMaxBlockSize) {
                minMaxBlockSize = maxBlockSize;
                minNum = num;
            }
        }

        return minNum;
    }

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5);

        // Timing brute force method
        long startTimeBruteForce = System.nanoTime();
        int bruteForceResult = minimalMaxBlockBruteforce(list);
        long endTimeBruteForce = System.nanoTime();
        long durationBruteForce = endTimeBruteForce - startTimeBruteForce;

        // Timing optimized method
        long startTimeOptimized = System.nanoTime();
        int optimizedResult = minimalMaxBlock(list);
        long endTimeOptimized = System.nanoTime();
        long durationOptimized = endTimeOptimized - startTimeOptimized;

        // Output results
        System.out.println("Brute Force Result: " + bruteForceResult);
        System.out.println("Brute Force Time: " + durationBruteForce + " nanoseconds");

        System.out.println("Optimized Result: " + optimizedResult);
        System.out.println("Optimized Time: " + durationOptimized + " nanoseconds");
    }
}

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlockBruteforce(List<Integer> list) {
        int minMaxBlockSize = Integer.MAX_VALUE;
        int minNum = -1;

        Set<Integer> uniqueElements = new HashSet<>(list);

        for (int num : uniqueElements) {
            List<Integer> indices = new ArrayList<>();
            for (int i = 0; i < list.size(); ++i) {
                if (list.get(i) == num) {
                    indices.add(i);
                }
            }
            indices.add(0, -1);
            indices.add(list.size());

            int maxBlockSize = 0;
            for (int i = 1; i < indices.size(); ++i) {
                maxBlockSize = Math.max(maxBlockSize, indices.get(i) - indices.get(i - 1) - 1);
            }

            if (maxBlockSize < minMaxBlockSize) {
                minMaxBlockSize = maxBlockSize;
                minNum = num;
            }
        }

        return minNum;
    }

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5);

        // Timing brute force method
        long startTimeBruteForce = System.nanoTime();
        int bruteForceResult = minimalMaxBlockBruteforce(list);
        long endTimeBruteForce = System.nanoTime();
        long durationBruteForce = endTimeBruteForce - startTimeBruteForce;

        // Timing optimized method
        long startTimeOptimized = System.nanoTime();
        int optimizedResult = minimalMaxBlock(list);
        long endTimeOptimized = System.nanoTime();
        long durationOptimized = endTimeOptimized - startTimeOptimized;

        // Output results
        System.out.println("Brute Force Result: " + bruteForceResult);
        System.out.println("Brute Force Time: " + durationBruteForce + " nanoseconds");

        System.out.println("Optimized Result: " + optimizedResult);
        System.out.println("Optimized Time: " + durationOptimized + " nanoseconds");
    }
}

Java

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

Java

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

Java

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

Java

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }
}

Java

import java.util.*;

public class MinimalMaxBlock {

    public static int minimalMaxBlockBruteforce(List<Integer> list) {
        int minMaxBlockSize = Integer.MAX_VALUE;
        int minNum = -1;

        Set<Integer> uniqueElements = new HashSet<>(list);

        for (int num : uniqueElements) {
            List<Integer> indices = new ArrayList<>();
            for (int i = 0; i < list.size(); ++i) {
                if (list.get(i) == num) {
                    indices.add(i);
                }
            }
            indices.add(0, -1);
            indices.add(list.size());

            int maxBlockSize = 0;
            for (int i = 1; i < indices.size(); ++i) {
                maxBlockSize = Math.max(maxBlockSize, indices.get(i) - indices.get(i - 1) - 1);
            }

            if (maxBlockSize < minMaxBlockSize) {
                minMaxBlockSize = maxBlockSize;
                minNum = num;
            }
        }

        return minNum;
    }

    public static int minimalMaxBlock(List<Integer> list) {
        HashMap<Integer, Integer> lastOccurrence = new HashMap<>();
        HashMap<Integer, Integer> maxBlockSizes = new HashMap<>();

        for (int i = 0; i < list.size(); ++i) {
            int num = list.get(i);
            if (!lastOccurrence.containsKey(num)) {
                maxBlockSizes.put(num, i);
            } else {
                int blockSize = i - lastOccurrence.get(num) - 1;
                maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
            }
            lastOccurrence.put(num, i);
        }

        for (Map.Entry<Integer, Integer> entry : lastOccurrence.entrySet()) {
            int num = entry.getKey();
            int pos = entry.getValue();
            int blockSize = list.size() - pos - 1;
            maxBlockSizes.put(num, Math.max(maxBlockSizes.get(num), blockSize));
        }

        int minNum = -1;
        int minBlockSize = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : maxBlockSizes.entrySet()) {
            if (entry.getValue() < minBlockSize) {
                minBlockSize = entry.getValue();
                minNum = entry.getKey();
            }
        }

        return minNum;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5);

        // Timing brute force method
        long startTimeBruteForce = System.nanoTime();
        int bruteForceResult = minimalMaxBlockBruteforce(list);
        long endTimeBruteForce = System.nanoTime();
        long durationBruteForce = endTimeBruteForce - startTimeBruteForce;

        // Timing optimized method
        long startTimeOptimized = System.nanoTime();
        int optimizedResult = minimalMaxBlock(list);
        long endTimeOptimized = System.nanoTime();
        long durationOptimized = endTimeOptimized - startTimeOptimized;

        // Output results
        System.out.println("Brute Force Result: " + bruteForceResult);
        System.out.println("Brute Force Time: " + durationBruteForce + " nanoseconds");

        System.out.println("Optimized Result: " + optimizedResult);
        System.out.println("Optimized Time: " + durationOptimized + " nanoseconds");
    }
}

Introduction

Task Statement

Brute Force Approach

Join the 1M+ learners on CodeSignal

Complexity Analysis

Step 1: Setup the Solution Approach

Step 2: Initialize the Dictionaries

Step 3: Traverse the List

Step 4: Handle Tail Blocks

Step 5: Return the Optimal Result

Full Code

Lesson Summary