#june leetcode challenge

[mother-sauces]

Day 17: Surrounded Regions

Problem: You are given a grid of cells containing either "X" or "O". Flip all "surrounded" Os to Xs. An O is surrounded if it is part of a region of adjacent Os that does not touch the border of the grid.

My approach: Flood fill the grid. Cells with an "O" are open to the flood, and cells with an "X" block it. The fill reaches every "border" cell and every cell that's adjacent to a filled cell (no diagonals). Finally, fill in all the cells that aren't touched by the fill.

Definitely save partial work, you'll be revisiting cells fairly often. You can do this in-place if you store results in the grid. Make sure you format your code nicely, because you'll have to repeat things four times (one per direction) with small variations.

My advice for this problem is pretty generic. Flood-fill isn't trivial, but the individual steps are pretty simple. Test as you go, and make sure each step is correct, independently? Hopefully you're doing that already.

54 LOC; expect variation.

[mother-sauces]

Day 16: Validate IP Address

We're tasked with writing a function that can validate IPv4 and IPv6 addresses.

It's possible to do each one with a single regex. If that sounds good to you, are you mental?! Please do not!!

(This is a good challenge. Parsing is one of the highest arts of programming.)

I prefer a mixed approach, something like:

Split string into groups based on . or : delimeter

Validate number of groups

Validate individual groups

You can do this as one generic function or two similar functions. I don't care, I need a nap.

37 LOC

[mother-sauces]

Day 8: Power of Two

I was getting restless and skipped the weekend, so of course they threw some interesting problems my way. I'll get to Days 6 & 7 soon.

The problem: "Given an integer, determine if it's a power of two"

Generate integer powers of 2 in O(log n). Test each one against the argument. 5 LOC. Boring.

Also possible to do this by inspecting bits in O(len(n)), but this problem isn't worth it.

[mother-sauces]

Day 30: Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Link

(Note that this means that words can bend, which is not at all how real word searches work)

The hints here are really good! You have to iterate through every cell on the board, and then you have to decide whether to do a depth-first or breadth first search, so naive computational complexity looks bad. But you can decide whether to backtrack in O(len(current_candidate_string)), if you “trie” hard enough. 

For a problem with this many moving parts, I’d normally be worried about performance, but my first full solution was accepted immediately. A nice end to the month! (I’m writing this on July 2 because I’m slow)

I enjoyed writing these, so I might continue along similar lines in the future. I’m definitely not doing the July LeetCode Challenge; I’m reclaiming my spare time.

[mother-sauces]

Day 29: Unique Paths

Time to finish the month strong!

A robot is located at the upper-left corner of an m x n grid. The robot can only take one step at a time, moving either down or right. How many unique paths are there that take the robot to the bottom-right corner?

If you haven't seen it before, this is a pretty classic problem for learning Dynamic Programming. We can describe it as an elegant induction problem, and use that to write an elegant program.

Consider: for most grids, the robot has to move either right or down. If it moves right, it's now at the upper-left corner of an (m-1) x n grid. For moves downward, we reduce n by 1. Add those together, and you have a solution. For an easy base case, a 1 x 1 grid has 1 unique path.

If you code this naively, it might be too slow on its own. You can improve the base cases or exploit the symmetry, but I really like memoization: caching previously calculated results. You'll often be able to reuse solutions to subproblems, almost as if you're a hoity-toity functional programmer.

9 LOC

[mother-sauces]

Day 23: Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Or, if you're lazy, just count nodes while ignoring whether the tree is complete. 5 LOC

[mother-sauces]

Day 22: Single Number II

You are given an array of integers. Every element in the array appears three times, except for one, which appears only once. Return that element.

(This is really straightforward if you use a hashmap and just count the elements, but we can also do this in linear time with constant extra memory)

This is a twist on a classic parity problem. If you want to eliminate elements which occur twice, you can just XOR them together. In principle, there's some forms of XOR gates that work with 3 inputs at once, but I can't figure out how I'd iterate over the elements.

After a bit of Binging around, I found the obvious solution: just count parity. Since we need to do this in constant space, I thought about ways to encode that succinctly. In the XOR method, we're counting parity of bits. We can do that in sizeof(int) space with an array!

Once we have the parity, we can combine all the bits which show up with a parity that isn't a multiple of 3.

I have a few more days to catch up on. All the really interesting problems take more time.

[mother-sauces]

Day 18: H-Index II

Consider a scientist who publishes papers which are cited by other authors. The H-Index is the largest number of papers N which have at least N citations. Given an array containing the number of citations on each paper, calculate their H-Index. The array is sorted from least to greatest.

Got that? Here's a quick example:

citations = [0, 1, 3, 5, 6]

There are 3 papers with at least 3 citations, so the H-index is 3.

My first instinct was to do this as a linear search. That's fine! It was really concise. (Go backwards!)

But there's a reason the array is sorted. They want you to try binary search. So I did that too. If you have a solution for linear search, you've already got the tools to pinpoint the answer. 14 LOC.