Find the Number of Subarrays Where Boundary Elements Are Maximum in Java
The following article explores the concept of subarrays, the fundamental building blocks of computational tasks, and the problem of counting subarrays where boundary elements reach maximum values. It involves various algorithmic approaches, practical implementations, and the broader implications of subarray manipulation and maximum value identification.
Example1:
Input: nums = [1,4,3,3,2]
Output: 6
Explanation: The output is 6 because there are 6 subarrays where all elements are maximum, which are [1,4], [1,4,3], [1,4,3,3], [1,4,3,3,2], [4,3], and [4,3,3,2].
Example2:
Input: nums = [3, 3, 3]
Output: 6
Explanation: Despite all elements being the same (3), each subarray is considered separately as each subarray's boundary elements are maximum. Thus, the total count remains 6.
Using Brute-Force Approach
Algorithm
Step 1: Initialize the counter variable to track maximum boundary elements.
Step 2: Iterates through each element of the array.
Step 3: Initialize the variable to store the maximum value encountered so far.
Step 4: Iterates through the array starting from the current element.
Step 5: Updates maximum value encountered so far.
Step 6: If current and maximum values are equal, increments counter.
Step 7: Repeats steps 4-6 for all elements.
Step 8: Returns final count of subarrays with maximum boundary elements.
Here is an implementation of finding the number of subarrays where boundary elements are maximum using a brute-force approach :
FileName:SubarraysWithMaxBoundary.java
public class SubarraysWithMaxBoundary { // Method to count subarrays with maximum boundary elements using brute force approach public static int countSubarraysWithMaxBoundaryBruteForce(int[] arr) { int count = 0; int n = arr.length; for (int i = 0; i < n; i++) { int max = arr[i]; // Iterate from the current element to the end of the array for (int j = i; j < n; j++) { max = Math.max(max, arr[j]); // Update max value with maximum element encountered so far // If both boundary elements of the subarray are maximum, the increment count if (arr[i] == max && arr[j] == max) { count++; } } } return count; } public static void main(String[] args) { int[] arr = {1, 4, 3, 3, 2}; System.out.println(countSubarraysWithMaxBoundaryBruteForce(arr)); }
Output:
6
Complexity analysis: The above approach's time complexity is O(n^2) due to nested loops iterating through the input array `arr`. In contrast, its space complexity is O(1) due to constant additional space usage in variables like `count`, `n`, `max`, `i', and `j`.
Using Monotonic Stack Approach
Algorithm
Step 1: Initialize an empty stack for integer pairs.
Step 2: Initialize a variable for the result.
Step 3: Iterate through each element in the input array.
Step 4: Remove elements from the stack until it's empty or the top element's number is less than the current number.
Step 5: Push a new pair `[current number, 0]` onto the stack if empty or the top element's number is greater than the current number.
Step 6: Increase the count of subarrays with odd numbers by the top element's count.
Step 7: Return the result representing the total count of odd subarrays.
Here is an implementation of finding the number of subarrays where boundary elements are maximum using a monotonic stack approach :
FileName: SubarraysCounter.java
import java.util.ArrayDeque; public class SubarraysCounter { // Method to count the number of subarrays with odd numbers public long countSubarraysWithOddNumbers(int[] nums) { ArrayDequestack = new ArrayDeque<>(); long result = 0; for (int num : nums) { // Pop elements from the stack until it's empty or the top element's number is greater than the current number while (!stack.isEmpty() && stack.peek()[0] < num) stack.pop(); // If the stack is empty or the top element's number is greater than the current number, // push a new pair [current number, 0] onto the stack if (stack.isEmpty() || stack.peek()[0] > num) stack.push(new int[]{num, 0}); // Increment the count of subarrays with odd numbers by the count of the top element in the stack result += ++stack.peek()[1]; } return result; // Return the total count of subarrays with odd numbers } public static void main(String[] args) { SubarraysCounter counter = new SubarraysCounter(); int[] nums = {1,4,3,3,2}; System.out.println(counter.countSubarraysWithOddNumbers(nums)); } }
Output:
6
Complexity analysis: The above approach's time complexity is O(n), as it iterates through the input array `nums` once, with operations like pushing and popping taking constant time. The space complexity is O(n), as the stack size can grow up to the input array's size.