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

1. This solution is straight, so O(N^2)

2. Code style of cycles is mess of continue/breaks...

    for left:=i-1; left >= 0; left-- {
    	if arr[left] < arr[i] {
    		numberOfArrays++
    		continue
    	}
    	break
    }
   

why don't write as

    for left:=i-1; left >= 0; left-- {
		if arr[left] >= arr[i]  //   note  >= vs former <
			break;
		numberOfArrays++
	}

Both cases would work. But I'm agreed - your example are better.

Curious if we can do better than O(N^2) ?
Here's my solution (still O(N^2)):

class Main {

  // Add any helper functions you may need here
  

  int[] countSubarrays(int[] arr) {
    // Write your code here
    int[] results = new int[arr.length];
    
    for (int i = 0; i < arr.length; i++) {
      // find left most ind smaller than arr[i]
      
      int leftmost = i - 1;
      while (leftmost >= 0 && arr[leftmost] < arr[i]) {
        leftmost--;
      }
      
      // find right most ind small than arr[i]
      int rightmost = i + 1;
      while (rightmost < arr.length && arr[rightmost] < arr[i]) {
        rightmost++;
      }
      

      if (i == 0) {
        // no left
        results[i] = 1 + (rightmost - i - 1);
      } else if (i == arr.length - 1) {
        // no right
        results[i] = 1 + (leftmost + 1 - i);
      } else {
        results[i] = 1 + (i - leftmost - 1) + (rightmost - i - 1);
      }
      
      
    }
    
    return results;
  }

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
}