Painting

Problem Statement

You are given an $N$ by $N$ array, with all values initially $0$ . An artist painted $N \times N$ rectangles of various sizes (there can be rectangles of the same size), one in each of $N \times N$ different colors (denoted 1… $N \times N$ ). The artist could have drawn over another rectangle while painting, replacing the color in that grid completely. How many different colors could have been the color of the first rectangle drawn? A final color of $0$ means that the artist never painted on that square.


int painting(int **grid, int n) {
  // your code here
}

Examples

Example 1

1 1
2 2

We have a $2$ by $2$ rectangle, so we should have 4 different colors. Any four of those colors could have been the first to be drawn. We could have drawn a $2$ by $1$ rectangle of color $1$ first, a $2$ by $1$ rectangle of color $2$ first, or any dimension rectangle of color $3$ or $4$ first.

Example 2

The answer shoule be $13$ .

Hints

Click Here

When we find the four corners of the rectangle, what if another rectangle cuts through it perfectly? For example…
```
1 1 0
1 1 0
2 2 0
```
How do we know if rectangle of color $1$ doesn’t extend beneath the rectangle of color $2$ ? Does it matter?
What happens if we only see one color on the final painting?
```
1 0
0 0
```
What if we see all the colors on the screen in the end?
```
1 2
3 4
```
Is the following situation possible?
```
1 0
0 1
```

Click below for the solution

Click Here

General Solution

First, let’s look at all the colors left after the artist finished the painting. If we only saw $X$ colors in the final painting, we know immediately that any of the $N \times 2 - X$ colors could have been used first. This is because we could easily started with a $1$ by $1$ rectangle of color $i$ , which would later have been drawn over. Now, let’s look at the actual painting. We can keep track of the $4$ corners of each rectangle. This can easily be done by scanning through the array and looking at the maximum/minimum $x$ and $y$ values. Iterate through each point of each rectangle, and if we see a color that is not supposed to be there, we know that the “rogue” color could not have come first in the painting. To determine if a color is a “rogue” color, it must appear within the bounds of a rectangle of a different color.

Walkthrough of Example 2

Since this is a $4$ by $4$ grid, there are $16$ total rectangles, exactly one in each color. We see that there are $4$ colors in the final canvas, so we know that there is at least $12$ colors that could have been used first. Now, let’s look at the corners of the color $2$ rectangle. The left-most location is $x = 0$ , its bottom-most location is $y = 1$ , its upper-most location is $y = 3$ (note that we are indexing starting at $0$ ), and its right-most location is $x = 1$ . A big insight here is that though this rectangle could have been extended to $x = 2$ , we cannot treat it as such because there is no guarentee; otherwise, we could be falsely assuming that colors $3$ and $4$ are overlapping rectangle $2$ . We can similarly find the four corners of the other rectangles. Once we found the rectangle corners, go through all the colors that we see in the final canvas state ( $2$ , $3$ , $4$ , and $7$ ). If any color shows up within the bounds of a differently colored rectangle, then it could not have come first. For example, we know $7$ could not have come first because a block of color $7$ shows up where color $2$ should have been. We can ignore double counting with a set data-structure, which holds only unique values.

Runtime

We have to go through the $N \times N$ array once to scan for all the colors in the final painting. Then, we have to go through the rectangles in the array, each once. Worst case, we go through the entire array once more. This gives us an $O(N \times N)$ runtime.

Sample Solution

#include <iostream>
#include <set>
using namespace std;

const int MAXINT = 0x7fffffff;

int painting(int **grid, int n) {
  int i, j, counter = 0;
  set<int> used, b;
  set<int>::iterator it;
  for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (grid[i][j] != 0) used.insert(grid[i][j]); // Finding all the colors used in the painting
  int **t = new int*[n * n + 1];
  for (i = 0; i < n * n + 1; i++) t[i] = new int[4];
  for (i = 0; i < n * n + 1; i++) for (j = 0; j < 4; j++) t[i][j] = j > 1 ? MAXINT : -1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (grid[i][j] != 0) {
        t[grid[i][j]][0] = min(t[grid[i][j]][0], j); // The next few lines finds the corners of a rectangle 
        t[grid[i][j]][1] = min(t[grid[i][j]][1], i);
        t[grid[i][j]][2] = max(t[grid[i][j]][2], j);
        t[grid[i][j]][3] = max(t[grid[i][j]][3], i);
      }
    }
  }
  int *final = new int[n * n];
  for (i = 0; i < n * n; i++) final[i] = 0;
  for (it = used.begin(); it != used.end(); it++) {       // Here, we go through each color and check to see if it appears in location where a rectangle of a different color
    for (i = t[*it][1]; i <= t[*it][3]; i++) {            // should have been
      for (j = t[*it][0]; j <= t[*it][2]; j++) {
        if (grid[i][j] != *it) {
          if (final[grid[i][j] - 1] == 0) {
            final[grid[i][j] - 1] = 1;
            counter++;
          }
        }
      }
    }
  }
  return used.size() == 1 ? n * n - 1 : n * n - counter;
}