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(N2)
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 subarraysint 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 Codeint 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 approachclass GFG{// Function to find minimum possible sum// of pair which breaks the array into 3// non-empty subarraysstatic 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 Codepublic 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 approachimport sys# Function to find minimum possible sum# of pair which breaks the array into 3# non-empty subarraysdef 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 Codeif __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 approachusing System;public class GFG{// Function to find minimum possible sum// of pair which breaks the array into 3// non-empty subarraysstatic 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 Codepublic 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
5
Time Complexity: O(n)
Space Complexity: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
