Huahua’s Tech Road

花花酱 LeetCode 2080. Range Frequency Queries

By zxi on November 21, 2021

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output

[null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

Solution: Hashtable + Binary Search

Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)

C++

// Author: Huahua

class RangeFreqQuery {

public:

RangeFreqQuery(vector<int>& arr) : s_(10001) {

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

s_[arr[i]].push_back(i);

}

int query(int left, int right, int value) {

const auto& m = s_[value];

if (m.empty()) return 0;

auto r = prev(upper_bound(begin(m), end(m), right));

auto l = lower_bound(begin(m), end(m), left);

return r - l + 1;

}

private:

vector<vector<int>> s_;

};

/**

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

* RangeFreqQuery* obj = new RangeFreqQuery(arr);

* int param_1 = obj->query(left,right,value);

花花酱 LeetCode 2079. Watering Plants

By zxi on November 20, 2021

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i^th plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

Water the plants in order from left to right.
After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i^th plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int wateringPlants(vector<int>& plants, int capacity) {

const int n = plants.size();

int ans = 0;

for (int i = 0, c = capacity; i < n; c -= plants[i++], ++ans) {

if (c >= plants[i]) continue;

ans += i * 2;

c = capacity;

}

return ans;

}

};

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

By zxi on November 20, 2021

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the i^th house.

Return the maximum distance between two houses with different colors.

The distance between the i^th and j^th houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Solution 1: Brute Force

Try all pairs.
Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

const int n = colors.size();

for (int d = n - 1; d > 0; --d)

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

if (colors[i] != colors[i + d])

return d;

return 0;

}

};

Solution 2: Greedy / One pass

First house or last house must be involved in the ans.

Scan the house and check with first and last house.

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

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

int ans = 0;

const int n = colors.size();

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

ans = max({ans,

i * (colors[i] != colors[0]),

(n - i - 1) * (colors[i] != colors[n - 1])});

return ans;

}

};

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

By zxi on November 20, 2021

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 10⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

Example 1:

Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

Example 2:

Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

Example 3:

Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.

Constraints:

Solution: DFS on a single path

One ancestors of node with value of 1 will have missing values greater than 1. We do a dfs on the path that from node with value 1 to the root.

Time complexity: O(n + max(nums))
Space complexity: O(n + max(nums))

C++

// Author: Huahua

class Solution {

public:

vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {

const int n = parents.size();

vector<int> ans(n, 1);

vector<int> seen(100002);

vector<vector<int>> g(n);

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

g[parents[i]].push_back(i);

function<void(int)> dfs = [&](int u) {

if (seen[nums[u]]++) return;

for (int v : g[u]) dfs(v);

};

int u = find(begin(nums), end(nums), 1) - begin(nums);

for (int l = 1; u < n && u != -1; u = parents[u]) {

dfs(u);

while (seen[l]) ++l;

ans[u] = l;

}

return ans;

}

};

花花酱 LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

By zxi on November 20, 2021

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

Example 1:

Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1^st subsequence and "cdc" for the 2^nd subsequence.
The product of their lengths is: 3 * 3 = 9.

Example 2:

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1^st subsequence and "b" (the second character) for the 2^nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1^st subsequence and "xxcxx" for the 2^nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

2 <= s.length <= 12
s consists of lowercase English letters only.

Solution 1: DFS

Time complexity: O(3ⁿ*n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

vector<string> ss(3);

size_t ans = 0;

function<void(int)> dfs = [&](int i) -> void {

if (i == n) {

if (isPalindrom(ss[0]) && isPalindrom(ss[1]))

ans = max(ans, ss[0].size() * ss[1].size());

return;

}

for (int k = 0; k < 3; ++k) {

ss[k].push_back(s[i]);

dfs(i + 1);

ss[k].pop_back();

}

};

dfs(0);

return ans;

}

};

Solution: Subsets + Bitmask + All Pairs

Time complexity: O(2²ⁿ)
Space complexity: O(2ⁿ)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

unordered_set<int> p;

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

string t;

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

if (i >> j & 1) t.push_back(s[j]);

if (isPalindrom(t))

p.insert(i);

}

int ans = 0;

for (int s1 : p)

for (int s2 : p)

if (!(s1 & s2))

ans = max(ans, __builtin_popcount(s1) * __builtin_popcount(s2));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2080. Range Frequency Queries

C++

花花酱 LeetCode 2079. Watering Plants

Solution: Simulation

C++

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

Solution 1: Brute Force

C++

Solution 2: Greedy / One pass

C++

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

Solution: DFS on a single path

C++

花花酱 LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

Solution 1: DFS

C++

Solution: Subsets + Bitmask + All Pairs

C++