Problem

Submissions

Hints & solutions

Discuss

Sum of minimum and maximum elements of all subarrays of size “K”

Moderate

0/80

Average time to solve is 25m

Contributed by

57 upvotes

Asked in companies

Problem statement

You are given an array consisting of N integers, and an integer, K. Your task is to determine the total sum of the minimum element and the maximum element of all subarrays of size K.

Note :

The array may contain duplicate elements.
The array can also contain negative integers.
The size of the array is at least 2.
There exists at least one such subarray of size k.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space-separated integers N and K, denoting the number of elements in the array and the size of the subarray to be considered.

The second line of each test case contains N space-separated integers, representing the elements of the array.

Output Format :

For each test case print in a new line, an integer denoting the total sum of minimum and maximum element in all subarrays of size K.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
1 <= arr[i] <= 10^9

Time Limit: 1sec

Sample Input 1 :

1
5 3
1 2 3 4 5

Sample Output 1 :

Explanation for sample input 1 :

For the subarray starting from the 0th index and ending at the 2nd index, its minimum element is 1 and the maximum element is 3. Similarly, for the next subarray starting at the 1st index and ending at the 3rd index, the minimum value is 2 and the maximum is 4. And, for the last subarray, the minimum value is 3 and the maximum is 5. So, the total sum will be 1 + 3 + 2 + 4 + 3 + 5 = 18.

Sample Input 2 :

1
6 4
2 4 7 3 8 1

Sample Output 2 :

Explanation for sample input 2 :

For the subarray starting from the 0th index and ending at the 3rd index, its minimum element is 2 and the maximum element is 7. Similarly, for the next subarray starting at the 1st index and ending at the 4th index, the minimum value is 3 and the maximum is 8. And, for the last subarray, the minimum value is 1 and the maximum is 8. So, the total sum will be 2 + 7 + 3 + 8 + 1 + 8 = 29.

Hint 1

Hint 2

Hint 3

Loop through all subarrays of size K.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive approach

The idea behind this brute force approach is to run a loop(say, loop variable i) through all the possible starting indices of such subarray.
- Run a nested loop(say, loop variable j) through the elements starting from index i up to the next K elements.
- Initialize two variables to store the minimum and maximum values of this subarray.
- At each iteration of the inner loop check and update the minimum value and the maximum value of that subarray.
- Finally, after the inner loop ends, add the maximum value and the minimum value of this subarray to our final sum.

Time Complexity

O(N*K), where N is the number of elements in the array and K is the length of the subarray.

The time complexity is O(N*K) because the outer loop will run for the order of O(N) and the inner loop will run for the order of O(K), So the total complexity is O(N*K).

Space Complexity

O(1).

As we are using constant extra memory.

(100% EXP penalty)

Sum of minimum and maximum elements of all subarrays of size “K”

Console