

0151-0160

151. Reverse Words in a String $\star\star$

class Solution {
 public:
  string reverseWords(string s) {
    reverse(s.begin(), s.end());
    reverseWords(s, 0, 0);

    return cleanSpaces(s, 0, 0);
  }

 private:
  void reverseWords(string& s, int i, int j) {
    while (i < s.length()) {
      while (i < j || i < s.length() && s[i] == ' ') ++i;
      while (j < i || j < s.length() && s[j] != ' ') ++j;
      reverse(s.begin() + i, s.begin() + j);
    }
  }

  string cleanSpaces(string& s, int i, int j) {
    while (j < s.length()) {
      while (j < s.length() && s[j] == ' ') ++j;
      while (j < s.length() && s[j] != ' ') s[i++] = s[j++];
      while (j < s.length() && s[j] == ' ') ++j;
      if (j < s.length()) s[i++] = ' ';
    }

    return s.substr(0, i);
  }
};

152. Maximum Product Subarray $\star\star$

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    int ans = nums[0];
    int prevMin = nums[0];
    int prevMax = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
      int min = prevMin * nums[i];
      int max = prevMax * nums[i];
      prevMin = std::min(nums[i], std::min(min, max));
      prevMax = std::max(nums[i], std::max(min, max));
      ans = std::max(ans, prevMax);
    }

    return ans;
  }
};

153. Find Minimum in Rotated Sorted Array $\star\star$

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

    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] < nums[r])
        r = m;
      else
        l = m + 1;
    }

    return nums[l];
  }
};

154. Find Minimum in Rotated Sorted Array II $\star\star\star$

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

    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] == nums[r])
        --r;
      else if (nums[m] < nums[r])
        r = m;
      else
        l = m + 1;
    }

    return nums[l];
  }
};

155. Min Stack $\star$

class MinStack {
 public:
  void push(int x) {
    int min = stack.empty() ? x : std::min(stack.top().second, x);
    stack.push({x, min});
  }

  void pop() { stack.pop(); }

  int top() { return stack.top().first; }

  int getMin() { return stack.top().second; }

 private:
  std::stack<pair<int, int>> stack;
};

156. Binary Tree Upside Down $\star\star$

157. Read N Characters Given Read4 $\star$

158. Read N Characters Given Read4 II - Call multiple times $\star\star\star$

159. Longest Substring with At Most Two Distinct Characters $\star\star$

160. Intersection of Two Linked Lists $\star$

class Solution {
 public:
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return NULL;

    ListNode* a = headA;
    ListNode* b = headB;

    while (a != b) {
      a = a == NULL ? headB : a->next;
      b = b == NULL ? headA : b->next;
    }

    return a;
  }
};