# Posts tagged as “subarray”

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.


Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.


Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

## Solution: Prefix Sum

ans = max{abs(prefix_sum[i] – max(prefix_sum[0:i])), abs(prefix_sum – min(prefix_sum[0:i])}

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

## C++

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).


Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3


Example 4:

Input: nums = [0,0,0], target = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

## Solution: Prefix Sum + DP

Use a hashmap index to record the last index when a given prefix sum occurs.
dp[i] := max # of non-overlapping subarrays of nums[0~i], nums[i] is not required to be included.
dp[i+1] = max(dp[i], // skip nums[i]
dp[index[sum – target] + 1] + 1) // use nums[i] to form a new subarray
ans = dp[n]

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

## C++

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

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

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.


Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.


Example 4:

Input: s = "000"
Output: 0


Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

## Solution: DP/ Prefix Sum

dp[i] := # of all 1 subarrays end with s[i].
dp[i] = dp[i-1] if s[i] == ‘1‘ else 0
ans = sum(dp)
s=1101
dp[0] = 1 // 1
dp[1] = 2 // 11, *1
dp[2] = 0 // None
dp[3] = 1 // ***1
ans = 1 + 2 + 1 = 5

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

## C++

dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)

## Python3

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:

1. 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.
2. 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:
[
"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”.

1. We just need to record the first and last occurrence of each character
2. 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”
3. 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”.
4. 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.
5. For the first valid substring, we append it to the ans array. “abbeefba” => ans = [“abbeefba”]
6. 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”]
7. 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++

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.


Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.


Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50


Constraints:

• 1 <= nums.length <= 10^3
• nums.length == n
• 1 <= nums[i] <= 100
• 1 <= left <= right <= n * (n + 1) / 2

## Solution 1: Brute Force

Find sums of all the subarrays and sort the values.

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

## Solution 2: Priority Queue/ Min Heap

For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).

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

## Solution 3: Binary Search + Sliding Window

Use binary search to find S s.t. that there are at least k subarrys have sum <= S.

Given S, we can use sliding window to count how many subarrays have sum <= S and their total sum.

ans = sums_of_first(right) – sums_of_first(left – 1).

Time complexity: O(n * log(sum(nums))
Space complexity: O(n)