Back in undergrad, I did a lot of programming challenges – the sort of thing that shows up as a somewhat-contrived question in an interview. Great way to learn about automated testing, though, as in a school environment it’s basically an automated test suite where you aren’t allowed to see the tests.
I’ve been wanting to brush up on algorithms a bit, and figured this would be a good way to do it. This time around, though, I’m using Swift; C++ was a fine language to learn, but I have exactly no desire to use it anymore.
So, the first problem I found whilst aimlessly googling was “Islands”. Given a grid of some sort (could be [[Bool]], although in this case I’ve done one as [[Character]], with '1' and '0' being the inputs), count the number of islands in it.
An island, in this case, is any contiguous collection of '1' is in the grid, while all the the '0's are ocean.
Step One: Ask Questions
First question: what does ‘contiguous’ mean? Can we move diagonally, or only in the four cardinal directions?
Only the four cardinal directions, in this example.
Alright. Next, what happens at the edges? Do we Asteroids-style loop around, or is it just ‘out of bounds == ocean’?
Out of bounds is ocean.
Excellent! Means we don’t have any literal edge cases.
Final question before I start actually digging into the problem, how are we hooking into the test case?
protocol Islands {
func numIslands(_ grid: [[Character]]) -> Int
}
Alright, simple enough. Let’s get cracking.
Step Two: Brainstorm
My first thought upon seeing a grid is “flood fill.” Now, this isn’t quite a flood fill, because the whole point is that it’s not all interconnected, but that at least gives me a starting point – for a flood fill, you want recursion. And you want to remember where you’ve been, so you can make a base case – otherwise, you’ll just loop forever. O(infinity) isn’t really ideal.
So, what’s the actual algorithm here?
Simple enough: for each point on the grid, check if it’s part of a new island. If it is, add one to our count of islands; if it isn’t, don’t. Move on to the next point on the grid.
Now, how do we check if it’s a new island? Also pretty simple: check if we’ve been here before; if we have, it’s not a new island. Then check if it’s an island; if it isn’t, it’s also not a new island. And, now that we know it’s a new island, we go recursive – mark that we’ve been to this spot, and flood fill our way across the neighboring tiles on the grid until we run out of island.
Step Three: Code
class Solution: Islands {
private var visited: [[Bool]] = [] // (1)
private var grid: [[Character]] = [] // (2)
@discardableResult
private func isNewIsland(x: Int, y: Int) -> Bool { // (3)
guard x >= 0 else { return false }
guard y >= 0 else { return false }
guard x < grid.count else { return false }
guard y < grid[0].count else { return false }
if (visited[x][y]) { return false }
visited[x][y] = true
if (grid[x][y] == "1") {
// visit all neighbors
isNewIsland(x: x+1, y: y)
isNewIsland(x: x-1, y: y)
isNewIsland(x: x, y: y+1)
isNewIsland(x: x, y: y-1)
return true
} else {
return false
}
}
func numIslands(_ grid: [[Character]]) -> Int { // (4)
// precondition checks
guard grid.count > 0 else {
return 0
}
guard grid[0].count > 0 else {
return 0
}
// reset visited state
let subItem = Array<Bool>(repeating: false, count: grid[0].count)
self.visited = Array<Array<Bool>>(repeating: subItem, count: grid.count)
self.grid = grid
var islandCount = 0
for i in 0..<grid.count {
for j in 0..<grid[i].count {
if isNewIsland(x: i, y: j) {
islandCount = islandCount + 1
}
}
}
return islandCount
}
}
Let’s go through this bit by bit.
visited is key – we need to know where we’ve been. Unlike the folks making the problem statement, I actually know what my data type is – [[Bool]]- This… is mostly for ease of passing it around. While I could write up my
isNewIsland function in a purely-functional sense, with it taking in the coordinates, visited state, and grid, and then outputting the result… well, that’s kinda silly, really.
isNewIsland is the bulk of the work. Let’s go through it.
- The first four lines are checking that we’ve got valid input. This saves us from needing to check the range every time we call the method; if we try to do something that we can’t, it’ll just return false. Admittedly, I’m not checking that the grid properly exists before using it, but that’s what
private is for – this is an implementation detail.
- Next, check if we’ve visited this spot before. If we have, we’re done – it’s not a new island!
- Before we go any further, mark this spot as visited! Important, because we may be recursing shortly, and we don’t want to get caught in an infinite loop.
- Check if this is an island at all. If it isn’t, we’re done – this wasn’t a new island. If it is, though, we recurse. This is where the
@discardableResult comes in – since we’ve got an early bail-out for “we’ve already visited this spot”, we know we’ll never be checking the same island twice, so we actually don’t care about the result of checking the neighboring spaces, we just need it to happen… so that they get marked as visited. And after we’re done marking the whole island as visited, we can finally return true, telling the caller (if they’re listening!) that this was a new island.
- Finally, our implementation of
numIslands. Mostly it’s just checking for valid inputs – Swift can enforce at compile-time that nobody tries to pass us anything completely the wrong type, but it can’t force people to give us a grid with dimensions greater than 0 in either direction, so we need to check that ourselves. After that, we set up our visited as all-false, copy the grid, and loop through it, counting up our islands.
Step Four: Test
This part, I will mostly leave to your imagination; for myself, I just hit ‘run’ and let the automated tests do their thing. In an interview, Step Two should also include coming up with some test cases and running through them on your pseudo code – and remember to include one or two invalid inputs!
After that, if your tests pass, you could talk about changes you might make. Given my numerous remarks about [[Character]] instead of [[Boolean]], my thought would be to make it generic – have a grid of [[T]] and take a (T) -> Bool closure that tells you whether or not a grid point is an island. I’d also want to comment up the code a bit more, which I’ve neglected to do in this case as I’m writing a blog post around it instead.
Now, having already spoiled the answer, I’ll go ahead and mention that I tried this out at LeetCode; while this one may not be the most fun for you in the immediate wake of my explainer, they’ve got plenty of other solutions you could take a crack at, and a variety of languages to use. Give it a go, it’s kinda fun!
- Basically, the inverse of an “opaque box” analysis, if you think about it. ↩
- And by “I’ve done one” I mean “the site that gave the example,” because I… wouldn’t use
[[Character]] to represent a [[Bool]]. ↩