September LeetCoding Challenge, Day 12: Combination Sum III

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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:

class Solution {
private:
  vector<vector<int>> ans;
  vector<int> next;

  void dfs(int curr_sum, int next_num, int n_nums, int k, int n) {
    if (n_nums == k) {
      if (curr_sum == n)
        ans.push_back(next);
      return;
    }
    for (int i = next_num; i <= 9; ++i) {
      if (curr_sum + i > n)
        continue;
      next.push_back(i);
      dfs(curr_sum + i, i + 1, n_nums + 1, k, n);
      next.pop_back();
    }
  }

public:
  vector<vector<int>> combinationSum3(int k, int n) {
    ans.clear();
    next.clear();
    dfs(0, 1, 0, k, n);
    return ans;
  }
};

September LeetCoding Challenge, Day 11: Maximum Product Subarray

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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:

class Solution {
public:
  int maxProduct(vector<int>& nums) {
    int best_neg = -1;
    int best_pos = -1;
    int ans = nums[0];
    if (nums[0] < 0)
      best_neg = -nums[0];
    else if (nums[0] > 0)
      best_pos = nums[0];
    else {
      best_neg = -1;
      best_pos = -1;
    }
    int N = nums.size();
    for (int i = 1; i < N; ++i) {
      if (nums[i] < 0) {
        int prev_best_pos = best_pos;
        int prev_best_neg = best_neg;
        if (prev_best_neg != -1)
          best_pos = prev_best_neg * abs(nums[i]);
        else
          best_pos = -1;
        if (prev_best_pos != -1)
          best_neg = prev_best_pos * abs(nums[i]);
        else
          best_neg = abs(nums[i]);
      }
      if (nums[i] == 0) {
        best_neg = -1;
        best_pos = -1;
        ans = max(ans, 0);
      }
      if (nums[i] > 0) {
        if (best_pos != -1)
          best_pos = best_pos * nums[i];
        else
          best_pos = nums[i];
        if (best_neg != -1)
          best_neg = best_neg * nums[i];
      }
      ans = max(ans, best_pos);
    }
    return ans;
  }
};

September LeetCoding Challenge, Day 10: Bulls and Cows

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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:

class Solution {
public:
  string getHint(string secret, string guess) {
    int N = secret.size();
    int bulls = 0, cows = 0;
    map<char, int> in_secret, in_guess;
    for (int i = 0; i < N; ++i) {
      if (secret[i] == guess[i])
        bulls++;
      else {
        in_secret[secret[i]]++;
        in_guess[guess[i]]++;
      }
    }
    for (auto itr = in_guess.begin(); itr != in_guess.end(); ++itr) {
      char ch = itr->first;
      int cnt = itr->second;
      cows += min(cnt, in_secret[ch]);
    }
    ostringstream ss;
    ss << bulls << "A" << cows << "B";
    return ss.str();
  }
};

September LeetCoding Challenge, Day 9: Compare Version Numbers

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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:

class Solution {
private:
  int str_to_int(string str) {
    int ans;
    istringstream ss(str);
    ss >> ans;
    return ans;
  }

  vector<int> split_version(string version) {
    vector<int> ans;
    size_t pos;
    while ((pos = version.find('.')) != string::npos) {
      ans.push_back(str_to_int(version.substr(0, pos)));
      version.erase(0, pos + 1);
    }
    ans.push_back(str_to_int(version));
    return ans;
  }

public:
  int compareVersion(string version1, string version2) {
    vector<int> v1 = split_version(version1);
    vector<int> v2 = split_version(version2);
    int N1 = v1.size(), N2 = v2.size(), i = 0;
    while (i < N1 || i < N2) {
      int p1 = i < N1 ? v1[i] : 0;
      int p2 = i < N2 ? v2[i] : 0;
      if (p1 < p2)
        return -1;
      if (p1 > p2)
        return 1;
      i++;
    }
    return 0;
  }
};

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

September 9, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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:

class Solution {
private:
  void dfs(TreeNode* curr, int curr_value, int& curr_sum) {
    if (curr == nullptr)
      return;
    bool is_leaf = curr->left == nullptr && curr->right == nullptr;
    curr_value = curr_value * 2 + curr->val;
    if (is_leaf)
      curr_sum += curr_value;
    if (curr->left != nullptr)
      dfs(curr->left, curr_value, curr_sum);
    if (curr->right != nullptr)
      dfs(curr->right, curr_value, curr_sum);
  }

public:
  int sumRootToLeaf(TreeNode* root) {
    int ans = 0;
    dfs(root, 0, ans);
    return ans;
  }
};