The problem for September 12 is Combination Sum III. We are
interested in finding all possible distinct combinations of \(k\) numbers that
add up to a number \(n\), given that only numbers from \(1\) to \(9\) can be
used and each combination should be a unique set of numbers. Since you can only
use numbers from \(1\) to \(9\), both \(k\) and \(n\) can’t be negative; \(k\)
is at most \(9\) and \(n\) is at most \(\sum_{i=1}^{9} i = \frac{9 \times (9 +
1)}{2} = 45\).

An exhaustive search using a DFS is possible given these limits, so it
looks like a good candidate for a solution. The following is an implementation
of that:

September LeetCoding Challenge, Day 11: Maximum Product Subarray

The problem for September 11 is Maximum Product Subarray. You’re
given a non-empty array of integers nums and are interested in finding the
contiguous non-empty subarray which has the largest product. You’re not given
any limits on the size of nums.

Since we’re not given any limits on the size of nums, I didn’t assume that the
naive algorithm of checking all possible subarrays in \(\mathcal{O}(n^3)\)
(possibly reducing to \(\mathcal{O}(n^2)\) using dynamic programming) would
work. Instead, I tried to find an algorithm whose time complexity would match
the theoretical lower bound of \(\mathcal{O}(n)\). Some relevant observations
are:

If the array has a single element, then the maximum product will be that
element;

If the array has more than one element, then the maximum product subarray will
contain an even number of negative integers, so that it is either positive or
0;

If there’s at least one non-empty subarray without a 0 with an even number of
negative integers, then the maximum product will never be 0.

Based on the previous observations, we can derive an \(\mathcal{O}(n)\)
algorithm to solve this problem. The idea is to iterate through all the values
of nums, keeping track of, for the product of a non-empty subarray ending at
that number, the largest possible positive number and the smallest possible
negative number. When visiting a new number, if the number is 0, we reset both
these values. If the number is positive, both the largest positive number and
smallest negative number are multiplied by that number. If the number is
negative, the largest possible positive number becomes the multiplication of the
smallest negative number with that number, and vice-versa for the smallest
possible negative number. The largest positive number at each iteration (or 0)
is the largest product of a non-empty subarray ending at that number. The
following is an implementation of that idea:

September LeetCoding Challenge, Day 10: Bulls and Cows

The problem for September 10 is Bulls and Cows. You have to return
the hint for an opponent’s guess in a game of Bulls and Cows,
the paper and pencil game that predated Mastermind.

To get the number of bulls, we simply count the number of digits that match in
both digit and position. For the remaining of digits, for each possible digit
value, we count the number of times there’s a repeated occurrence in both the
guess and the secret. The following is an implementation of this idea:

September LeetCoding Challenge, Day 9: Compare Version Numbers

The problem for September 9 is Compare Version Numbers. Given two
version numbers version1 and version2, represented as strings, you want to
return -1 if version1 is smaller than version2, 1 if version1 is larger
than version2, and 0 if they’re equal. Versions are strings consisting of one
or more revisions joined by a .. Each revision consists of digits only, but
may contain leading zeros. Every revision contains at least one character, so
it’s impossible for a substring of two . to exist. Comparing versions consists
in comparing the integer value of its revisions in left-to-right order. If a
version doesn’t specify a revision at a given index, then the revision should be
treated as 0.

A solution for this problem consists in splitting the two provided strings in
two sequences of numbers and do a pairwise comparison of them. Whenever a
version number is missing a revision, assume 0 as its value. The following is an
implementation of this strategy:

September LeetCoding Challenge, Day 8: Sum of Root To Leaf Binary Numbers

The problem for September 8 is Sum of Root to Leaf Binary Numbers.
You’re given a binary tree in which each node has value 0 or 1. In this case,
each path from the root to a leaf represents a binary number starting with the
most significant bit. For example, a path from root to leaf \(0 \rightarrow 1
\rightarrow 1 \rightarrow 0 \rightarrow 1\) represents the number \(01101\) in
binary, or \(13\) in decimal. We’re interested in the sum of numbers produced
from the paths from the root to every leaf in the tree.

We’re told that the number of nodes in the tree doesn’t exceed 1000 and that the
sum will not exceed \(2^{31} - 1\). Therefore, we can do a DFS on the
tree while keeping track of the number at each path, accumulating the current
number whenever we reach a leaf. Since the path follows the significance of the
bits in the resulting number, we can keep track of the current number while
traversing the tree by multiplying the current number by 2 whenever we go either
left or right, and sum the value at the node we’re visiting. The following is an
implementation of this idea: