Minimize the Sum of Minimum and Second Minimum Elements from All Possible Triplets

Saksham Gupta
Last Updated: May 13, 2022

Introduction

Greedy problems are often difficult to solve as they don’t have any predefined method of solving, and every new problem is a problem in itself. Thus only practice can help you to master it. But don’t you dare to worry, your best friend Ninjas is here to help you, and today we will one such frequently asked question, i.e., minimize the sum of minimum and second minimum elements from all possible triplets, which will help you to get a better grasp of the greedy algorithm.

Problem Statement

We have been given an array ‘ARR’. Our task is to minimize the sum of minimum and second minimum elements from all possible triplets in the array, with the constraint that a single element can be part of only one triplet.

Let’s understand this by the following example.

‘ARR’ = [9, 1, 3, 4, 5, 2]

Now we can form two triplets (i.e., number of elements (6) / 3 = 2). We can form a large number of triplets, but the ones that will give us the best answer are (1, 2, 9) and (3, 4, 5). Thus our answer would be 10.

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);
}

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.

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 CodeStudio to practice top problems and many more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes