

0081-0090

81. Search in Rotated Sorted Array II $\star\star$

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

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

    return false;
  }
};

82. Remove Duplicates from Sorted List II $\star\star$

class Solution {
 public:
  ListNode* deleteDuplicates(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;

    while (head) {
      while (head->next && head->val == head->next->val) head = head->next;
      if (prev->next == head)
        prev = prev->next;
      else
        prev->next = head->next;
      head = head->next;
    }

    return dummy.next;
  }
};

83. Remove Duplicates from Sorted List $\star$

class Solution {
 public:
  ListNode* deleteDuplicates(ListNode* head) {
    ListNode* curr = head;

    while (curr) {
      while (curr->next && curr->val == curr->next->val)
        curr->next = curr->next->next;
      curr = curr->next;
    }

    return head;
  }
};

84. Largest Rectangle in Histogram $\star\star\star$

class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {
    int ans = 0;
    stack<int> stack;

    for (int i = 0; i <= heights.size(); ++i) {
      while (!stack.empty() &&
             (i == heights.size() || heights[i] < heights[stack.top()])) {
        int h = heights[stack.top()];
        stack.pop();
        int w = stack.empty() ? i : i - stack.top() - 1;
        ans = max(ans, h * w);
      }
      stack.push(i);
    }

    return ans;
  }
};

85. Maximal Rectangle $\star\star\star$

class Solution {
 public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;

    int ans = 0;
    vector<int> temp(matrix[0].size());

    for (int i = 0; i < matrix.size(); ++i) {
      for (int j = 0; j < matrix[0].size(); ++j)
        temp[j] = matrix[i][j] == '0' ? 0 : temp[j] + 1;
      ans = max(ans, largestRectangleArea(temp));
    }

    return ans;
  }

 private:
  int largestRectangleArea(vector<int>& heights) {
    int ans = 0;
    stack<int> stack;

    for (int i = 0; i <= heights.size(); ++i) {
      while (!stack.empty() &&
             (i == heights.size() || heights[i] < heights[stack.top()])) {
        int h = heights[stack.top()];
        stack.pop();
        int w = stack.empty() ? i : i - stack.top() - 1;
        ans = max(ans, h * w);
      }
      stack.push(i);
    }

    return ans;
  }
};

86. Partition List $\star\star$

class Solution {
 public:
  ListNode* partition(ListNode* head, int x) {
    ListNode beforeHead(0);
    ListNode afterHead(0);
    ListNode* before = &beforeHead;
    ListNode* after = &afterHead;

    while (head) {
      if (head->val < x) {
        before->next = head;
        before = before->next;
      } else {
        after->next = head;
        after = after->next;
      }
      head = head->next;
    }

    after->next = NULL;
    before->next = afterHead.next;

    return beforeHead.next;
  };
};

87. Scramble String $\star\star\star$

88. Merge Sorted Array $\star$

class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int k = m + n;

    while (n > 0) {
      if (m > 0 && nums1[m - 1] > nums2[n - 1])
        nums1[--k] = nums1[--m];
      else
        nums1[--k] = nums2[--n];
    }
  }
};

89. Gray Code $\star\star$

class Solution {
 public:
  vector<int> grayCode(int n) {
    vector<int> ans = {0};

    for (int i = 0; i < n; ++i)
      for (int j = ans.size() - 1; j >= 0; --j) ans.push_back(ans[j] | 1 << i);

    return ans;
  }
};

90. Subsets II $\star\star$

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

    sort(nums.begin(), nums.end());
    dfs(nums, 0, path, ans);

    return ans;
  }

 private:
  void dfs(vector<int>& nums, int s, vector<int>& path,
           vector<vector<int>>& ans) {
    ans.push_back(path);
    if (s == nums.size()) return;

    for (int i = s; i < nums.size(); ++i) {
      if (i > s && nums[i] == nums[i - 1]) continue;
      path.push_back(nums[i]);
      dfs(nums, i + 1, path, ans);
      path.pop_back();
    }
  }
};