Island Perimeter
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
public static int islandPerimeter(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
result += 4;
if (i > 0 && grid[i-1][j] == 1) result -= 2;
if (j > 0 && grid[i][j-1] == 1) result -= 2;
}
}
}
return result;
}There are many ways to solve this but I like this approach the best. The key is to think of each cell as having 4 sides and noting that when cells are adjacent and both part of the island, to remove the shared perimeter you can decrement by 2 (one side for each cell). I don't think this will be many peoples first thought when trying to solve this problem but once you know this trick it simplifies the problem. Any depth first search or other traversal approach will have to deal with the complexity of double counting sides and determining what is actually a perimeter, so the above approach will likely be simpler and shorter code.
Related Problems
Given a function fn, return a curried version of that function.
A curried function is a function that accepts fewer or an equal number of parameters as the original function and returns either another curried function or the same value the original function would have returned.
In practical terms, if you called the original function like sum(1,2,3), you would call the curried version like csum(1)(2)(3), csum(1)(2,3), csum(1,2)(3), or csum(1,2,3). All these methods of calling the curried function should return the same value as the original.
The Hamming Distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.