Sum of Minimum and Maximum Elements of all Subarrays of Size K in Java
In this article, we will look at the sum of the minimum and maximum elements of all subarrays of size K in Java. It is the mathematical computation of the sum derived by adding the minimum and maximum elements in each continuous subarray of a particular size K in a numerical sequence or array.
Example 1:
Input: Array: [2, -5, 1, -8, 2, 9], K: 3
Output: -15
Explanation:
Subarray [2, -5, 1]: Minimum = -5, Maximum = 2, Sum = -5 + 2 = -3
Subarray [-5, 1, -8]: Minimum = -8, Maximum = 1, Sum = -8 + 1 = -7
Subarray [1, -8, 2]: Minimum = -8, Maximum = 2, Sum = -8 + 2 = -6
Subarray [-8, 2, 9]: Minimum = -8, Maximum = 9, Sum = -8 + 9 = 1
The ultimate result is [-3, -7, -6, 1], with the sum of these values being -15.
Implementation: Iterative
Let's look at how to compute the sum mentioned above of the minimum and maximum elements of all subarrays with size K.
FileName: SumOfMinMaxSubarrays.java
public class SumOfMinMaxSubarrays {
// Returns the sum of the min and max elements of all subarrays
static int sumOfKSubArray(int[] arr, int N, int k) {
// To store the final answer
int sum = 0;
// Find all subarrays
for (int i = 0; i < N; i++) {
// To store the length of the subarray
int length = 0;
for (int j = i; j < N; j++) {
// Increment the length
length++;
// When there is a subarray of size k
if (length == k) {
// To store the maximum and minimum element
int maxi = Integer.MIN_VALUE;
int mini = Integer.MAX_VALUE;
for (int m = i; m <= j; m++) {
// Find the maximum and minimum element
maxi = Math.max(maxi, arr[m]);
mini = Math.min(mini, arr[m]);
}
// Add the maximum and minimum element to the sum
sum += maxi + mini;
}
}
}
return sum;
}
public static void main(String[] args) {
int[] arr = {2, -5, 1, -8, 2, 9};
int N = arr.length;
int k = 3;
System.out.println(sumOfKSubArray(arr, N, k));
}
}
Output:
-15
Complexity Analysis:
The code's time complexity is O(N^3), where N is the length of the input array. This is due to the nested loops: the outer loop iterates over all starting indices, the middle loop over all ending indices, and the innermost loop finds the minimum and maximum values in each subarray. The code's space complexity is O(1) since it consumes a constant amount of additional space.
Implementation: Deque-based Sliding Window
The Deque-based Sliding Window technique improves subarray calculations by using a deque to effectively process components within a fixed-size window, allowing for speedy determination of minimum and maximum values during traversal.
FileName: SumOfMinMaxSubarrays1.java
import java.util.Deque;
import java.util.LinkedList;
public class SumOfMinMaxSubarrays1 {
// Function to calculate the sum of minimum and maximum elements of subarrays of size 'k'
public static int SumOfKsubArray(int arr[], int k) {
int sum = 0;
// Deque 'S' maintains indices of elements in decreasing order (useful for finding minimum)
// Deque 'G' maintains indices of elements in increasing order (useful for finding maximum)
Deque<Integer> S = new LinkedList<>(), G = new LinkedList<>();
// Process the first window of size 'k'
int i = 0;
for (i = 0; i < k; i++) {
// Remove all previous greater elements that are useless for finding minimum
while (!S.isEmpty() && arr[S.peekLast()] >= arr[i])
S.removeLast();
// Remove all previous smaller elements that are useless for finding maximum
while (!G.isEmpty() && arr[G.peekLast()] <= arr[i])
G.removeLast();
// Add the current index to both 'S' and 'G'
G.addLast(i);
S.addLast(i);
}
// Process the rest of the array elements
for (; i < arr.length; i++) {
// Add the sum of minimum and maximum elements in the current window to the final result
sum += arr[S.peekFirst()] + arr[G.peekFirst()];
// Remove elements that are out of the current window
while (!S.isEmpty() && S.peekFirst() <= i - k)
S.removeFirst();
while (!G.isEmpty() && G.peekFirst() <= i - k)
G.removeFirst();
// Remove previous greater elements that are useless for finding minimum
while (!S.isEmpty() && arr[S.peekLast()] >= arr[i])
S.removeLast();
// Remove previous smaller elements that are useless for finding maximum
while (!G.isEmpty() && arr[G.peekLast()] <= arr[i])
G.removeLast();
// Add the current index to both 'S' and 'G'
G.addLast(i);
S.addLast(i);
}
// Add the sum of minimum and maximum elements in the last window to the final result
sum += arr[S.peekFirst()] + arr[G.peekFirst()];
return sum;
}
// Main method to test the SumOfKsubArray function
public static void main(String args[]) {
int arr[] = {2, -5, 1, -8, 2, 9};
int k = 3;
System.out.println(SumOfKsubArray(arr, k));
}
}
Output:
-15
Complexity Analysis:
The time complexity of the provided code is O(N), where N represents the length of the input array. This is because each element is processed twice: once during initial window formation and again during sliding window traversal. The space complexity is O(K) due to index storage in the deque, where K is the sliding window's size. The technique efficiently maintains the deque to discover the least and maximum elements within each window, yielding a linear time complexity.