Two Smallests in Every Subarray

Given an array of integers arr, the task is to find and return the maximum sum of the smallest and second smallest element among all possible subarrays of size greater than one. If it is not possible, then return -1.

Examples:

Input: arr = [4, 3, 1, 5, 6]
Output: 11
Explanation: Subarrays with smallest and second smallest are,
Subarray: [4, 3], smallest = 3, second smallest = 4, sum = 7
Subarray: [4, 3, 1], smallest = 1, second smallest = 3, sum = 4
Subarray: [4, 3, 1, 5], smallest = 1, second smallest = 3, sum = 4
Subarray: [4, 3, 1, 5, 6], smallest = 1, second smallest = 3, sum = 4
Subarray: [3, 1], smallest = 1, second smallest = 3, sum = 4
Subarray: [3, 1, 5], smallest = 1, second smallest = 3, sum = 4
Subarray: [3, 1, 5, 6], smallest = 1, second smallest = 3, sum = 4
Subarray: [1, 5], smallest = 1, second smallest = 5, sum = 6
Subarray: [1, 5, 6] ,smallest = 1, second smallest = 5, sum = 6
Subarray: [5, 6], smallest = 5, second smallest = 6, sum = 11
Maximum sum among all above choices is, 5 + 6 = 11, hence the answer is 11.

Input: arr = [1]
Output: -1
Explanation: Here the size of array is 1, but we need minimum 2 elements. Hence, the answer is -1.

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints:
1<=arr.size()<=10⁵ 
1<=arr[i]<=10⁵

Approach 01:

Time Complexity

• First two elements sum:

  The function starts by calculating the sum of the first two elements, which takes \(O(1)\).

• Iterating through the array:

  The function then iterates through the array starting from the third element, updating the sum by adding the current element and subtracting the element two indices back. This iteration takes \(O(n)\), where \(n\) is the size of the input array.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input array, since the function iterates through the array once.

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of extra space for variables such as currentSum and maxSum. No additional data structures are used, so the space complexity is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the function only uses a constant amount of extra space regardless of the input size.