Sum of minimum and maximum elements of all subarrays of size k

The problem, simply

You get an array arr and a window size k. Look at every run of k boxes next to each other: boxes 0 to k - 1, then 1 to k, and so on. For each window, add its largest number and its smallest number. Give back the sum over all windows.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each window, walk through its k numbers and find the max and the min.

1. For each start i from 0 to n - k:
2. Scan arr[i] to arr[i + k - 1], keeping the max and the min.
3. Add max + min to the total.

class Solution {
    public long sumMinMax(int[] arr, int k) {
        long total = 0;
        for (int i = 0; i + k <= arr.length; i++) {
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int j = i; j < i + k; j++) {          // look at the whole window again
                max = Math.max(max, arr[j]);
                min = Math.min(min, arr[j]);
            }
            total += (long) max + min;
        }
        return total;
    }
}

How long it takes: n - k + 1 windows, k numbers each, O(n*k). Extra room: a few numbers, O(1).

Way 2: the clever way

Keep two deques (lines you can use from both ends) of positions.

• The max deque keeps positions whose values go down from front to back. Its front is the max of the window.
• The min deque keeps positions whose values go up from front to back. Its front is the min of the window.

For each new position i:

1. If a front position has slid out of the window (it is i - k or less), remove it from the front.
2. From the back of the max deque, remove every position whose value is not bigger than arr[i]. They can never be the max again. Do the same on the min deque for values not smaller.
3. Add i at the back of both deques.
4. Once the first window is full (i >= k - 1), add the two front values to the total.

import java.util.*;

class Solution {
    public long sumMinMax(int[] arr, int k) {
        Deque<Integer> maxQ = new ArrayDeque<>();   // positions, values going down
        Deque<Integer> minQ = new ArrayDeque<>();   // positions, values going up
        long total = 0;
        for (int i = 0; i < arr.length; i++) {
            if (!maxQ.isEmpty() && maxQ.peekFirst() <= i - k) maxQ.pollFirst();   // slid out
            if (!minQ.isEmpty() && minQ.peekFirst() <= i - k) minQ.pollFirst();
            while (!maxQ.isEmpty() && arr[maxQ.peekLast()] <= arr[i]) maxQ.pollLast();
            while (!minQ.isEmpty() && arr[minQ.peekLast()] >= arr[i]) minQ.pollLast();
            maxQ.addLast(i);
            minQ.addLast(i);
            if (i >= k - 1) {
                total += (long) arr[maxQ.peekFirst()] + arr[minQ.peekFirst()];
            }
        }
        return total;
    }
}

How long it takes: each position joins each deque once and leaves at most once, so O(n) in total. Extra room: each deque holds positions from one window only, O(k).

Watch out for

• Removing old fronts with if is enough here, because the window moves one step at a time, so at most one position expires per step. A while is also fine and is safer if you are unsure.
• Overflow. The sum of many windows can pass the int limit. Return a long.
• k bigger than the array means no window at all. The loop adds nothing and returns 0; check what the interviewer wants.

What interviewers ask next

• Sliding window maximum (LeetCode 239): the same max deque, but output the front for each window instead of adding.
• Longest subarray where max minus min is at most a limit: use both deques with a window that grows and shrinks, O(n).
• First negative number in every window of size k: a single queue of positions of negative numbers.
• Could a heap do it? Yes, a max heap and a min heap with lazy removal of old positions give O(n log k). The deques are faster and simpler.
• Sum of max minus min over all subarrays of every size: count for each number how many subarrays it is the max of, and how many it is the min of, using next greater and next smaller elements. O(n).

Remember this

Grown-up words: the sliding photo frame is a sliding window, the lists you can change at both ends are deques, keeping them sorted by crossing off useless entries makes them monotonic deques, and "each item joins and leaves once" is amortized O(1) per step.