Huahua’s Tech Road

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

By zxi on July 25, 2020

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

Constraints:

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

Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

C++

class Solution {

public:

int numOfSubarrays(vector<int>& arr) {

const int n = arr.size();

constexpr int kMod = 1e9 + 7;

// dp[i][0] # of subarrays ends with a[i-1] have even sums.

// dp[i][1] # of subarrays ends with a[i-1] have odd sums.

vector<vector<int>> dp(n + 1, vector<int>(2));

long ans = 0;

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

if (arr[i - 1] & 1) {

dp[i][0] = dp[i - 1][1];

dp[i][1] = dp[i - 1][0] + 1;

} else {

dp[i][0] = dp[i - 1][0] + 1;

dp[i][1] = dp[i - 1][1];

}

ans += dp[i][1];

}

return ans % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int numOfSubarrays(int[] arr) {

long ans = 0, odd = 0, even = 0;

for (int x : arr) {

even += 1;

if (x % 2 == 1) {

long t = even; even = odd; odd = t;

}

ans += odd;

}

return (int)(ans % (int)(1e9 + 7));

}

Python3

# Author: Huahua

class Solution:

def numOfSubarrays(self, arr: List[int]) -> int:

ans, odd, even = 0, 0, 0

for x in arr:

if x & 1:

odd, even = even + 1, odd

else:

odd, even = odd, even + 1

ans += odd

return ans % int(1e9 + 7)

花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

By zxi on July 25, 2020

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

0 <= low <= high <= 10^9

Solution: Math

The count of odd numbers between [1, low – 1] is low / 2
e.g. low = 6, we have [1,3,5] in range [1, 5] and count is 6/2 = 3.
The count of odd numbers between [1, high] is (high + 1) / 2
e.g. high = 7, we have [1,3,5,7] in range [1, 7] and count is (7+1) / 2 = 4

Then the count of odd numbers in range [low, high] = count(1, high) – count(1, low-1)
e.g. in range [6, 7] we only have [7], count: 4 – 3 = 1

ans = (high + 1) / 2 – low / 2

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

C++

// Author: Huahua

class Solution {

public:

int countOdds(int low, int high) {

return (high + 1) / 2 - low / 2;

}

};

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

By zxi on July 19, 2020

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Solution: Brute Force w/ Optimization

Try all possible [l, r] range with pruning.
1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
2. Case 1, s = arr[l] & … & arr[n-1], s > target,
Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
if s > target, then s’ > target, we can stop outer loop as well.
Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.

Time complexity: O(n)? on average, O(n^2) in worst case.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int closestToTarget(vector<int>& arr, int target) {

const int n = arr.size();

int ans = INT_MAX;

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

int s = arr[i];

for (int j = i; j < n; ++j) {

s &= arr[j];

ans = min(ans, abs(s - target));

if (ans == 0) return 0;

if (s <= target) break; // s is decreasing.

}

if (s > target) break; // s is increasing.

}

return ans;

}

};

花花酱 LeetCode 1520. Maximum Number of Non-Overlapping Substrings

By zxi on July 19, 2020

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.

Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = "adefaddaccc"
Output: ["e","f","ccc"]
Explanation: The following are all the possible substrings that meet the conditions:
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda", we are left with "ccc" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose "ef" since it can be split into two. Therefore, the optimal way is to choose ["e","f","ccc"] which gives us 3 substrings. No other solution of the same number of substrings exist.

Example 2:

Input: s = "abbaccd"
Output: ["d","bb","cc"]
Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Greedy

Observation: If a valid substring contains shorter valid strings, ignore the longer one and use the shorter one.
e.g. “abbeefba” is a valid substring, however, it includes “bbeefb”, “ee”, “f” three valid substrings, thus it won’t be part of the optimal solution, since we can always choose a shorter one, with potential to have one or more non-overlapping substrings. For “bbeefb”, again it includes “ee” and “f”, so it won’t be optimal either. Thus, the optimal ones are “ee” and “f”.

We just need to record the first and last occurrence of each character
When we meet a character for the first time we must include everything from current pos to it’s last position. e.g. “abbeefba” | ccc, from first ‘a’ to last ‘a’, we need to cover “abbeefba”
If any character in that range has larger end position, we must extend the string. e.g. “abcabbcc” | efg, from first ‘a’ to last ‘a’, we have characters ‘b’ and ‘c’, so we have to extend the string to cover all ‘b’s and ‘c’s. Our first valid substring extended from “abca” to “abcabbcc”.
If any character in the covered range has a smallest first occurrence, then it’s an invalid substring. e.g. ab | “cbc”, from first ‘c’ to last ‘c’, we have ‘b’, but ‘b’ is not fully covered, thus “cbc” is an invalid substring.
For the first valid substring, we append it to the ans array. “abbeefba” => ans = [“abbeefba”]
If we find a shorter substring that is full covered by the previous valid substring, we replace that substring with the shorter one. e.g.
“abbeefba” | ccc => ans = [“abbeefba”]
“abbeefba” | ccc => ans = [“bbeefb”]
“abbeefba” | ccc => ans = [“ee”]
If the current substring does not overlap with previous one, append it to ans array.
“abbeefba” | ccc => ans = [“ee”]
“abbeefba” | ccc => ans = [“ee”, “f”]
“abbeefbaccc” => ans = [“ee”, “f”, “ccc”]

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

C++

// Author: Huahua

class Solution {

public:

vector<string> maxNumOfSubstrings(const string& s) {

const int n = s.length();

vector<int> l(26, INT_MAX);

vector<int> r(26, INT_MIN);

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

l[s[i] - 'a'] = min(l[s[i] - 'a'], i);

r[s[i] - 'a'] = max(r[s[i] - 'a'], i);

}

auto extend = [&](int i) -> int {

int p = r[s[i] - 'a'];

for (int j = i; j <= p; ++j) {

if (l[s[j] - 'a'] < i) // invalid substring

return -1; // e.g. a|"ba"...b

p = max(p, r[s[j] - 'a']);

}

return p;

};

vector<string> ans;

int last = -1;

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

if (i != l[s[i] - 'a']) continue;

int p = extend(i);

if (p == -1) continue;

if (i > last) ans.push_back("");

ans.back() = s.substr(i, p - i + 1);

last = p;

}

return ans;

}

};

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

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

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

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

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

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

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans

Huahua's Tech Road

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

Solution: DP

C++

Java

Python3

花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

Solution: Math

C++

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

Solution: Brute Force w/ Optimization

C++

花花酱 LeetCode 1520. Maximum Number of Non-Overlapping Substrings

Solution: Greedy

C++

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

Solution: Post order traversal + hashtable

C++

Java

Python3