Huahua's Tech Road

花花酱 LeetCode 1344. Jump Game V

By zxi on February 1, 2020

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Example 4:

Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:

Input: arr = [66], d = 1
Output: 1

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

Solution: Recursion w/ Memoization

dp(i) = max{1, max{dp(j) + 1}}, if i can jump to j.
ans = max(dp(i))

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

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

int n = a.size();

vector<int> m(n);

function<int(int)> dp = [&](int i) {

if (m[i]) return m[i];

int ans = 1;

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

ans = max(ans, dp(j) + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

ans = max(ans, dp(j) + 1);

return m[i] = ans;

};

int ans = 0;

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

ans = max(ans, dp(i));

return ans;

}

};

Solution 2: DP

Time complexity: O(nlogn + n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

const int n = a.size();

vector<pair<int, int>> m(n); // <height, index>

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

m[i] = {a[i], i};

// Solve from the lowest bar.

sort(begin(m), end(m));

vector<int> dp(n, 1);

for (auto [v, i] : m) {

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

dp[i] = max(dp[i], dp[j] + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

dp[i] = max(dp[i], dp[j] + 1);

}

return *max_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1339. Maximum Product of Splitted Binary Tree

By zxi on February 1, 2020

Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation:  Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Example 3:

Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025

Example 4:

Input: root = [1,1]
Output: 1

Constraints:

Each tree has at most 50000 nodes and at least 2 nodes.
Each node’s value is between [1, 10000].

Solution: Recursion

Two passes:
First pass, compute the sum of the entire tree S.
Second pass, for each node, compute the sum of left/right subtree S_l, S_r.
ans = max{(S – S_l) * S_l, (S – S_r) * S_r}

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(TreeNode* root) {

const int kMod = 1e9 + 7;

long s = 0;

long ans = 0;

function<int(TreeNode*)> sum = [&](TreeNode* r) {

if (!r) return 0;

int sl = sum(r->left);

int sr = sum(r->right);

if (s) ans = max({ans, (s - sl) * sl, (s - sr) * sr});

return r->val + sl + sr;

};

s = sum(root);

sum(root);

return ans % kMod;

}

};

花花酱 LeetCode 912. Sort an Array

By zxi on February 1, 2020

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

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

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better

Solution 1: QuickSort

Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)

C++

// Author: Huahua, 60 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

function<void(int, int)> quickSort = [&](int l, int r) {

if (l >= r) return;

int i = l;

int j = r;

int p = nums[l + rand() % (r - l + 1)];

while (i <= j) {

while (nums[i] < p) ++i;

while (nums[j] > p) --j;

if (i <= j)

swap(nums[i++], nums[j--]);

}

quickSort(l, j);

quickSort(i, r);

};

quickSort(0, nums.size() - 1);

return nums;

}

};

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))

C++

// Author: Huahua, 54 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto [min_it, max_it] = minmax_element(begin(nums), end(nums));

int l = *min_it, r = *max_it;

vector<int> count(r - l + 1);

for (int n : nums) ++count[n - l];

int index = 0;

for (int i = 0; i < count.size(); ++i)

while (count[i]--) nums[index++] = i + l;

return nums;

}

};

Solution 2: HeapSort

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

C++

// Author: Huahua, 72ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

priority_queue<int> q(begin(nums), end(nums));

int i = nums.size();

while (!q.empty()) {

nums[--i] = q.top();

q.pop();

}

return nums;

}

};

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto heapify = [&](int i, int e) {

while (i <= e) {

int l = 2 * i + 1;

int r = 2 * i + 2;

int j = i;

if (l <= e && nums[l] > nums[j]) j = l;

if (r <= e && nums[r] > nums[j]) j = r;

if (j == i) break;

swap(nums[i], nums[j]);

swap(i, j);

}

};

const int n = nums.size();

// Init heap

for (int i = n / 2; i >= 0; i--)

heapify(i, n - 1);

// Get min.

for (int i = n - 1; i >= 1; i--) {

swap(nums[0], nums[i]);

heapify(0, i - 1);

}

return nums;

}

};

Solution 3: MergeSort

Time complexity: O(nlogn)
Space complexity: O(logn + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

vector<int> t(nums.size());

function<void(int, int)> mergeSort = [&](int l, int r) {

if (l + 1 >= r) return;

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

mergeSort(l, m);

mergeSort(m, r);

int i1 = l;

int i2 = m;

int index = 0;

while (i1 < m || i2 < r)

if (i2 == r || (i1 < m && nums[i1] < nums[i2]))

t[index++] = nums[i1++];

else

t[index++] = nums[i2++];

std::copy(begin(t), begin(t) + index, begin(nums) + l);

};

mergeSort(0, nums.size());

return nums;

}

};

Solution 4: BST

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

multiset<int> s(begin(nums), end(nums));

return {begin(s), end(s)};

}

};

花花酱 LeetCode 1302. Deepest Leaves Sum

By zxi on January 31, 2020

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int deepestLeavesSum(TreeNode* root) {

int sum = 0;

int max_depth = 0;

function<void(TreeNode*, int)> dfs = [&](TreeNode* n, int d) {

if (!n) return;

if (d > max_depth) {

max_depth = d;

sum = 0;

}

if (d == max_depth) sum += n->val;

dfs(n->left, d + 1);

dfs(n->right, d + 1);

};

dfs(root, 0);

return sum;

}

};

花花酱 LeetCode 162. Find Peak Element

By zxi on January 31, 2020

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Solution: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int findPeakElement(const vector<int> &num) {

int l = 0, r = num.size() - 1; // preventing OOB

while (l < r) {

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

// Find the first m s.t. num[m] > num[m + 1]

if (num[m] > num[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};