aboutsummaryrefslogtreecommitdiff
path: root/num_subarr_bounded_max.c
diff options
context:
space:
mode:
Diffstat (limited to 'num_subarr_bounded_max.c')
-rw-r--r--num_subarr_bounded_max.c43
1 files changed, 43 insertions, 0 deletions
diff --git a/num_subarr_bounded_max.c b/num_subarr_bounded_max.c
new file mode 100644
index 0000000..3f0ae26
--- /dev/null
+++ b/num_subarr_bounded_max.c
@@ -0,0 +1,43 @@
+// 795. Number of Subarrays with Bounded Maximum
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and two integers 'left' and 'right', return the
+ * number of contiguous non empty subarrays such that the value of the maximum
+ * array element in that subarray is in the range '[left, right]'. the test
+ * cases are generated such that the answer will fit into a 32 bit integer.
+ */
+
+int helper(int *nums, int n, int left) {
+ if (!n)
+ return 0;
+ long long res = (long long)(n + 1) * n / 2;
+ int cnt = 0;
+ for (int i = 0; i < n; i++) {
+ if (nums[i] < left)
+ cnt++;
+ else {
+ res -= (cnt + 1) * cnt / 2;
+ cnt = 0;
+ }
+ }
+ res -= (cnt + 1) * cnt / 2;
+ return res;
+}
+
+int numSubarrayBoundedMax(int *nums, int numsSize, int left, int right) {
+ int ans = 0, prev = 0;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i] > right) {
+ ans += helper(&nums[prev], i - prev, left);
+ prev = i + 1;
+ }
+ ans += helper(&nums[prev], numsSize - prev, left);
+ return ans;
+}
+
+int main() {
+ int n1[] = {2, 1, 4, 3}, n2[] = {2, 9, 2, 5, 6};
+ printf("%d\n", numSubarrayBoundedMax(n1, ARRAY_SIZE(n1), 2, 3)); // expect: 3
+ printf("%d\n", numSubarrayBoundedMax(n2, ARRAY_SIZE(n2), 2, 8)); // expect: 7
+}