Interviews

Number of Subarrays with Bounded Maximum

user profile image
System made a post.

LeetCode 795 Number of Subarrays with Bounded Maximum

We are given an array A of positive integers, and two positive integers L and R (L <= R).
Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :

Input:
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Note:
* L, R  and A[i] will be an integer in the range [0, 10^9].
* The length of A will be in the range of [1, 50000].


    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int head = 0;
        int pre = -1;
        int count = 0;
        
        for(int i = 0; i < A.length; i++){
            if(A[i] >=  L && A[i] <= R){
                count += i - head + 1;
                pre = i;
            }
            else if(A[i] <  L){
                if(pre != -1){
                    count += pre - head + 1;
                }
            }
            else if(A[i] > R) {
                head = i + 1;
                pre = -1;
            }
        }
        return count;
    }


One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.


Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.


Free Consultation

aonecoding@gmail.com