Huahua’s Tech Road

花花酱 LeetCode 76. Minimum Window Substring

By zxi on November 29, 2021

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

Time complexity: O(m + n)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

string minWindow(string s, string t) {

const int n = s.length();

const int m = t.length();

vector<int> freq(128);

for (char c : t) ++freq[c];

int start = 0;

int l = INT_MAX;

for (int i = 0, j = 0, left = m; j < n; ++j) {

if (--freq[s[j]] >= 0) --left;

while (left == 0) {

if (j - i + 1 < l) {

l = j - i + 1;

start = i;

}

if (++freq[s[i++]] == 1) ++left;

}

return l == INT_MAX ? "" : s.substr(start, l);

}

};

花花酱 LeetCode 81. Search in Rotated Sorted Array II

By zxi on November 29, 2021

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
nums is guaranteed to be rotated at some pivot.
-10⁴ <= target <= 10⁴

Solution: Binary search or divide and conquer

If current range is ordered, use binary search, Otherwise, divide and conquer.

Time complexity: O(logn) best, O(n) worst
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

bool search(vector<int>& A, int target) {

return search(A, 0, A.size() - 1, target);

}

private:

bool search(vector<int>& A, int l, int r, int target) {

if (l > r) return 0;

if (l == r) return target == A[l];

int mid = l + (r - l) / 2;

if (A[l] < A[mid] && A[mid] < A[r])

return (target <= A[mid]) ? search(A, l, mid, target) : search(A, mid + 1, r, target);

else

return search(A, l, mid, target) || search(A, mid + 1, r, target);

}

};

花花酱 LeetCode 117. Populating Next Right Pointers in Each Node II

By zxi on November 29, 2021

Given a binary tree

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 6000].
-100 <= Node.val <= 100

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution -2: Group nodes into levels

Use pre-order traversal to group nodes by levels.
Connects nodes in each level.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

vector<vector<Node*>> levels;

dfs(root, 0, levels);

for (auto& nodes : levels)

for(int i = 0; i < nodes.size() - 1; ++i)

nodes[i]->next = nodes[i+1];

return root;

}

private:

void dfs(Node *root, int d, vector<vector<Node*>>& levels) {

if (!root) return;

if (levels.size() < d+1) levels.push_back({});

levels[d].push_back(root);

dfs(root->left, d + 1, levels);

dfs(root->right, d + 1, levels);

}

};

Solution -1: BFS level order traversal

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

if (!root) return root;

queue<Node*> q{{root}};

while (!q.empty()) {

int size = q.size();

Node* p = nullptr;

while (size--) {

Node* t = q.front(); q.pop();

if (p)

p->next = t, p = p->next;

else

p = t;

if (t->left) q.push(t->left);

if (t->right) q.push(t->right);

}

return root;

}

};

Solution 1: BFS w/o extra space

Populating the next level while traversing current level.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

Node* p = root;

while (p) {

Node dummy;

Node* c = &dummy;

while (p) {

if (p->left)

c->next = p->left, c = c->next;

if (p->right)

c->next = p->right, c = c->next;

p = p->next;

}

p = dummy.next;

}

return root;

}

};

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

By zxi on November 28, 2021

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Solution: DP

A special case of 花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV where k = 2.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& prices) {

constexpr int k = 2;

const int n = prices.size();

vector<int> balance(k + 1, INT_MIN);

vector<int> profit(k + 1, 0);

for (int i = 0; i < n; ++i)

for (int j = 1; j <= k; ++j) {

balance[j] = max(balance[j], profit[j - 1] - prices[i]);

profit[j] = max(profit[j], balance[j] + prices[i]);

}

return profit[k];

}

};

花花酱 LeetCode 143. Reorder List

By zxi on November 28, 2021

You are given the head of a singly linked-list. The list can be represented as:

L₀ → L₁ → … → L_{n - 1} → L_n

Reorder the list to be on the following form:

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 2} → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10⁴].
1 <= Node.val <= 1000

Solution: Three steps

Step 1: Find mid node that splits the list into two halves.
Step 2: Reverse the second half
Step 3: Merge two lists

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

void reorderList(ListNode* head) {

if (!head || !head->next) return;

ListNode* slow = head;

ListNode* fast = head;

while (fast->next && fast->next->next) {

slow = slow->next;

fast = fast->next->next;

}

ListNode* h1 = head;

ListNode* h2 = reverse(slow->next);

slow->next = nullptr;

while (h1 && h2) {

ListNode* n1 = h1->next;

ListNode* n2 = h2->next;

h1->next = h2;

h2->next = n1;

h1 = n1;

h2 = n2;

}

private:

// reverse a linked list

// returns head of the linked list

ListNode* reverse(ListNode* head) {

if (!head || !head->next) return head;

ListNode* prev = head;

ListNode* cur = head->next;

ListNode* next = cur;

while (cur) {

next = next->next;

cur->next = prev;

prev = cur;

cur = next;

}

head->next = nullptr;

return prev;

}

};

Huahua's Tech Road

花花酱 LeetCode 76. Minimum Window Substring

Solution: Hashtable + Two Pointers

C++

花花酱 LeetCode 81. Search in Rotated Sorted Array II

Solution: Binary search or divide and conquer

C++

花花酱 LeetCode 117. Populating Next Right Pointers in Each Node II

Solution -2: Group nodes into levels

C++

Solution -1: BFS level order traversal

C++

Solution 1: BFS w/o extra space

C++

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

Solution: DP

C++

花花酱 LeetCode 143. Reorder List

Solution: Three steps

C++