[JS] Count contiguous subarrays

countSubarrays.js

// O(n**2)
function countSubarrays(arr) {
  
  const output = arr.map(idx => 1); 
  
  for(let i = 0; i < arr.length; i++) { 
    let stopCount = false;
    let max = arr[i];
    for(let j = i + 1; j < arr.length; j++) { 
      if(!stopCount && arr[i] > arr[j]) {
        output[i] ++;  
      }        
      else {
        stopCount = true;
      }
      
      if (arr[i] < arr[j] && max < arr[j])  {
        max = arr[j]; 
        output[j]++;
      }
    }
  }
  return output;
  
  // O(n) using stack
  function countSubarrays(arr) {
    const stack = [];
    const result = [];
    arr.forEach((num, idx) => {
      while(stack.length && stack[stack.length - 1].num < num) {
        const {idx: outIdx} = stack.pop();
        result[outIdx] = idx - outIdx;
      }
      stack.push({ num, idx });    
    });
    while(stack.length) {
      const {idx: outIdx} = stack.pop();
      result[outIdx] = arr.length - outIdx;
    }

    arr.reverse().forEach((num, idx) => {
      while(stack.length && stack[stack.length - 1].num < num) {
        const {idx: outIdx} = stack.pop();
        result[arr.length - outIdx - 1] += idx - outIdx - 1;
      }
      stack.push({ num, idx });    
    });
    while(stack.length) {
      const {idx: outIdx} = stack.pop();
      result[arr.length - outIdx - 1] += arr.length - outIdx - 1;
    }

    return result;
  }