Intuition
As we have to choose minimum elements, we will first sort the array in ascending order. Then we will traverse the array and form triplets by choosing two elements from the left side and one from the right side. This is done because we need to separate the maximum elements from each other. Thus, each maximum (starting from the rightmost) element is distributed among possible triplets. We will maintain a ‘FIN_ANS’ variable which will store the final answer.
Now let’s look at the code.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to minimize the sum of two minimum elements of every triplet.
int TwoMinTriplets(vector<int> &arr)
{
// To store the final minimized sum.
int finAns = 0;
// Sorting the array.
sort(arr.begin(), arr.end());
int i = 0;
int j = arr.size() - 1;
// Traverse the array.
while (i + 1 < j)
{
// Now, as only minimum and second minimum elements need to be added, they will be added to 'FIN_ANS'.
finAns += arr[i];
finAns += arr[i + 1];
i = i + 2;
j = j - 1;
}
// Return the ans as the result.
return finAns;
}
int main()
{
int n;
cin >> n;
vector<int> arr(n, 0);
// Taking input.
for (int i = 0; i < n; i++)
{
int element;
cin >> element;
arr[i] = element;
}
// Calling the function 'twoMinTriplets()'.
cout << TwoMinTriplets(arr);
}
You can also try this code with Online C++ Compiler
Input
6
1 9 2 4 5 3
Output
10
Time Complexity
O(N * log N), where ‘N’ is the length of the array.
As we are sorting the array it will take O(N * log N) time. And also we are looping the array, which will take O(N) time. Thus overall time complexity will be O(N * log N) + O(N) ~ O(N * log N).
Space Complexity
O(1).
As we are not using any extra space.
Check out this problem - Two Sum Problem
Key Takeaways
We saw how we solved the problem minimize the sum of minimum and second minimum elements from all possible triplets using the greedy method, i.e., by first sorting it and then picking only the required elements from the array for our final answer. Now greedy problems require a lot of practice only after one can truly master them. So what are you waiting for? Move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!
84+ registered