# 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`.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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<>());
unlocks.put(key, dep);
}
}
}
}

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