LeetCode1’s daily challenge2 for the 17th of August 2024
was a fun little problem whose solution is interesting enough to provide a
dedicated write-up.
The problem is named Maximum Number of Points with Cost. In the
problem, we are given an \(M \times N\) integer matrix named \(points\) from
which we want to maximize the number of points we can get from. To gain points
from a matrix, we must pick exactly one cell in each row. By picking the cell
with coordinates \((r, c)\) we add \(points[r][c]\) to the score. There is,
however, a caveat that prevents us from being greedy and always choosing the
cell with most points from each row: for every two adjacent rows \(r\) and \(r +
1\), picking cells at coordinates \((r, c_1)\) and \((r + 1, c_2)\) will
subtract \(\operatorname{abs}(c_1 - c_2)\) from the total score. In other words,
the horizontal distance between selected cells in adjacent rows is subtracted
from the total score.
In terms of constraints, we have, for \(M\) being the number of rows and \(N\)
being the number of columns:
\(1 \leq M \leq 10^5\);
\(1 \leq N \leq 10^5\);
\(1 \leq M \times N \leq 10^5\);
\(0 \leq points[r][c] \leq 10^5\).
We can take a look at some example inputs to better understand how we can get
points from a matrix:
Using the above matrix as input, the maximum number of points we can achieve is
obtained from selecting the maximum value from each row, for a total of \(3 -
1 + 5 - 1 + 3 = 9\) points.
Using the above matrix as input, it is preferable to not select the maximum
value from the first row (the \(6\)), because we would be penalized by \(2\) if
we were to select the \(5\) from the second row. Since all selected cells lie in
the same column, we get a total of \(5 + 5 + 5 = 15\) points. If we were to
change the selected cell from the first row from the 5 to the 6, we would get a
total of \(6 - 2 + 5 + 5 = 14\) points.
There are various ways to approach this problem. We are going to take a look at
some of them, even those that won’t lead to accepted solutions given the problem
constraints.
Brute Force
A potential brute force solution involves checking every possible combination of
selections for each row. Since we have \(N\) options per row and \(M\) rows, a
brute force approach would lead to a time complexity of \(\mathcal{O}(N^M)\).
Even though it is not a practical approach given the problem constraints, let’s
see how a brute force solution would look like:
On the C++ sample code above, we’re doing a breadth-first search3 over the
state of possible solutions. Each search state is comprised of the current row,
current column and points gathered so far. We produce new search states by
checking how many points we would get for every cell in the next row. Once we
reach the bottom row we don’t expand our search state further and update our
current best score accordingly. As expected by the problem constraints, the
above code is going to exceed the time (and likely memory) limit of the online
judge.
Brute Force with Cuts
Building on the brute force approach above, we can avoid complete search paths
if we don’t explore search states that have less points than the maximum we have
observed so far for that cell.
The time complexity of the solution above is still \(\mathcal{O}(N^M)\), but
avoids entire search paths for some inputs. It is still not good enough to be
accepted.
Dynamic Programming
Given that \(M \times N\) is at most \(10^5\), a \(\mathcal{O}(M \times N)\)
solution or even a \(\mathcal{O}(M \times N \times \log(N))\) or \(\mathcal{O}(M
\times N \times \log(M))\) solution would work, but anything assymptotically
larger would be challenging. Let’s see if there’s an opportunity to reuse
previous computations when building our solution.
There are some observations we can make in order to base our solution in terms
of smaller subproblems. To compute the maximum number of points for a given cell
of a row \(r\) we only need the maximum number of points we can obtain from each
cell in row \(r - 1\).
To illustrate this idea, let’s consider the following matrix:
Let’s go row by row and fill each cell with the maximum points we could get by
picking it at that point:
Looking at the above, we can make some observations:
The first row is equal to the first row of \(points\).
On each subsequent row \(r\), we only need the values from row \(r - 1\) to
compute the best we can get for each cell. For example, at the second row, we
chose \(10\) for its maximum value since it’s the value we get from \(5 +
\max(5 + 0, 1 - 1, 6 - 2)\).
More formally, if \(f(r, c)\) is the maximum number of points we can get at cell
\((r, c)\) then we can arrive at the following recurrence based on this idea:
With the above recurrence in place, the solution to our problem is given by:
\[\smash{\displaystyle\max_{0 \leq c < N}} f(M - 1, c)\]
We can implement the idea above with the following C++ code:
This is better than our brute force approach, but we are at a time complexity of
\(\mathcal{O}(M \times N^2)\), which is still not good enough to get accepted.
In order to improve the time complexity, let’s focus on what we are doing to
compute \(f(r, c)\) for \(r \neq 0\):
Can we avoid iterating through all possible values of \(c_{prev}\) for every
\((r, c)\) pair? If we could produce a function \(g(r, c)\) that would give us
the best selection from the previous row for a given \(c\) column we could
rewrite our recurrence as:
To produce \(g(r, c)\) it is important to notice that at any given column \(c\)
we have three options: we either don’t move horizontally (so there’s no
penalty), or we either go left or right. In essence, we have that \(g(r, c) =
\max(points[r][c], \operatorname{left}(r, c), \operatorname{right}(r, c))\),
with \(\operatorname{left}(r, c)\) being the maximum value we can get by going
left of \(c\) and \(\operatorname{right}(r, c)\) being the maximum value we can
get by going right of \(c\). We are now left with the task of efficiently
producing \(\operatorname{left}\) and \(\operatorname{right}\).
If we suspect that there is a recurrence at place, it is often helpful to try
and investigate a possible base case and an inductive step that seems plausible.
As such, if we look at the \(\operatorname{left}\) function, we can conclude
that \(\operatorname{left}(r, 0) = f(r, 0)\), because we can’t go any left, so
the best we can get at column \(0\) is the maximum so far for cell \((r, 0)\).
For \(\operatorname{left}(r, 1)\) we can pick the maximum of either \(f(r, 1)\)
or \(\operatorname{left}(r, 0) - 1\). In other words, we either pick the value
we get from choosing the current cell or we pick the best value we have to our
left and subtract \(1\) (which is the penalty of moving right). We can
generalize \(\operatorname{left}\) as follows:
We can apply a similar strategy for our \(\operatorname{right}\) function:
\[\operatorname{right}(r, c) = \left\{
\begin{array}{ll}
f(r, c), & \mbox{if $c = N - 1$}.\\
\max(\operatorname{right}(r, c + 1) - 1, f(r, c)), & \mbox{otherwise}.
\end{array}
\right.\]
With that idea in place, we can avoid one extra inner loop.
The above solution has time complexity \(\mathcal{O}(M \times 3 \times N)\)
which simplifies to \(\mathcal{O}(M \times N)\) and is good to get accepted.
Reducing the Space Complexity
Even though the solution described above has a sufficient time complexity to be
accepted, we can reduce its space complexity with the following three
observations:
We don’t need to keep track of the maximum number of points for each cell
previously visited (our previously defined \(f\) function), since we’re only
ever interested in the previous row.
We don’t need to have separate vectors for \(\operatorname{left}\) and
\(\operatorname{right}\). Since we’re always computing the maximum of both
functions, we can reuse the same vector.
At every new row, we’re only interested in the \(\operatorname{left}\) and
\(\operatorname{right}\) functions (which we saw previously that can be
combined into one lookup vector), so we can reuse the vector of the maximum
values for the previous row (the lookup for our \(f\) function) for that.
If we put those ideas into practice we arrive at the following solution, which
still has a time complexity of \(\mathcal{O}(M \times N)\) but an extra space
complexity of just \(\mathcal{O}(N)\), which is better than the previous
\(\mathcal{O}(M \times N)\):
LeetCode is an online platform providing practice coding and
algorithmic problems. ↩
LeetCode’s daily challenges are problems from LeetCode’s database that
are meant to be solved on each day of the year. Solving them provides some
extra rewards in terms of LeetCoins and can get you a badge if you solve all
problems of a given calendar month. I have been solving them for fun and
trying to keep a streak going. ↩
We can change the queue into a stack for a depth-first search. ↩
Scala with Cats is a book about the Cats library,
which provides abstractions for functional programming in the Scala
programming language. The book provides an introduction not only to the
Cats library but also to some category theory
structures. It’s divided in two major sections: “Theory” and “Case Studies”. The
“Theory” section starts with a chapter dedicated to the way Cats is
designed around type classes and how type classes are encoded in the Scala
programming language. The section follows with dedicated chapters for different
algebraic data structures, some functional programming constructs and how they
are implemented in Cats: Monoids, Semigroups, Functors, Monads, Monad
Transformers, Semigroupal, Applicative, Foldable and Traverse. The “Case
Studies” section ties it all up with 4 practical applications of the previously
introduced structures and constructs: testing asynchronous code, map reduce,
data validation and CRDTs.
I worked through the book in March and April this year and found it engaging and
with a fast pace. Laws are presented and explained in terms of Scala code. The
exercises complement the content of the book well, particularly the ones in the
“Case Studies” section, which showcase the applications of everything that was
introduced in the “Theory” section.
I would recommend the book to anyone with moderate knowledge of the Scala
programming language who wants to learn more about typed functional programming
in general and about the Cats library in particular.
If you’re interested in my solutions to the book’s exercises, they are available
in the following posts:
The following are possible implementations of BoundedSemiLattice for Ints
and Sets. As described in the problem statement, we don’t need to model
non-negativity in the instance for Ints:
Exercise 11.3.3: Generic GCounter
The following is a possible implementation of a generic GCounter that uses
instances of CommutativeMonoid and BoundedSemiLattice:
Exercise 11.4: Abstracting GCounter to a Type Class
The implementation of an instance of the GCounter type class for Map closely
resembles the original GCounter implementation:
Exercise 11.5: Abstracting a Key Value Store
The following is a possible implementation of an instance of the KeyValueStore
type class for Map:
The and method of Check will create a new Check that calls apply on both
instances. However, we soon hit the problem of what to do if they both return a
Left:
We need a way to combine values of type E, which hints towards the need for a
Semigroup instance for E. We’re assuming that we don’t want to short-circuit
but rather accumulate all errors.
For the and implementation, we follow the algebraic data type style that is
recommended by the book:
Validated is a more appropriate data type to accumulate errors than Either.
We can also rely on the Applicative instance for Validated to avoid the
pattern match:
The or combinator should return a Valid if the left hand side is Valid or
if the left hand side is Invalid but the right hand side is Valid. If both
are Invalid, it should return an Invalid combining both errors. Due to the
latter, we can’t rely on orElse but rather have a slightly more complicated
implementation:
Exercise 10.4.2: Checks
With our previous Check renamed to Predicate, we can implement the new
Check with the proposed interface as follows, using an algebraic data type
approach as before:
flatMap is a bit weird to implement because we don’t have a flatMap for
Validated. Fortunately, we have flatMap in Either and a withEither
method in Validated that allows us to apply a function over an Either that
gets converted back to a Validated.
andThen gets implemented very similarly to flatMap, except that we don’t use
the output of the first Check to decide which other Check to use. The next
Check is already statically provided to us:
Exercise 10.4.3: Recap
The helper predicates that are introduced in this exercise make use of a lift
method on Predicate that we haven’t implemented yet. Its implementation can be
something like the following:
A Check for username can be implemented as follows, making use of the
longerThan and alphanumeric predicates.
A Check for the email address can be implemented as follows. We first check
that the string contains at least one @, then split the string, check each of
the sides and combine them back at the end:
Exercise 10.5: Kleislis
The run method on Predicate must return a A => Either[E, A]. We must rely
on the existing apply method so we also need a Semigroup instance for E:
Our checks don’t change much. We have decided to implement the email address
check slightly differently here, applying the checks directly in the split step:
The signature of foldMap can be as follows. We add Monoid as a context bound
for B:
To implement the body of foldMap, we have moved the Monoid from a context
bound to an implicit parameter list for easier access:
On the code above, we have done both steps separetely for clarity (the map and
the foldLeft), but we could have made the calls to func directly in the
combine step of foldLeft.
Exercise 9.3.3: Implementing parallelFoldMap
We can implement parallelFoldMap as follows:
We determine the amount of batches in which to split our work based on the
number of CPUs we have available. We then determine the size of our groups by
dividing the length of our input by the number of batches we’re going to run,
rounding up. We spawn a Future with foldMap for each group and join them via
Future.sequence, reducing the results of each batch with the Monoid instance
we have in scope for B.
Exercise 9.3.4: parallelFoldMap with more Cats
To implement parallelFoldMap using Foldable and Traverse we import the
respective instances from cats.instances.vector and the syntax extension
methods that allow us to call foldMap and traverse directly on Vector
instances: