Minimize the sum of pair which upon removing divides the Array into 3 subarrays ❤️

Given an array arr of size N, the task is to find pair of elements having minimum sum, which on removal breaks the array into 3 non-empty subarrays of the original array. Print the sum of the elements in this pair.

Input: arr[]: {4, 2, 1, 2, 4}
Output: 4
Explanation:
Minimum sum pairs are values (2, 1) and (1, 2) but selecting a pair with adjacent indices won’t break the array into 3 parts. Next minimum value pair is (2, 2), which divides the array into {4}, {1}, {4}. Hence the answer is 2 + 2 = 4.

Input: arr[] = {5, 2, 4, 6, 3, 7}
Output: 5
Explanation:
Among all the pairs which break the array into 3 subparts, pair with values (2, 3) gives minimum sum.

Naive approach: To divide the array into three subarrays. Both elements which needs to be removed should follow these conditions:

any of the endpoints (index 0 and N-1) can’t be selected.
adjacent indices can’t be selected.

So, find all combinations of possible pairs and select the one which follows the above conditions and has the lowest sum of all.

Time Complexity: O(N²)
Auxiliary space: O(N)

Efficient approach: Follow the below steps to solve this problem efficiently:

Create an array prefixMin, in which ith element represents the minimum element from 0th to ith index in array arr.
Create a variable ans, to store the final answer and initialise it with INT_MAX.
Now, run a loop for i=3 to i=N-1 (starting from 3 as 0th can’t be selected and this loop is to select the second element of the pair, which means it even can’t be started from 2 because then the only remaining options for the first element are 1 & 2, which both don’t follow the given conditions) and in each iteration change ans to the minimum value out of ans and arr[i]+prefixMin[i-2].
Print ans, after following the above steps.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
int minSumPair(int arr[], int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int prefixMin[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = INT_MAX;
 
    for (int i = 3; i < N - 1; i++) {
        ans = min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 5, 2, 4, 6, 3, 7 };
    int N = sizeof(arr) / sizeof(int);
 
    cout << minSumPair(arr, N) << endl;
 
    return 0;
}

Java

// Java implementation of the above approach
class GFG{
 
// Function to find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
static int minSumPair(int arr[], int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int []prefixMin = new int[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = Math.min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = Integer.MAX_VALUE;
 
    for (int i = 3; i < N - 1; i++) {
        ans = Math.min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array
    int arr[] = { 5, 2, 4, 6, 3, 7 };
    int N = arr.length;
 
    System.out.print(minSumPair(arr, N) +"\n");
 
}
}
 
// This code is contributed by Princi Singh

Python3

# Python 3 implementation of the above approach
import sys
 
# Function to find minimum possible sum
# of pair which breaks the array into 3
# non-empty subarrays
def minSumPair(arr, N):
    if(N < 5):
        return -1
 
    prefixMin = [0 for i in range(N)]
    prefixMin[0] = arr[0]
 
    # prefixMin[i] contains minimum element till i
    for i in range(1,N - 1,1):
        prefixMin[i] = min(arr[i], prefixMin[i - 1])
 
    ans = sys.maxsize
 
    for i in range(3,N - 1,1):
        ans = min(ans, arr[i] + prefixMin[i - 2])
 
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [5, 2, 4, 6, 3, 7]
    N = len(arr)
    print(minSumPair(arr, N))
     
    # This code is contributed by ipg201107.

C#

// C# implementation of the above approach
using System;
 
public class GFG{
 
// Function to find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
static int minSumPair(int []arr, int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int []prefixMin = new int[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = Math.Min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = int.MaxValue;
 
    for (int i = 3; i < N - 1; i++) {
        ans = Math.Min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given array
    int []arr = { 5, 2, 4, 6, 3, 7 };
    int N = arr.Length;
 
    Console.Write(minSumPair(arr, N) +"\n");
 
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find minimum possible sum
        // of pair which breaks the array into 3
        // non-empty subarrays
        function minSumPair(arr, N) {
 
            if (N < 5) {
                return -1;
            }
 
            let prefixMin = new Array(N).fill(0);
            prefixMin[0] = arr[0];
 
            // prefixMin[i] contains minimum element till i
            for (let i = 1; i < N - 1; i++) {
                prefixMin[i] = Math.min(arr[i], prefixMin[i - 1]);
            }
 
            let ans = Number.MAX_VALUE;
 
            for (let i = 3; i < N - 1; i++) {
                ans = Math.min(ans, arr[i] + prefixMin[i - 2]);
            }
 
            return ans;
        }
 
        // Driver Code
 
        // Given array
        let arr = [5, 2, 4, 6, 3, 7];
        let N = arr.length;
 
        document.write(minSumPair(arr, N));
 
     // This code is contributed by Potta Lokesh
 
    </script>

Output

Time Complexity: O(n)

Space Complexity: O(n)

Minimize the sum of pair which upon removing divides the Array into 3 subarrays

C++

Java

Python3

C#

Javascript

Contact Us