花花酱 LeetCode 209. Minimum Size Subarray Sum

By zxi on April 13, 2019

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution 1: Two Pointers (Sliding Window)

Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.

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

C++

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int l = 0;

int r = 0;

int t = 0;

int ans = INT_MAX;

while (l < nums.size()) {

while (t < s && r < nums.size()) t += nums[r++];

if (t < s) break;

ans = min(ans, r - l);

t -= nums[l++];

}

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 974. Subarray Sums Divisible by K

By zxi on January 17, 2019

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5 
Output: 7 
Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

Solution: Count prefix sums

let c[i] denotes the counts of prefix_sum % K init: c[0] = 1
Whenever we end up with the same prefix sum (after modulo), which means there are subarrys end with current element that is divisible by K (0 modulo).

e.g. A = [4,5,0,-2,-3,1], K = 5
[4,5] has prefix sum of 4, which happens at index 0 [4], and index 1, [4,5]
[4,5,0] also has a prefix sum of 4, which means [4, {5,0}], [4,5, {0}] are divisible by K.

ans += (c[prefix_sum] – 1)
i = 0, prefix_sum = 0, c[(0+4)%5] = c[4] = 1, ans = 0
i = 1, prefix_sum = 4+5, c[(4+5)%5] = c[4] = 2, ans = 0+2-1=0 => [5]
i = 2, prefix_sum = 4+0, c[(4+0)%5] = c[4] = 3, ans = 1+3-1=3 => [5], [5,0], [0]
i = 3, prefix_sum = 4-2, c[(4-2)%5] = c[2] = 1, ans = 3
i = 4, prefix_sum = 2-3, c[(2-3+5)%5] = c[4] = 4, ans = 3+4-1=6 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3]
i = 5, prefix_sum = 4+1, c[(4+1)%5] = c[0] = 2, ans = 6 + 2 – 1 =>
[5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3], [4,5,0,-2,-3,1]

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

C++

class Solution {

public:

int subarraysDivByK(vector<int>& A, int K) {

vector<int> c(K);

c[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum = (sum + a % K + K) % K;

ans += c[sum]++;

}

return ans;

}

};

Python3

class Solution:

def subarraysDivByK(self, A, K):

c = [0] * K

c[0] = 1

s = 0

ans = 0

for a in A:

s = (s + a % K + K) % K

ans += c[s]

c[s] += 1

return ans

花花酱 LeetCode 907. Sum of Subarray Minimums

By zxi on September 16, 2018

Problem

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

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

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Idea

order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
1. e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
1. e.g. A = [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 1504 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

int ans = 0;

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

int left = 0;

for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);

int right = 0;

for (int j = i + 1; j < A.size() && A[j] >= A[i]; ++j, ++right);

ans = (ans + static_cast<long>(A[i]) * (left + 1) * (right + 1)) % kMod;

}

return ans;

}

};

Java

// Author: Huahua, 511 ms

class Solution {

public int sumSubarrayMins(int[] A) {

final int kMod = 1000000007;

final int n = A.length;

int ans = 0;

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

int left = 0;

for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);

int right = 0;

for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right);

ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod);

}

return ans;

}

Python3 (TLE)

# Author: Huahua, 96/100 passed

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

ans = 0

for i in range(n):

left, right = 1, 1

while i - left >= 0 and A[i - left] > A[i]:

left += 1

while i + right < n and A[i + right] >= A[i]:

right += 1

ans += A[i] * left * right

return ans % kMod

Solution2 : Monotonic Stack

Time complexity: O(n)

Space complexity: O(n)

We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span

C++

// Author: Huahua, 60 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

const int n = A.size();

vector<int> left(n);

vector<int> right(n);

stack<pair<int, int>> s;

int ans = 0;

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

int len = 1;

while (!s.empty() && s.top().first > A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

left[i] = len;

}

while (!s.empty()) s.pop();

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

int len = 1;

while (!s.empty() && s.top().first >= A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

right[i] = len;

}

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

ans = (ans + static_cast<long>(left[i]) * A[i] * right[i]) % kMod;

return ans;

}

};

Java

// Author: Huahua, 154 ms

class Solution {

public int sumSubarrayMins(int[] A) {

final int kMod = 1000000007;

final int n = A.length;

Stack<Integer> nums = new Stack<>();

Stack<Integer> lens = new Stack<>();

int[] left = new int[n];

int[] right = new int[n];

int ans = 0;

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

int len = 1;

while (!nums.empty() && nums.peek() > A[i]) {

len += lens.pop(); nums.pop();

}

nums.push(A[i]);

lens.push(len);

left[i] = len;

}

nums.clear();

lens.clear();

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

int len = 1;

while (!nums.empty() && nums.peek() >= A[i]) {

len += lens.pop(); nums.pop();

}

nums.push(A[i]);

lens.push(len);

right[i] = len;

}

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

ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod;

return ans;

}

Python3

# Author: Huahua, 376 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

s, left, right = [], [1] * n, [1] * n

for i in range(n):

while s and s[-1][0] > A[i]:

left[i] += s.pop()[1]

s.append((A[i], left[i]))

s = []

for i in range(n - 1, -1, -1):

while s and s[-1][0] >= A[i]:

right[i] += s.pop()[1]

s.append((A[i], right[i]))

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

Python3 V2

# Author: Huahua, 366 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

left, right = [1] * n, [1] * n

def fillLength(counts, start, end, step):

s = []

for i in range(start, end, step):

num = A[i] if step > 0 else A[i] - 1

while s and s[-1][0] > num:

counts[i] += s.pop()[1]

s.append((A[i], counts[i]))

fillLength(left, 0, n, 1)

fillLength(right, n - 1, -1, -1)

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

花花酱 LeetCode 643. Maximum Average Subarray I

By zxi on July 16, 2018

Problem

题目大意：找出k长度的子数组的平均值的最大值。

https://leetcode.com/problems/maximum-average-subarray-i/description/

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

Solution: Sliding Window

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 124 ms

class Solution {

public:

double findMaxAverage(vector<int>& nums, int k) {

const int n = nums.size();

int sum = 0;

int ans = INT_MIN;

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

if (i >= k) sum -= nums[i - k];

sum += nums[i];

if (i + 1 >= k) ans = max(ans, sum);

}

return static_cast<double>(ans) / k;

}

};

Problem

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Special case:

nums = [0,0], k = 0, return = True

Solution: Prefix Sum Reminder

Time complexity: O(n)

Space complexity: O(min(n, k))

// Author: Huahua

// Running time: 16 ms (<99.62%)

class Solution {

public:

bool checkSubarraySum(vector<int>& nums, int k) {

unordered_map<int, int> m; // sum % k -> first index

m[0] = -1;

int sum = 0;

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

sum += nums[i];

if (k != 0) sum %= k;

if (m.count(sum)) {

if (i - m.at(sum) > 1) return true;

} else {

m[sum] = i;

}

return false;

}

};

Posts tagged as “subarray”

花花酱 LeetCode 209. Minimum Size Subarray Sum

C++

花花酱 LeetCode 974. Subarray Sums Divisible by K

C++

Python3

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2

花花酱 LeetCode 643. Maximum Average Subarray I

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 523. Continuous Subarray Sum

Problem

Special case:

Solution: Prefix Sum Reminder

Related Problems