795. Number of Subarrays with Bounded Maximum

795. Number of Subarrays with Bounded Maximum

 

Complexity: O(n)

Solution 1:

 int numSubarrayBoundedMax(const vector<int>& A, int l, int r)
{
  int result = 0, start = -1, end = -1;

  for(int i = 0; i < A.size(); i++){
    if(A[i] >r)start = i;
    if(A[i] >= l)end = i;
    result += end - start;
  }
  return result;
}

Solution 2:

class Solution {
public:
 enum Valutype{
  RESET,
  NEEDED,
  OK
};

int numSubarrayBoundedMax (const vector<int>& A, int L, int R) {
  int result = 0, start = -1, end = -1;

  for(int i = 0; i < A.size(); i++){
    auto val_type = A[i] > R ? RESET : A[i] >= L ? NEEDED : OK;

    switch(val_type){
      case RESET: start = i;
      case NEEDED: end = i;
      case OK: ///do nothing
      default: result += end - start;
    }
  }
  return result;
}
};

Share: