Easy to understand Java Solution (Beats 99%) [Java]
The question asks us to count the subarrays where max element for that subarray lies in a particular range. It clearly means if there is say a single element in
The question asks us to count the subarrays where max element for that subarray lies in a particular range. It clearly means if there is say a single element in the subarray and we encounter another element in the array which is smaller than left, then without any hassle we can increment answer by 1, if it is out of range we need to end this subarray, and other case could be the element is within range of left and right, we can increase answer by 2 if previous element is also included, because we will include this new element also as a seperate subarray.\n\t\nConsider this example [1,2,4,3] and left = 1, right = 3.\nWe encounter 1, ans += 1  => [1]\nWe encounter 2 ans += 2   => [2],[1,2]\nWe encounter 4 ans += 0 (Out of range)\nWe encounter 3 ans += 1   => [3]\n\t\nFirst off, let us consider a brute force solution using a sliding window approach, we start from i=0 and move untill i=nums.length - 1. For each j we move from i to nums.length - 1\nand if the local maximum is within range, we increment answer by 1.\n\nBut this approach has a Time Complexity of  O(N^2) and it will lead to Time Limit Exceeded.\n\nThe code for this is as follows: \n\n```\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {\n        if(nums.length == 0)\n            return 0;\n        int ans = 0;\n        for(int i=0;i<nums.length;i++)\n        {\n            int local_maxima = 0;\n            for(int j=i;j<nums.length;j++)\n            {\n                local_maxima = Math.max(local_maxima,nums[j]);\n                if(local_maxima >= left && local_maxima <= right)\n                    ans++;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nThere is also some kind of optimization possible to make the solution of linear order. How?\n\nBy considering a window, whenever we reach element nums[i] such that nums[i] >= right, \nwe set low = i and whenever we see a element that is within range we set high = i\nand keep increment answer by high-low.\nThe code for this is as follows:\n\n```\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {\n        int high = -1;\n        int low = -1;\n        int ans = 0;\n        for(int i=0;i<nums.length;i++)\n        {\n            if(nums[i] > right)\n                low = i;\n            if(nums[i] >= left)\n                high = i;\n            ans += high - low;\n        }\n        return ans;\n    }\n}\n```\nLet us consider an example for this:\n\n[2,1,4,3], left = 2, right = 3.\n\nInitially, low = -1, high = -1\ni = 0, nums[0] = 2\nHere, nums[i] >= left\nhigh = 0 , low = -1\nans += (0-1) = 1\n\ni=1, low = -1, high = 0\nHere nums[1] = 1\nLow and high remains same, low = -1, high = 0\nans += (0-(-1) = 2\n\ni=2, low = -1, high = 0\nHere nums[i] > right\nhigh = 2, \nAlso nums[i] >= left\nhigh = 2, low = 2\nans += (2-2) = 2\n\ni=3, low = 2, high = 2\nnums[i] >= 3\nhigh = 3, low = 2\nans += (3-2) = 3\n\nSo finally we return 3.\n\nTime Complexity: O(N)\nSpace Complexity: O(1)\n\nIf you find the solution useful, please upvote it. It motivates me to write even better articles.
[]