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

We can use an additional data structure and keep the index of the previous greater (ignore elements less current one) element for left and right parts. Then calculate the distance between left and right index plus 1 (arr of single current element).

It's additional memory, but time complexity is O(n).

int[] countSubarrays(int[] arr) {
    int[] res = new int[arr.length];
    int[] leftMax = new int[arr.length];
    int[] rightMax = new int[arr.length];
    
    LinkedList<Integer> maxx = new LinkedList<>();
    for (int i=0; i<arr.length; i++) {
      if (maxx.isEmpty()) {
        leftMax[i] = i;
        maxx.add(i);   
      } else {
        while (!maxx.isEmpty() && arr[maxx.getLast()] < arr[i]) {
          maxx.removeLast();
        }
        
        leftMax[i] = maxx.isEmpty() ? 0 : maxx.getLast() + 1;
        maxx.add(i);
        
      }
      
    }
     
    maxx.clear();
    
    for (int i=arr.length - 1; i>=0; i--) {
      if (maxx.isEmpty()) {
        rightMax[i] = i;
        maxx.add(i);;
      } else {
        while (!maxx.isEmpty() && arr[maxx.getLast()] < arr[i]) {
          maxx.removeLast();
        }
        
        rightMax[i] = maxx.isEmpty() ? arr.length - 1 : maxx.getLast() - 1;
        maxx.add(i);
        
      }
    }
    
    for (int i=0; i<arr.length; i++) {
      res[i] = 1 + (rightMax[i] - leftMax[i]);
     }
    
    return res;
  }

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
}

@churchofthought why that solution is O(n) if you're calling a nested while within the forEach??

@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/