Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author Saksham Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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!

Previous article
Minimize the sum of minimum and second minimum elements from all possible triplets
Next article
Minimize Cost for Reducing Array by Replacing Two Elements with Sum at most K times for any Index
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass