A detailed solution for LeetCode 1818: Minimum Absolute Sum Difference.

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

LeetCode has been running a writing contest during February and March of this year. Here’s what I submitted:

How to LeetCode: What I Learned from a Year of LeetCoding Challenge Problems.

Problem

LeetCode 322: Coin Change (Medium)

Problem Statement: You are given a set of coin denominations (integers) and an amount of change to make using only these coins. Return an integer representing the smallest number of coins sufficient to make the given amount of change. You may use as many coins of each denomination as you want. If the amount of change is impossible to make using the given coins, return -1.

Solution

This is based on a solution by Stefan Pochmann.

Coin Change is a classic dynamic programming problem. As usual for DP problems, we’ll store earlier results in an array and use them to efficiently calculate later results.

Let amount be the amount of change we need to make. Define an integer array dp[amount+1]. For each amount a, dp[a] is the minimum number of coins sufficient to make a using the coins we have checked so far. We’ll make a pass through dp for each coin denomination, updating it if we get a better result by including that coin.

The base case is dp[0] = 0, since zero coins of any denomination are sufficient to make zero dollars. For every other amount dp[i], we’ll initialize the array with dp[i] = amount+1. This is just an out-of-range value (coin values are integers no smaller than 1, so we’ll never need more than amount of them). When we’re done, the return value will be stored in dp[amount]. If dp[amount] == amount+1, there is no possible answer, so we return -1.

Once the array is initialized, we’ll update it using each coin value. Consider a coin with value c. To make an amount c, we need only one coin with that value, so dp[c] = 1. To make an amount 2c using only that coin, we need two copies of the coin, so dp[2c] = 2, and so on. Continue until the end of the array. At this point, dp stores the minimum number of c coins necessary to make each amount from 0 to amount, if it’s possible to make that amount using only c. Amounts that aren’t possible still have the initialized value, amount+1.

Now consider a second coin with value d, where c != d. To make the amount c+d using these two coins, the best we can do is use one c coin and one d coin, so dp[c+d] = 2. But making the amount c+2d doesn’t necessarily require three coins. For example, if c = 2 and d = 1, then we can make the amount 4 using just two c coins, which is a better result. To ensure that each dp[i] always contains the best result we have found so far, we need to store the smaller of these two coin counts at each step:

• Count 1: the value already in dp[i], which is the minimum coin count calculated so far for amount i.
• Count 2: dp[i-c] + 1. The current minimum count for amount i-c, plus one more coin of value c, gives us an amount i and a new count for dp[i].

Since we store the minimum value at each step and we only check one coin at at time, it doesn’t matter what order we check the coins in. We’ll get the same result when we’re done with the whole coin list regardless of whether we process the coins in sorted order, reverse sorted order, or any other order.

Pseudocode

Inputs:

• coins: an array of integers.

• amount: the target amount

  define an integer array dp of size amount+1
  initialize each element of dp to amount+1
  initialize dp[0] to 0
  
  for each coin c
      for each i from c to amount
          set dp[i] to the minimum of dp[i] and dp[i-c] + 1
  
  if dp[amount] is amount+1, return -1
  else return dp[amount]
  

Code

Coin Change on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 152: Maximum Product Subarray (Medium)

Problem Statement: Given an array of integers, return the largest possible product of a contiguous subarray.

Some notes:

• A contiguous subarray is a range of values [i..j], where i and j are positions in the input array. For this problem, the subarray must contain at least one value (which would mean i==j). You’re not allowed to pick the subarray [] and calculate the product as 0. The one exception is when the input array is empty, in which case the correct answer is 0.
• The input values are 32-bit integers (positive, negative, or zero), but they’re guaranteed to be small enough that the solution will fit in a 32-bit integer.

Solution

This is based on a solution by lee215.

The problem requires us to multiply elements of an array, so there are a few rules of multiplication to think about:

• If there’s a 0 value anywhere in the subarray, the entire product is zero. So we generally want to avoid including zeros, unless the only other alternative is a negative product.
• We’ll rarely be forced to settle for a negative product. If there’s only one negative element in the array, we can always exclude it unless the array only has one element. If there are two or more, we can include an even number of negative elements.

There are $O(n^2)$ contiguous subarrays in an array of length $n$. We could find the one with the largest product by checking every range [i..j] in the array, where $i \leq j$. But the rules above suggest a more efficient process:

• If we’re checking all ranges that start at i and we arrive at a range [i..j] whose product is zero, there’s no reason to check any further ending j values, since the product will stay at zero forever.
• If we keep track of the maximum product found so far, there are no special cases for negative elements. If the product of a range [i..j] becomes negative, then either it will become positive again when we encounter the next negative element, or if there are no negative elements remaining, we’ll just use the maximum product before we encountered the negative element.

So the key idea is: Rather than checking every starting position i and every ending position j, we can just start i at position 0 and maintain the maximum product, only moving i when the product becomes zero. That means we only need a single pass through the array. At each new j position, the product will either increase (when a[j] is positive), reset to zero (when a[j] is zero), or become negative (when a[j] is negative). In the first case, we’ll just increase the stored maximum. In the second case, we need to restart the product after the zero element. In the third case, we can just continue multiplying in case there’s another negative value coming up.

But this approach doesn’t quite work. What if our input array is [1,-2,3]? The products will be $1$, $1 \times -2 = -2$, and $-2 \times 3 = -6$. So the algorithm would return $1$ as the maximum, when it should return $3$ (for the range [2,2]).

A simple way to fix this problem is to maintain a left product that starts at position 0 and checks to the right, and a right product that starts at position len-1 and checks to the left. The answer will the maximum value found for either of these products.

Pseudocode

Variables:

• a: the input array
• len: the length of a
• max: the maximum product
• left: the product starting at the beginning of the array and moving right

• right: the product starting at the end of the array and moving left

  for i from 0 to len-1
      if left is 0, set it to a[i]
      else set it to left*a[i]
  
      if right is 0, set it to a[len-1-i]
      else set it to right*a[len-1-i]
  
      if left or right exceeds max, update max
  
  return max
  

Code

Maximum Product Subarray on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.