Posts tagged as “medium”

花花酱 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 152. Maximum Product Subarray

By zxi on November 28, 2021

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution: Track high and low

Compute the low / high of prefix product, reset if nums[i] is higher than high or lower than low.

Swap low and high if nums[i] is a negative number.

e.g. [2, 3, -1, 8, -2]
nums[i] = 2, low = 2, high = 2
nums[i] = 3, low = 3, high = 2 * 3 = 6
nums[i] = -1, low = 6 * -1 = -6, high = -1
nums[i] = 8, low = -6 * 8 = -48, high = 8
nums[i] = -2, low = 8*-2 = -16, high = -48 * -2 = 96

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int ans = nums[0];

for (int i = 1, h = ans, l = ans; i < nums.size(); ++i) {

if (nums[i] < 0) swap(l, h);

l = min(nums[i], nums[i] * l);

h = max(nums[i], nums[i] * h);

ans = max(ans, h);

}

return ans;

}

};

花花酱 LeetCode 173. Binary Search Tree Iterator

By zxi on November 28, 2021

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁶
At most 10⁵ calls will be made to hasNext, and next.

Follow up:

Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Solution: In-order traversal using a stack

Use a stack to simulate in-order traversal.

Each next, we walk to the left most (smallest) node and push all the nodes along the path to the stack.

Then pop the top one t as return val, our next node to explore is the right child of t.

Time complexity: amortized O(1) for next() call.
Space complexity: O(n)

C++

// Author: Huahua

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

class BSTIterator {

public:

BSTIterator(TreeNode* root) : root_(root) {}

int next() {

while (root_) {

s_.push(root_);

root_ = root_->left;

}

TreeNode* t = s_.top(); s_.pop();

root_ = t->right;

return t->val;

}

bool hasNext() {

return (root_ || !s_.empty());

}

private:

TreeNode* root_;

stack<TreeNode*> s_;

};

/**

* Your BSTIterator object will be instantiated and called as such:

* BSTIterator* obj = new BSTIterator(root);

* int param_1 = obj->next();

* bool param_2 = obj->hasNext();

Posts tagged as “medium”

花花酱 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 143. Reorder List

Solution: Three steps

C++

花花酱 LeetCode 152. Maximum Product Subarray

Solution: Track high and low

C++

花花酱 LeetCode 173. Binary Search Tree Iterator

Solution: In-order traversal using a stack

C++