Is it possible to get a better performance using memoization? Array algorithm

Question

I have a working solution for the problem below. I have the feeling that it could be improved using memoization, but I cannot see how to do it.

The problem:

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill 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] 

My solution (Is it O(n^2) time complexity?):

function countSubarrays(arr) { // Write your code here if(arr.length === 0) return []; if(arr.length === 1) return [1]; const checkLeft = (index) => { let count = 0; for(let i=index-1; i>=0; i--) { if(arr[i] < arr[index]) { count++; } else break; } return count; } const checkRight = (index) => { let count = 0; for(let i=index+1; i<arr.length; i++) { if(arr[i] < arr[index]) { count++; } else break; } return count; } const output = []; for(let i=0; i<arr.length; i++) { output.push(1 + checkLeft(i) + checkRight(i)) } return output; } 

Answer 1

Starting from your main question My solution (Is it O(n^2) time complexity?) the answer is yes because for every element of the array you are looking for elements at the left and at the right of it so the complexity of your algorithm is quadratic. You can erase from your code the if(arr.length === 0) return []; line because it is guarantee that array is always not empty.

It is possible to reach a linear complexity O(n) using an auxiliary structure like a stack and iterating two times over the elements of your array, first one from the beginning :

function countSubarrays(arr) { const length = arr.length; const result = new Array(length).fill(1); let stack = []; for (let i = 0; i < length; ++i) { while(stack.length && arr[stack[stack.length - 1]] < arr[i]) { result[i] += result[stack.pop()]; } stack.push(i); } //code for the reversed loop I'adding after } 

Taking your [3, 4, 1, 6, 2] array example I create an initial [1, 1, 1, 1, 1] result array obtaining the [1, 2, 1, 4, 1] result array equal to the left maximum number of contiguous subarrays of arr[i] including itself.

The same algorithm can be applied to calculate the the right maximum number of contiguous subarrays of arr[i] subtracting itself in a reverse cycle, arriving to the final code :

function countSubarrays(arr) { const length = arr.length; const result = new Array(length).fill(1); let stack = []; for (let i = 0; i < length; ++i) { while(stack.length && arr[stack[stack.length - 1]] < arr[i]) { result[i] += result[stack.pop()]; } stack.push(i); } stack = []; let tmp = new Array(length).fill(1); for (let i = length - 1; i >= 0; --i) { while((stack.length) && (arr[stack[stack.length - 1]] < arr[i])) { tmp[i] += tmp[stack.pop()]; } stack.push(i); result[i] += (tmp[i] - 1); } return result; } console.log(countSubarrays([3, 4, 1, 6, 2]));