Facebook: Contiguous Subarrays

Contiguous_Subarrays.go

package Facebook

import "testing"

/*
Contiguous Subarrays

You are given an array a 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 a 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 a[i]


Example:
a = [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]
*/

func countSubarrays(arr []int) []int {
	result := make([]int, len(arr))

	for i:=0; i < len(arr); i++ {
		numberOfArrays := 1

		//Move from Right to Left
		for left:=i-1; left >= 0; left-- {
			if arr[left] < arr[i] {
				numberOfArrays++
				continue
			}
			break
		}

		//Move from Left to Right
		for right:=i+1; right <len(arr); right++{
			if arr[right] < arr[i] {
				numberOfArrays++
				continue
			}

			break
		}

		result[i] = numberOfArrays
	}

	return result
}

func Test_Count_Subarrays(t *testing.T) {
	testDatas := []struct{
		arr []int
		result []int
	} {
		{
			[]int{3, 4, 1, 6, 2},
			[]int{1, 3, 1, 5, 1},
		},
	}

	IsIntArraysEquals := func (a []int, b []int) bool {
		if len(a) != len(b) {
			return false
		}
		for i, v := range a {
			if v != b[i] {
				return false
			}
		}
		return true
	}

	for _, td := range testDatas {
		r := countSubarrays(td.arr)

		if !IsIntArraysEquals(r, td.result) {
			t.Errorf("Source: %d\n Expected:%v \n Actual:  %v\n",
				td.arr,
				td.result,
				r)
		}
	}
}

Here's my take, O(n) ES2021 elegance:

function countSubarrays(arr) {
  const stack = []
  const results = Array(arr.length).fill(-1)
  
  const processEntry = (v, i) => {
    while (v > arr[stack[stack.length - 1]]){
        const top = stack.pop()
        results[top] += Math.abs(i - top)
    }
    stack.push(i)
  }
  
  arr.forEach(processEntry)
  
  //process remaining stack entries
  processEntry(Infinity, arr.length)
  
  for (var i = arr.length - 1; i >= 0; --i)
    processEntry(arr[i], i)
   
  //process remaining stack entries
  processEntry(Infinity, -1)
    
  return results
}