Lecture 170:-Sum Of Min & Max Elements Of All Subarray of Size K

To find the sum of the minimum and maximum elements of all subarrays of size K in an array, you can use a data structure called a "deque" (double-ended queue) to efficiently maintain the minimum and maximum elements within a sliding window. The sliding window approach is commonly used for solving such problems efficiently.

Here's a Python implementation to calculate the sum of the minimum and maximum elements of all subarrays of size K using the deque data structure:

pythonCopy code

from collections import deque def sum_of_min_max_subarrays(arr, K): if not arr or K <= 0: return 0 n = len(arr) min_deque = deque() max_deque = deque() result = 0 # Calculate maximum elements for the first K elements for i in range(K): while min_deque and arr[i] <= arr[min_deque[-1]]: min_deque.pop() min_deque.append(i) while max_deque and arr[i] >= arr[max_deque[-1]]: max_deque.pop() max_deque.append(i) # Calculate maximum and minimum elements for remaining subarrays for i in range(K, n): result += arr[min_deque[0]] + arr[max_deque[0]] # Remove elements that are outside the current window while min_deque and min_deque[0] <= i - K: min_deque.popleft() while max_deque and max_deque[0] <= i - K: max_deque.popleft() # Remove smaller elements from the back while min_deque and arr[i] <= arr[min_deque[-1]]: min_deque.pop() min_deque.append(i) # Remove larger elements from the back while max_deque and arr[i] >= arr[max_deque[-1]]: max_deque.pop() max_deque.append(i) result += arr[min_deque[0]] + arr[max_deque[0]] return result # Example usage arr = [2, 5, -1, 7, -3, -1, -2] K = 3 print(sum_of_min_max_subarrays(arr, K)) # Output: 18

This implementation uses two deques to keep track of the indices of the minimum and maximum elements within the sliding window. It iterates through the array, maintaining the deques to efficiently find the minimum and maximum elements for each subarray of size K and calculates the sum accordingly.

Keep in mind that this solution has a time complexity of O(N), where N is the length of the input array, since each element is processed only twice in the worst case.