Hello everybody. I have been very busy looking into a problem at work which seemed to be caused by sockets. It seems that the issue might be related to encryption. Have a couple tests that should verify my assumption. Will let you know if that pan out.
Today in the Twin Cities of Minneapolis and St. Paul we woke up with a temperature above 0F (7F). Looking at the weather forecast it seems like the sub zero temperatures will be a thing of the past in a day or so. Weather forecasts are based on models and models in general are far from perfect, but they provide us with an idea of what might happen in the specified future.
Earlier this morning I finished reading an article Differential Privacy: The Pursuit of Protections by Default. It appears that Google in September 2019 released an open source version of the differential privacy library they use in some internal projects. The article provides a basic description on the technology. You can read more about what it is at Harvard University Privacy Tools Project.
The article provides some examples of users making queries to obtain some aggregates. One of the examples describes medical information. I have been working with medical images for some time. There are also regulations i.e., HIPAA regarding ho have access to which information from patients.
I believe differential privacy is a step in the right direction. That said; the real problem seems to be in which data is collected, how is it stored and who can have access to it. The best way to avoid privacy invasions is by not having the data collected at all. In my opinion companies should not collect any data that the user is not allowing and the data should be deleted after a short period of time e.g., one month. Aggregations may be held for a much longer time. Keep in mind that the problem persists as how to secure such data and who has access to it.
The article is interesting and provides you with insights as how some people are interested in privacy.
OK, let’s get down to the subject for this post.
I have read different requirements to what seems to be the same problem. We are given a grid with cells containing 1s indicating land and 0s indicating water. The dimensions of the grid may vary. The idea is to switch a single cell from 0 to 1 to create the largest island in the grid. If this sounds attractive to you, I suggest reading LeetCode 827 Making a Larger Island problem to get the requirements directly from the source. LeetCode provides a few examples so you can fully understand the requirements.
If you can identify the islands then you are one step closer to the solution. LeetCode has a problem that will help figuring out the first step. Last year I wrote a post in this blog Number of Islands – Java in which we had to count the islands. To do so we had to collect the adjacent 1s and figure the size of each island. Given that we know how to get that done, we then need a way to figure out which cell containing a 0 we can flip to a 1 in order to join two or more islands and get a larger joint island.
It turns out that we will have to edit the code from the previous post in order to get to a solution which will be efficient enough to be accepted by LeetCode. I started with the previous code and built on top. At some point I had to edit the initial code to merge functionality. Such approach was accepted.
If you have been following my blog, lately I have been mostly developing solutions in Java. The reason for this is that Java seems to be more palatable to most readers. I do and have worked in many projects in C and C++. Moving forward we will see more posts using C and C++. That said, if you encounter an issue and would like to see the solution in Java, please let me know.
In this post I decided to use the Java programming language on a Windows 10 machine and the VSCode IDE. This requires a test scaffolding to collect the data, present it to the method of interest and display results. If you wish to avoid on a test scaffold, you can develop the code directly using the on-line IDE provided by LeetCode. It is pretty good.
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in grid AFTER applying this operation. An island is a 4-directionally connected group of 1s. Constraints: o n == grid.length o n == grid[i].length o 1 <= n <= 500 o grid[i][j] is either 0 or 1.
In this case we are given a square matrix. Due to the fact that the Number of Islands – Java problem had different rectangle dimensions for the grid, this solution will use different numbers for rows and columns.
Like I mentioned earlier, please visit the LeetCode site and get the latest version of the requirements. They may be somewhat different.
public int largestIsland(int[][] grid) {
}
The signature for the method in question is quite reasonable. We get a grid with 1s and 0s, need to detect the islands and then join them looking for the largest joint island. Our method needs to return the size of the largest possible island.
1,1 0 main <<< rows: 1 cols: 1 main <<< grid: [0] main <<< largestIsland: 1 2,2 1,0 0,1 main <<< rows: 2 cols: 2 main <<< grid: [1, 0] [0, 1] main <<< largestIsland: 3 2,2 1,1 1,0 main <<< rows: 2 cols: 2 main <<< grid: [1, 1] [1, 0] main <<< largestIsland: 4 2,2 1,1 1,1 main <<< rows: 2 cols: 2 main <<< grid: [1, 1] [1, 1] main <<< largestIsland: 4 2,2 0,0 0,0 main <<< rows: 2 cols: 2 main <<< grid: [0, 0] [0, 0] main <<< largestIsland: 1 2,2 1,0 0,0 main <<< rows: 2 cols: 2 main <<< grid: [1, 0] [0, 0] main <<< largestIsland: 2 3,3 1,0,0 0,0,0 0,0,1 main <<< rows: 3 cols: 3 main <<< grid: [1, 0, 0] [0, 0, 0] [0, 0, 1] main <<< largestIsland: 2 4,5 1,0,0,1,1 1,1,1,0,1 1,0,0,1,1 1,0,0,1,1 main <<< rows: 4 cols: 5 main <<< grid: [1, 0, 0, 1, 1] [1, 1, 1, 0, 1] [1, 0, 0, 1, 1] [1, 0, 0, 1, 1] main <<< largestIsland: 14 4,5 0,1,0,1,0 1,1,0,0,1 0,0,1,1,0 0,0,0,0,0 main <<< rows: 4 cols: 5 main <<< grid: [0, 1, 0, 1, 0] [1, 1, 0, 0, 1] [0, 0, 1, 1, 0] [0, 0, 0, 0, 0] main <<< largestIsland: 6 7,7 0,0,0,0,0,0,0 0,1,1,1,1,0,0 0,1,0,0,1,0,0 1,0,1,0,1,0,0 0,1,0,0,1,0,0 0,1,0,0,1,0,0 0,1,1,1,1,0,0 main <<< rows: 7 cols: 7 main <<< grid: [0, 0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 0, 0] [0, 1, 0, 0, 1, 0, 0] [1, 0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 1, 0, 0] [0, 1, 0, 0, 1, 0, 0] [0, 1, 1, 1, 1, 0, 0] main <<< largestIsland: 18 5,5 1,1,1,1,0 1,1,0,1,0 1,1,0,0,0 0,0,0,0,0 1,0,1,0,1 main <<< rows: 5 cols: 5 main <<< grid: [1, 1, 1, 1, 0] [1, 1, 0, 1, 0] [1, 1, 0, 0, 0] [0, 0, 0, 0, 0] [1, 0, 1, 0, 1] main <<< largestIsland: 11 5,5 1,1,0,0,0 1,1,0,0,0 0,0,1,0,0 0,0,0,1,1 1,1,0,0,1 main <<< rows: 5 cols: 5 main <<< grid: [1, 1, 0, 0, 0] [1, 1, 0, 0, 0] [0, 0, 1, 0, 0] [0, 0, 0, 1, 1] [1, 1, 0, 0, 1] main <<< largestIsland: 6 5,5 1,0,0,0,0 0,0,0,0,1 1,0,0,0,0 0,0,0,0,1 1,0,0,0,0 main <<< rows: 5 cols: 5 main <<< grid: [1, 0, 0, 0, 0] [0, 0, 0, 0, 1] [1, 0, 0, 0, 0] [0, 0, 0, 0, 1] [1, 0, 0, 0, 0] main <<< largestIsland: 3
LeetCode provides some examples. The rest were generated by me or encountered them while submitting the code. As we will find out, I ended up with a few methods which could have been condensed into two.
We are provided two numbers. The first is the number of rows in the grid and the second the number of columns. The lines that follow contain the data for each row.
Our test scaffold seems to read the input lines and display the number of rows and columns. The input grid seems to be allocated, populated and displayed. At that point it seems we call our method of interest and display the results. It seems I have too many test cases, but at some points I needed to verify different conditions.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the number of rows and columns ****
int[] rc = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** ****
int rows = rc[0];
int cols = rc[1];
// ???? ????
System.out.println("main <<< rows: " + rows + " cols: " + cols);
// **** declare and populate grid ****
int[][] grid = new int[rows][];
for (int i = 0; i < rows; i++) {
grid[i] = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
}
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< grid: ");
for (int r = 0; r < rows; r++)
System.out.println(Arrays.toString(grid[r]));
// **** generate and display size of the largest island ****
System.out.println("main <<< largestIsland: " + largestIsland(grid));
}
Our test scaffolding seems to collect and display the data as we already covered when looking at the test cases. I believe there is not much we can add to the description.
// **** global variable(s) ****
static int islandID;
static HashMap<Integer, Integer> sizes;
static int[][] dirs = new int[][]{ {0,1}, {0,-1}, {-1,0}, {1,0} };
We will use a set of three global variables. We could have used arguments to methods instead, but I started with the code from the previous post. In retrospect, I should have just used the ideas from the past post and write the code from scratch (what happened with code reuse).
We first need to identify the islands we have in our grid. Initially all islands are identified with a 1 (assume white) and water with a 0 (assume blue). We need to identify each island with a different value. Think of it as coloring each island with a different color. Since we start with white and we need to make sure we do not revisit cells, we will start coloring with the ID in the islanded variable. We will use 2 and will increment the value each time we encounter a new island. This is different from what we did in the previous post.
We will need to associate each island’s color with its size. That way we can avoid traversing the islands that are adjacent each time we change the color of a water tile. This is more efficient.
Finally we will use the int[][] dirs array to get the addresses of the adjacent cells to a cell in the grid. Remember that we can only go up, right, down and left when we perform a DFS traversal as specified by the requirements.
/**
* You are allowed to change at most one 0 to be 1.
* Return the size of the largest island in grid
* AFTER applying this operation.
*
* NOTE: in the current version of the LeetCode problem,
* the number of rows == number of columns. We will allow
* for different dimensions in this implementation.
*
* Runtime: 66 ms, faster than 35.39% of Java online submissions.
* Memory Usage: 78.5 MB, less than 11.28% of Java online submissions.
*/
static int largestIsland(int[][] grid) {
// **** sanity check(s) ****
if (grid.length == 1 && grid[0].length == 1)
return 1;
// **** initialization ****
int rows = grid.length;
int cols = grid[0].length;
islandID = 2;
sizes = new HashMap<Integer,Integer>();
// **** color islands and associate the color with their size ****
colorIslands(grid, rows, cols);
// **** join islands and determine which is the largest joint island ****
return joinIslands(grid, rows, cols);
}
This is the method of interest. After sanity checks and initialization we have the code separated into two methods. I believe we have covered the use of the variables we initialize in this section.
At this point we have a grid with 1s and 0s. We need to color them and store size information for every island based on their color (ID). Once that is done we need to figure out how to traverse the water (0) tiles and determine the size of the joint islands.
/**
* Given a 2D grid map of 1s (land) and 0s (water),
* assign each island a unique color (ID).
*/
static void colorIslands(int[][] grid, int rows, int cols) {
// **** initialization ****
int[] size = new int[] {0};
// **** loop once per cell in the grid ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** visit cell (if on land and not visited yet) ****
if (grid[r] == 1) {
// **** initialize this island size ****
size[0] = 0;
// **** visit the island starting at specified cell ****
visitIsland(grid, r, c, size);
// **** save the island ID (color) and size in the hash map ****
sizes.put(islandID, size[0]);
// **** increment the island ID (different color) ****
islandID++;
}
}
}
}
We initialize the size to 0 and then we will loop through each column on each row looking for unvisited cells. When we find an unvisited cell (1) we clear the size and visit the island in some recursive fashion using the visitIsland() method. With the size on hand, we put the ID (color) and size in the sizes hash map. We then increment the color (ID) in preparation to visit the next island (if any).
When this method returns we have identified and colored each island and saved the color and size in a hash map.
/**
* Visit an entire island.
* Recursive DFS call.
* Execution O(n * m)
*/
static void visitIsland(int[][] grid, int r, int c, int[] size) {
// **** base condition (water or visited island) ****
if (grid[r] != 1)
return;
// **** color this cell ****
grid[r] = islandID;
// **** count this cell ****
size[0]++;
// **** recurse right ****
if (c < grid[r].length - 1)
visitIsland(grid, r, c + 1, size);
// **** recurse down ****
if (r < grid.length - 1)
visitIsland(grid, r + 1, c, size);
// **** recurse left ****
if (c > 0)
visitIsland(grid, r, c - 1, size);
// **** recurse up ****
if (r > 0)
visitIsland(grid, r - 1, c, size);
}
This is the implementation of the method that performs a DFS traversal so we can color and determine the size of each island.
We start by making sure we only process unvisited land cells. We assign the current color to a visited cell. We also increment the count of cells for this island. We could have used the int[][] dirs array here but we did not. I will leave this as a possible added point. We need to recursively visit all land cells that are accessible in this island.
/**
* Join islands and return the largest size.
*/
static int joinIslands(int[][] grid, int rows, int cols) {
// **** sanity check(s) ****
if (grid.length == 1)
return 1;
// **** initialization ****
int largestSize = 0;
int id = 0;
int size = 0;
Set<Integer> ids = new HashSet<>();
// **** additional sanity check ****
if (sizes.size() == 1 && sizes.get(2) == rows * cols)
return rows * cols;
// **** loop checking water neighbors ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// **** skip land ****
if (grid[r] != 0)
continue;
// **** clear the list of ids ****
ids.clear();
// **** clear the size of the island ****
size = 0;
// **** check all four directions ****
for (int[] dir : dirs) {
// **** set the row and column ****
int rr = r + dir[0];
int cc = c + dir[1];
// **** check bounds and not water ****
if (rr < rows && rr >= 0 && cc >= 0 && cc < cols && grid[rr][cc] != 0) {
// **** get island ID ****
id = grid[rr][cc];
// **** join this island (if needed) ****
if (!ids.contains(id)) {
ids.add(id);
size += sizes.get(id);
}
}
}
// **** include in the count the cell we are visiting ****
size++;
// **** update the largest joint island size (as needed) ****
largestSize = (size > largestSize) ? size : largestSize;
}
}
// **** return the size of the largest joint island ****
return largestSize;
}
Now we take a look at the key method in this solution. We need to join our colored islands by visiting each water cell, virtually changing it to land, and adding the size of any adjacent island. Stop here for a moment and make sure we are on the same page as to why this approach will work.
After some sanity checks and initializations we are ready to traverse the grid looking for cells that contain water (0). BTW, the ids set will be used to make sure we do not include the same island more than once. Think about a water cell that is adjacent to up to four land cells that belong to the same island.
In the nested loop we check and skip cells that are not water.
We then clear the list of adjacent ids (colors) and clear the size of the island. We could have set it to 1 and remove the size++ statement. I guess I missed that.
We now have to look in all four directions from the water cell for different adjacent islands. We use the int[][] dirs array to step through the adjacent cells.
We check bounds in the grid and make sure the adjacent cell is not water. If so; we get the island ID (color). We then check if this island has not been visited yet. If not, we add the id (color) to our set of visited islands and add the size.
After we have checked all four directions, we include the water (0) cell which we would have flipped to land (1) by incrementing the size of the joint islands. We then update the largest size of the islands we have already joint.
When all is set and done, we return the size of the largest joint island(s).
This is considered as a hard problem by LeetCode. The idea on how to solve it takes some time. The idea on how to separate the islands is also required. It was a good problem to work on. It took me several hours to solve it. If you are asked to solve this problem in an interview, and you have no knowledge on how to solve it, there is no way you will get it solve. Less solve it without syntax issues on a white board not using an IDE.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,672 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com