

0121-0130

121. Best Time to Buy and Sell Stock $\star$

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sellOne = 0;
    int holdOne = INT_MIN;

    for (int price : prices) {
      sellOne = max(sellOne, holdOne + price);
      holdOne = max(holdOne, -price);
    }

    return sellOne;
  }
};

122. Best Time to Buy and Sell Stock II $\star$

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sell = 0;
    int hold = INT_MIN;

    for (int price : prices) {
      sell = max(sell, hold + price);
      hold = max(hold, sell - price);
    }

    return sell;
  }
};

123. Best Time to Buy and Sell Stock III $\star\star\star$

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sellTwo = 0;
    int holdTwo = INT_MIN;
    int sellOne = 0;
    int holdOne = INT_MIN;

    for (int price : prices) {
      sellTwo = max(sellTwo, holdTwo + price);
      holdTwo = max(holdTwo, sellOne - price);
      sellOne = max(sellOne, holdOne + price);
      holdOne = max(holdOne, -price);
    }

    return sellTwo;
  }
};

124. Binary Tree Maximum Path Sum $\star\star\star$

class Solution {
 public:
  int maxPathSum(TreeNode* root) {
    helper(root);

    return ans;
  }

 private:
  int ans = INT_MIN;

  int helper(TreeNode* root) {
    if (!root) return 0;

    int left = max(helper(root->left), 0);
    int right = max(helper(root->right), 0);
    ans = max(ans, root->val + left + right);

    return root->val + max(left, right);
  }
};

125. Valid Palindrome $\star$

class Solution {
 public:
  bool isPalindrome(string s) {
    int l = 0;
    int r = s.length() - 1;

    while (l < r) {
      while (l < r && !isalnum(s[l])) ++l;
      while (l < r && !isalnum(s[r])) --r;
      if (tolower(s[l]) != tolower(s[r])) return false;
      ++l;
      --r;
    }

    return true;
  }
};

126. Word Ladder II $\star\star\star$

class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    vector<vector<string>> ans;
    unordered_set<string> set(wordList.begin(), wordList.end());

    if (!set.count(endWord)) return ans;

    unordered_set<string> set1 = {beginWord};
    unordered_map<string, vector<string>> map;
    bool isFound = false;

    while (!set1.empty() && !isFound) {
      for (const string& word : set1) set.erase(word);
      unordered_set<string> tempSet;
      for (const string& parent : set1) {
        string word = parent;
        for (int i = 0; i < word.length(); ++i) {
          char c = word[i];
          for (char j = 'a'; j <= 'z'; ++j) {
            word[i] = j;
            if (word == endWord) {
              map[parent].push_back(word);
              isFound = true;
            } else if (set.count(word) && !isFound) {
              tempSet.insert(word);
              map[parent].push_back(word);
            }
          }
          word[i] = c;
        }
      }
      swap(set1, tempSet);
    }

    if (isFound) {
      vector<string> path = {beginWord};
      dfs(map, beginWord, endWord, path, ans);
    }

    return ans;
  }

 private:
  void dfs(const unordered_map<string, vector<string>>& map, const string& word,
           const string& endWord, vector<string>& path,
           vector<vector<string>>& ans) {
    if (word == endWord) {
      ans.push_back(path);
      return;
    }
    if (map.find(word) == map.cend()) return;

    for (const string& child : map.at(word)) {
      path.push_back(child);
      dfs(map, child, endWord, path, ans);
      path.pop_back();
    }
  }
};

127. Word Ladder $\star\star$

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> set(wordList.begin(), wordList.end());

    if (!set.count(endWord)) return 0;

    int ans = 0;

    unordered_set<string> set1 = {beginWord};
    unordered_set<string> set2 = {endWord};

    while (!set1.empty() && !set2.empty()) {
      ++ans;
      if (set1.size() > set2.size()) swap(set1, set2);
      unordered_set<string> tempSet;
      for (string word : set1)
        for (int i = 0; i < word.length(); ++i) {
          char c = word[i];
          for (char j = 'a'; j <= 'z'; ++j) {
            word[i] = j;
            if (set2.count(word)) return ans + 1;
            if (!set.count(word)) continue;
            set.erase(word);
            tempSet.insert(word);
          }
          word[i] = c;
        }
      swap(set1, tempSet);
    }

    return 0;
  }
};

128. Longest Consecutive Sequence $\star\star\star$

class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    int ans = 0;
    unordered_set<int> set(nums.begin(), nums.end());

    for (long num : nums)
      if (!set.count(num - 1)) {
        int length = 0;
        while (set.count(num++)) ++length;
        ans = max(ans, length);
      }

    return ans;
  }
};

129. Sum Root to Leaf Numbers $\star\star$

class Solution {
 public:
  int sumNumbers(TreeNode* root) {
    int ans = 0;
    int path = 0;

    dfs(root, path, ans);

    return ans;
  }

 private:
  void dfs(TreeNode* root, int& path, int& ans) {
    if (!root) return;
    if (!root->left && !root->right) {
      path = path * 10 + root->val;
      ans += path;
      path = (path - root->val) / 10;
      return;
    }

    path = path * 10 + root->val;
    dfs(root->left, path, ans);
    dfs(root->right, path, ans);
    path = (path - root->val) / 10;
  }
};

130. Surrounded Regions $\star\star$

class Solution {
 public:
  void solve(vector<vector<char>>& board) {
    if (board.empty()) return;

    const int m = board.size();
    const int n = board[0].size();

    for (int i = 0; i < m; ++i) {
      dfs(board, i, 0);
      dfs(board, i, n - 1);
    }

    for (int j = 1; j < n - 1; ++j) {
      dfs(board, 0, j);
      dfs(board, m - 1, j);
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) board[i][j] = board[i][j] == '.' ? 'O' : 'X';
  }

 private:
  void dfs(vector<vector<char>>& board, int i, int j) {
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() ||
        board[i][j] != 'O')
      return;

    board[i][j] = '.';

    dfs(board, i, j + 1);
    dfs(board, i, j - 1);
    dfs(board, i + 1, j);
    dfs(board, i - 1, j);
  }
};