1.
Introduction
2.
Problem Statement
3.
Intuition
4.
Code
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Saksham Gupta
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

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!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems