I could not find a solution for this in any where, after some time, I was able to come up with this solution.
It passed the predefined tests:
Contiguous Subarrays
You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfills the following conditions:
The value at index i must be the maximum element in the contiguous subarrays, and
These contiguous subarrays must either start from or end on index i.
Signature
int[] countSubarrays(int[] arr)
Input
Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000
Size N is between 1 and 1,000,000
Output
An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]
Example:
arr = [3, 4, 1, 6, 2]
output = [1, 3, 1, 5, 1]
Explanation:
For index 0 - [3] is the only contiguous subarray that starts (or ends) with 3, and the maximum value in this subarray is 3.
For index 1 - [4], [3, 4], [4, 1]
For index 2 - [1]
For index 3 - [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
For index 4 - [2]
So, the answer for the above input is [1, 3, 1, 5, 1]
function countSubarrays(arr) {
const N = arr.length;
const left = new Array(N).fill(1);
const right = new Array(N).fill(1);
let consec = 0;
let max = {
val: arr[0],
pos: 0
};
for (let i = 1; i < N; i++) {
const curr = arr[i];
const prev = arr[i - 1];
if (curr > max.val) {
left[i] += left[max.pos] + (i - max.pos - 1)
max.val = curr;
max.pos = i;
} else if (curr > prev) {
left[i] += ++consec;
} else {
consec = 0;
}
}
consec = 0;
max = {
val: arr[N - 1],
pos: N - 1
};
for (let i = N - 2; i >= 0; i--) {
const curr = arr[i];
const prev = arr[i + 1];
if (curr > max.val) {
right[i] += right[max.pos] + (max.pos - i - 1)
max.val = curr;
max.pos = i;
} else if (curr > prev) {
right[i] += ++consec;
} else {
consec = 0;
}
}
const res = new Array(N).fill(1);
for (let i = 0; i < left.length; i++) {
res[i] = left[i] + right[i] - 1
}
return res
}Test cases:
var test_1 = [3, 4, 1, 6, 2];
var expected_1 = [1, 3, 1, 5, 1];
var output_1 = countSubarrays(test_1);
check(expected_1, output_1);
var test_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [1, 2, 6, 1, 3, 1];
var output_2 = countSubarrays(test_2);
check(expected_2, output_2);