Strange Printer II

This page explains Java solution to problem Strange Printer II using Topological Sorting algorithm.

Problem Statement

There is a strange printer with the following two special requirements:

• On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
• Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Input: [[1,2,1],[2,1,2],[1,2,1]]
Output: false

Input: [[1,1,1],[3,1,3]]
Output: false

Solution

package com.vc.hard;

import java.util.*;

class StrangePrinterIi {
    public boolean isPrintable(int[][] targetGrid) {

        HashMap<Integer, int[]> rangeMap = new HashMap<>();
        for(int row = 0; row < targetGrid.length; row++) {
            for(int col = 0; col < targetGrid[0].length; col++) {
                if(!rangeMap.containsKey(targetGrid[row][col])) {
                    rangeMap.put(targetGrid[row][col], new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE});
                }

                int[] range = rangeMap.get(targetGrid[row][col]);
                range[0] = Math.min(range[0], row);
                range[1] = Math.max(range[1], row);
                range[2] = Math.min(range[2], col);
                range[3] = Math.max(range[3], col);
            }
        }

        Set<Integer> keys = rangeMap.keySet();
        HashMap<Integer, Integer> inDegree = new HashMap<>();
        for(Integer key: keys) inDegree.put(key, 0);

        HashMap<Integer, HashSet<Integer>> unlocks = new HashMap<>();
        for(Integer key: keys) {
            unlocks.put(key, new HashSet<>());
            int xMin = rangeMap.get(key)[0];
            int xMax = rangeMap.get(key)[1];
            int yMin = rangeMap.get(key)[2];
            int yMax = rangeMap.get(key)[3];
            for(int row = xMin; row <= xMax; row++) {
                for(int col = yMin; col <= yMax; col++) {
                    if(targetGrid[row][col] != key && !unlocks.get(key).contains(targetGrid[row][col])) {
                        inDegree.put(targetGrid[row][col], inDegree.get(targetGrid[row][col]) + 1);
                        HashSet<Integer> dep = unlocks.getOrDefault(key, new HashSet<>());
                        dep.add(targetGrid[row][col]);
                        unlocks.put(key, dep);
                    }
                }
            }
        }

        Queue<Integer> q = new LinkedList();
        int size = 0;
        for(Map.Entry<Integer, Integer> entry: inDegree.entrySet()) {
            if(entry.getValue() == 0) {
                q.offer(entry.getKey());
                size++;
            }
        }

        while(!q.isEmpty()) {
            int element = q.poll();
            if(unlocks.containsKey(element)) {
                HashSet<Integer> unlock = unlocks.get(element);
                for(Integer gettingUnlocked: unlock) {
                    inDegree.put(gettingUnlocked, inDegree.getOrDefault(gettingUnlocked, 0) - 1);
                    if(inDegree.get(gettingUnlocked) == 0) {
                        q.offer(gettingUnlocked);
                        size++;
                    }
                }
            }
        }

        return rangeMap.size() == size;
    }
}

Time Complexity

O(V * N * M + (V + E)) Where
V is number of distinct values in a targetGrid
N is number of rows in a targetGrid
M is number of cols in a targetGrid
E is total number of dependencies for e.g. color1 should go before color2

Space Complexity

O(V + E) Where
V is number of distinct values in a targetGrid
E is total number of dependencies for e.g. color1 should go before color2