Problem Statement
In my first read, the problem seems to be complicated. After two to three more reads of the problem statement, I was able to get the clear picture of what was asked. The crux is, we are given a grid with values {Y, N}. The character Y implies that you will be given the area of the corresponding cells. Having know areas of certain cells, we have to find a minimum number of cells whose areas needs to be known to find the area of the grid WXH.
Approach
The key idea for this problem is, breaking down the problem into subproblems. Here are the series of questions that helped me to answer.
- A minimum number of grid cells that are required?
- area of grid and its relation to the area of individual cells.
- trying out with smaller examples
- knowing the set of dependent equations and viewing them as connected graphs
Above questions, helped me to come with concrete subproblems.
- find the number of cells that are connected to each other forming a separate graph
- find the number of variables for which area is unknown.
The beauty of this problem lies in understanding the area of rectangle equation and how connected component helps in reducing the equation to one common unknown variable.
Code
public class RectangleArea {
int[] parent = new int[3000];
public void initialize(int N) {
for (int i = 0; i < N; i++)
parent[i] = i;
}
public void union(int u, int v) {
int parent_u = find(u);
int parent_v = find(v);
parent[parent_v] = parent_u;
}
public int find(int p) {
if (parent[p] != p)
parent[p] = find(parent[p]);
return parent[p];
}
public int minimumQueries(String[] known) {
int n = known.length;
int m = known[0].length();
initialize(n + m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (known[i].charAt(j) == 'Y')
union(i, j + n);
int result = 0;
for (int i = 0; i < n + m; i++)
if (parent[i] == i)
result++;
return result - 1;
}
}