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)
		}
	}
}

@Oscarz90 Here is better solution:

func countSubarrays(nums []int, minK int, maxK int) int64 {
	MIN := func(v1, v2 int) int {
		if v1 < v2 {
			return v1
		}
		return v2
	}

	outCur, minCur, maxCur := -1, -1, -1
	res := int64(0)
	for i, v := range nums {
		if v > maxK || v < minK {
			outCur = i
			continue
		}
		if v == minK {
			minCur = i
		}
		if v == maxK {
			maxCur = i
		}
		tmp := MIN(minCur, maxCur)
		if outCur < tmp {
			res += int64(tmp - outCur)
		}
	}
	return res
}

Same on leetcode: https://leetcode.com/problems/count-subarrays-with-fixed-bounds/description/