Stamp Box

Approach: The idea is to start removing the colors one by one instead of filling the colors.

After making the design, if you can successfully remove the colors, then it will be a blank grid. If it is not possible to make the design under the given conditions, then you won’t be able to reach a blank sheet.

Let’s say if we made a rectangle of 3X3 using color 1 and inside that, we made a rectangle of size 2X2 using color 2. How can we store the information that we have to remove color 2 first and then color 1?

We will use topological sorting for this. We will store indegrees of every color. For the above example, the indegree of color 2 will be 0, and the indegree of color 1 will be 1. It implies that we will remove all the colors with indegrees 0, and then reduce the indegrees of all the connected colors to it. This is similar to topological sorting.

The overview is: Find the colors that are present in the matrix -> find the rectangle in which color lies for all the given colors -> find indegrees of all the colors -> perform topological sorting.

The steps are as follows:

1. In order to find the colors that are present in the matrix and store their coordinates in which the colors lie, we will use hashmap COORDINATES with the key as an integer(to store the colors) and the value as an array. In the array, there will be 4 integers that denote the starting coordinate of the row, ending coordinate of the row, starting coordinate of the column, ending coordinate of the column in which the rectangle of given color lies respectively.
2. Iterate from i = 0 to N - 1:
   • Iterate from j = 0 to M - 1:
     • Insert the current color as the key into the hashmap COORDINATES and an empty array as the value initially. The idea behind this step is when we will store all the colors then we will find the coordinates.
3. In order to find the indegrees, we will iterate over the hashmap COORDINATES and initialize 4 integers - ROWMIN to N, ROWMAX to 0, COLMIN to M, COLMAX to 0 which stores the minimum coordinate for the row, maximum coordinate for the row, minimum coordinate for the column, maximum coordinate for the column respectively for a given color.
4. Iterate over the hashmap COORDINATES:
   • Store the current color(which is the key) in a variable CURRENTCOLOR.
   • Iterate from i = 0 to N - 1:
     • Iterate from j = 0 to M - 1:
       • If the color of the current element is equal to the CURRENTCOLOR:
         • Update ROWMIN to a minimum of i and ROWMIN.
         • Update ROWMAX to a maximum of i and ROWMAX.
         • Update COLMIN to a minimum of j and COLMIN.
         • Update COLMAX to a maximum of j and COLMAX.
   • Push back all the four variables in the hashmap COORDINATES as the value for which current color is the key.
5. In order to create dependencies, we need to make a matrix. As the maximum number of colors can be 50. So, the number of rows needed is more than 50. Initialize a matrix GRAPH with the number of rows = 51.
6. Iterate over the hashmap COORDINATES:
   • Declare a set DEPENDENTCOLOR that stores all the colors which should be removed before the current color.
   • As we have already found the rectangle in which the current color lies. Store the current color(which is the key) in a variable CURRENTCOLOR, and coordinates in variable ROWMIN, ROWMAX, COLMIN, COLMAX respectively.
   • Iterate from i = ROWMIN to ROWMAX:
     • Iterate from j = COLMIN to COLMAX:
       • If the CURRENTCOLOR is not equal to the MAT[i][j], it means this color needs to be removed before the current color and indegree of currentColor is not zero.
       • Insert the color MAT[i][j] in the set dependentColors.
   • Indegree of CURRENTCOLOR will be equal to the number of colors in the set DEPENDENTCOLOR.
   • Now iterate in the set DEPENDENTCOLOR:
     • Insert the currentColor behind the dependent color.
7. We have stored all the dependencies using a matrix GRAPH and indegrees in an array. Now, we will perform topological sorting.
8. Initialize a variable TOTALREMOVEDCOLORS to 0, which stores the number of colors we have removed till now under the given conditions.
9. Declare a queue Q to perform the topological sorting using breadth-first search.
10. Iterate over all the colors:
    • If the indegrees of the current color is zero, it means that the color can be removed first. So, insert the current color in queue Q.
11. Execute a while loop with the condition size of the queue Q is positive:
    • Pick the top color of the queue Q.
    • Increment TOTALREMOVEDCOLORS by 1 as we are removing this color.
    • Iterate over all the dependent colors and reduce their indegrees by 1. If the in-degree of any of the colors becomes 0, insert the color into the queue Q.
12. When we come out of the queue, it means that all the possible colors are removed.
13. If TOTALREMOVEDCOLORS is equal to the number of colors in the matrix, it means that we have removed all the colors. So, return 1.
14. Return 0 otherwise.

O(N*M), where N and M denote the number of rows and columns in the matrix ‘MAT’.

As we are traversing through all the elements of the matrix ‘MAT’. Meanwhile, we are also inserting the colors in a hashmap or hash set which takes constant time. Hence, the overall time complexity is O(N*M).

O(N*M), where N and M denote the number of rows and columns in the matrix ‘MAT’.

As we are storing all the colors, their dependencies, etc. In the worst case, all colors will be different and we need to store all the colors. Hence, the space complexity is O(N*M).