Stamp Box

Posted: 17 Apr, 2021
Difficulty: Moderate


Try Problem

Ninja got a moody friend who is very curious about colors. His friend presented him with a design made of various colors and gave him a stamp box. The various colors are given in the form of numbers. He can adjust the dimensions of the stamp box as per need.

Ninja is supposed to draw the given design under the given conditions:

1. Ninja can use one color at a time.
2. Ninja can’t use one color more than once.
3. The stamp box is in the form of a rectangle. So, Ninja can only draw rectangles(or squares) by adjusting the dimensions of the stamp box.
4. Once Ninja prints any color using the stamp box, the old color won’t be visible and only the new color will be visible.

Ninja is very busy in doing some other stuff but he can find some time if it is possible to print the design under the given conditions and if it is impossible to print the design, he won’t waste time on it.

Can you help Ninja to find if it is possible to print the design or not?

Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains two space-separated integers ‘N’ and ‘M’, which denotes the number of rows and columns in the matrix ‘MAT’.

The next ‘N’ lines contain ‘M’ space-separated integers denoting the colors at that point.
Output Format:
For each test case, print 1 if it is possible to draw the given design. Otherwise, print 0.

Print the output of each test case in a separate line.
You are not required to print the expected output, it has already been taken care of. Just implement the function.
1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
1 <= MAT[i][j] <= 50

Where 'MAT[i][j]' is the color in the coordinate (i, j).

Time Limit: 1 sec
Approach 1

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.
Try Problem