Two Smallests in Every Subarray

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

For every contiguous subarray of length >= 2, find the sum of the two smallest elements; return minimum such sum.

Algorithm

1Minimum sum of two smallest = minimum sum of two adjacent elements in sorted adjacent pairs.

Common Pitfalls

•Key insight: minimum of (first_min + second_min) over all subarrays equals minimum over adjacent pairs.

Two Smallests in Every Subarray.java

Java

// Approach: Sliding window deque tracking two smallest in current window.
// Time: O(n) Space: O(n)
class Solution {
    public int pairWithMaxSum(int[] arr) {
        int n = arr.length;
        if (n < 2)
            return -1;

        int c = arr[0] + arr[1];

        for (int i = 1; i < n - 1; i++)
            c = Math.max(c, arr[i] + arr[i + 1]);

        return c;
    }
}

Was this solution helpful?