When dealing with arrays in Java, a common problem is to count the number of subarrays where the maximum element is within a given range. This problem can be both challenging and educational as it requires a good understanding of array manipulation and efficient algorithms. In this blog, we will cover the problem statement, constraints, and provide a detailed solution in Java using the sliding window technique.

Problem Statement

Given an array of integers nums and two integers left and right, return the number of contiguous subarrays where the largest element is at least left and at most right.

Example:

Input: nums = [2, 1, 4, 333], left = 2, right = 3
Output: 3
Explanation: The subarrays that satisfy the conditions are [2], [2, 1], [3].

Constraints

1. Array Length: The length of the array nums will be in the range [1, 10000].
2. Element Range: Elements in nums and the values of left and right will be in the range [0, 10000].

Approach: Sliding Window Technique

To solve this problem efficiently, we can use the sliding window technique. This involves maintaining a window that satisfies the given conditions and counting the valid subarrays within this window.

Step-by-Step Solution

1. Initialize Counters: We need three counters:

• count: To count the number of valid subarrays.
• leftCount: To count the number of elements less than left in the current window.
• rightCount: To count the number of elements less than or equal to right in the current window.

1. Traverse the Array: Loop through the array while adjusting the window to ensure that the maximum element is between left and right.
2. Update Counters: Update the counters based on the conditions and calculate the number of valid subarrays.

Java Implementation

Here is the Java implementation of the solution:

public class BoundedMaxSubarrays {

    public static void main(String[] args) {
        int[] nums = {2, 1, 4, 3};
        int left = 2;
        int right = 3;
        System.out.println(numSubarrayBoundedMax(nums, left, right));
    }

    public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
    }

    private static int countSubarrays(int[] nums, int bound) {
        int count = 0, currentCount = 0;
        for (int num : nums) {
            if (num <= bound) {
                currentCount++;
                count += currentCount;
            } else {
                currentCount = 0;
            }
        }
        return count;
    }
}

Explanation of the Solution

1. Count Subarrays Function: The function countSubarrays(int[] nums, int bound) counts the number of subarrays where the maximum element is less than or equal to bound.
2. Calculate Valid Subarrays: The total number of valid subarrays with a maximum between left and right is the difference between the subarrays with maximum <= right and the subarrays with maximum < left.

Example Walkthrough

Let’s walk through the example nums = [2, 1, 4, 3], left = 2, right = 3 step-by-step:

1. Count Subarrays with Max <= 3:

• Subarray [2] is valid.
• Subarray [2, 1] is valid.
• Subarray [1] is valid.
• Subarray [3] is valid.
• Subarray [4] is invalid as 4 > 3.
• Total: 4 subarrays.

1. Count Subarrays with Max < 2:

• Subarray [1] is valid.
• Total: 1 subarray.

1. Valid Subarrays with Max Between 2 and 3:

• Total: 4 (Max <= 3) – 1 (Max < 2) = 3.

Conclusion

The “Numbers with Bounded Maximum” problem is an excellent exercise in understanding the sliding window technique and subarray counting. By breaking down the problem and using helper functions, we can arrive at an efficient solution that works in linear time. This method ensures that we can handle large arrays and complex constraints effectively.

By following this approach, you can solve similar problems involving subarrays and bounded conditions. Happy coding!

Additional Resources

1. Sliding Window Technique
2. Subarray Problems in Competitive Programming

Read More …

Solving the Square of a Rotated Array Problem – https://kamleshsingad.com/solving-the-square-of-a-rotated-array-problem/

Differences Between Arrays and Strings in Java – https://kamleshsingad.com/differences-between-arrays-and-strings-in-java/

Mastering Bit Manipulation: Squaring a Number Using Bitwise Operations in Java – https://kamleshsingad.com/mastering-bit-manipulation-squaring-a-number-using-bitwise-operations-in-java/