

0011-0020

11. Container With Most Water $\star\star$

class Solution {
 public:
  int maxArea(vector<int>& height) {
    int ans = 0;
    int l = 0;
    int r = height.size() - 1;

    while (l < r) {
      int h = min(height[l], height[r]);
      ans = max(ans, (r - l) * h);
      while (height[l] <= h && l < r) ++l;
      while (height[r] <= h && l < r) --r;
    }

    return ans;
  }
};

12. Integer to Roman $\star\star$

class Solution {
 public:
  string intToRoman(int num) {
    string M[4] = {"", "M", "MM", "MMM"};
    string C[10] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string X[10] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string I[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

    return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] +
           I[num % 10];
  }
};

13. Roman to Integer $\star$

class Solution {
 public:
  int romanToInt(string s) {
    int ans = 0;
    unordered_map<char, int> map = {{'I', 1},   {'V', 5},   {'X', 10},
                                    {'L', 50},  {'C', 100}, {'D', 500},
                                    {'M', 1000}};

    for (int i = 0; i < s.size(); ++i) {
      if (map[s[i]] < map[s[i + 1]])
        ans -= map[s[i]];
      else
        ans += map[s[i]];
    }

    return ans;
  }
};

14. Longest Common Prefix $\star$

class Solution {
 public:
  string longestCommonPrefix(vector<string>& strs) {
    if (strs.size() == 0) return "";
    if (strs.size() == 1) return strs[0];

    string ans;
    int min = strs[0].length();
    bool isMatch = true;

    for (int i = 1; i < strs.size(); ++i)
      min = std::min(min, (int)strs[i].length());

    for (int i = 0; i < min; ++i) {
      char c = strs[0][i];
      for (int j = 1; j < strs.size(); ++j)
        if (c != strs[j][i]) {
          isMatch = false;
          break;
        }
      if (!isMatch) break;
      ans += c;
    }

    return ans;
  }
};

15. 3Sum $\star\star$

class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;

    sort(nums.begin(), nums.end());

    for (int i = 0; i + 2 < nums.size(); ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;

      int l = i + 1;
      int r = nums.size() - 1;
      while (l < r) {
        int sum = nums[i] + nums[l] + nums[r];
        if (sum == 0) {
          ans.push_back({nums[i], nums[l], nums[r]});
          ++l;
          --r;
          while (nums[l] == nums[l - 1] && l < r) ++l;
          while (nums[r] == nums[r + 1] && l < r) --r;
        } else if (sum < 0) {
          ++l;
        } else {
          --r;
        }
      }
    }

    return ans;
  }
};

16. 3Sum Closest $\star\star$

class Solution {
 public:
  int threeSumClosest(vector<int>& nums, int target) {
    int ans = nums[0] + nums[1] + nums[2];

    sort(nums.begin(), nums.end());

    for (int i = 0; i + 2 < nums.size(); ++i) {
      int l = i + 1;
      int r = nums.size() - 1;
      while (l < r) {
        int sum = nums[i] + nums[l] + nums[r];
        if (sum == target) return sum;
        if (abs(sum - target) < abs(ans - target)) ans = sum;
        if (sum < target)
          ++l;
        else
          --r;
      }
    }

    return ans;
  }
};

17. Letter Combinations of a Phone Number $\star\star$

class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};

    vector<string> ans = {""};
    unordered_map<char, string> map = {
        {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};

    for (char i : digits) {
      vector<string> tmp;
      for (string& j : ans)
        for (char k : map[i]) tmp.push_back(j + k);
      ans = tmp;
    }

    return ans;
  }
};

18. 4Sum $\star\star$

class Solution {
 public:
  vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ans;
    vector<int> path;

    sort(nums.begin(), nums.end());
    nSum(nums, target, 0, nums.size() - 1, 4, path, ans);

    return ans;
  }

 private:
  void nSum(vector<int>& nums, int target, int l, int r, int n,
            vector<int>& path, vector<vector<int>>& ans) {
    if (r - l + 1 < n || n < 2 || target < nums[l] * n || target > nums[r] * n)
      return;
    if (n == 2) {
      while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum == target) {
          path.push_back(nums[l]);
          path.push_back(nums[r]);
          ans.push_back(path);
          path.pop_back();
          path.pop_back();
          ++l;
          while (nums[l] == nums[l - 1] && l < r) ++l;
        } else if (sum < target) {
          ++l;
        } else {
          --r;
        }
      }
      return;
    }

    for (int i = l; i <= r; ++i) {
      if (i > l && nums[i] == nums[i - 1]) continue;

      path.push_back(nums[i]);
      nSum(nums, target - nums[i], i + 1, r, n - 1, path, ans);
      path.pop_back();
    }
  }
};

19. Remove Nth Node From End of List $\star\star$

class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    auto slow = head;
    auto fast = head;

    while (n--) fast = fast->next;
    if (!fast) return head->next;

    while (fast->next) {
      slow = slow->next;
      fast = fast->next;
    }
    slow->next = slow->next->next;

    return head;
  }
};

20. Valid Parentheses $\star$

class Solution {
 public:
  bool isValid(string s) {
    stack<char> stack;

    for (char c : s) {
      if (c == '(' || c == '{' || c == '[') {
        stack.push(c);
      } else {
        if (stack.empty() ||
            (c == ')' && stack.top() != '(') ||
            (c == '}' && stack.top() != '{') ||
            (c == ']' && stack.top() != '['))
          return false;
        stack.pop();
      }
    }

    return stack.empty();
  }
};