Two Smallests in Every Subarray

? Short Summary:

In today's CODE OF THE DAY, we tackle how to find the maximum sum of the two smallest elements in adjacent pairs of a subarray. This problem combines array manipulation and optimization techniques for an efficient solution! ????

Question:

Given an array of integers, the task is to find the maximum sum of the smallest and second smallest element among all possible subarrays of size greater than one. If the array size is too small to form a subarray, return -1.

?? Problem Breakdown:

Imagine having an array of integers, and you need to figure out the best sum that can be achieved by selecting two smallest elements from subarrays of size greater than one. It sounds tricky, but with the right approach, it can be solved efficiently! ??

Example:

?? Input: arr = [4, 3, 1, 5, 6]

?? Explanation:

You need to evaluate each subarray and find the sum of the two smallest numbers within those subarrays:

• Subarray: [4, 3], sum = 7
• Subarray: [5, 6], sum = 11
• ?? The largest sum of these is 11.

?? Output: 11

Optimal Solution Approach:

1. Iterate through adjacent pairs in the array.
2. For each pair, compute the sum of the two elements.
3. Track the maximum sum encountered across all pairs.
4. If the array is too small to form valid pairs, return -1.

Code Implementation:

class Solution
{
public int pairWithMaxSum(int[] arr)
{
if(arr.length < 2)
{
return -1;
}

int n = arr.length;
int max = Integer.MIN_VALUE;

for(int i = 0; i < n-1; i++)
{
int sum = arr[i] + arr[i+1];
max = Math.max(sum, max);
}
return max;
}
}        

?? How Does the Code Work?

1. Input Check: If the array has fewer than 2 elements, return -1.
2. Loop Through Pairs: Iterate through adjacent pairs in the array and calculate their sum.
3. Maximization: Keep track of the highest sum encountered and return it at the end.

?? Why This Approach?

This approach runs in O(n) time, making it super efficient even for large arrays. The space complexity is O(1), ensuring that it uses minimal memory, no matter the size of the input.