Given 2D array players with three components [power, endurance, id]. A player needs training if it has strictly less power and endurance than any other player. The task is to find the number of players who need training with their ids.
Examples:
Input: {{5, 4, 1}, {6, 3, 2}, {3, 5, 3}}
Output: 0
Explanation: There is no player which has strictly greater power and endurance than any other player.Input: {{1, 1, 0}, {2, 2, 1}, {3, 3, 2}}
Output: 2
0 1
Explanation: Below are the players who need training
Player with id = 0, having power = 1 and endurance = 1 is strictly less than player with id = 2.
Player with id = 1, having power = 2 and endurance = 2 is strictly less than player with id = 2.
Therefore, there are 2 players who need training.
Approach: This problem can be solved by using the Greedy Approach. Let X and Y be the two players. Player X needs training if there exists Y such that power of X < power of Y and endurance of X < endurance of Y. Follow the steps below to solve the given problem.
- Two players will be compared on the basis of two parameters.
- Sort the array players[][] in non-decreasing order of power.
- If two elements have the same power value then, consider the one first whose endurance value is greater.
- Iterate from the right side of players[][] array and keep track of maximum previous endurance.
- At the start, if any player is eligible for training store its id.
- If current player endurance is smaller than the previous maximum endurance value then increment count of players.
- Otherwise, update the maximum endurance value.
- Return the array storing all the ids of players who need training.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;bool compare(vector<int>, vector<int>);vector<int> CountOfPlayers(vector<vector<int> >& qualities){ int count = 0; int n = qualities.size(); sort(qualities.begin(), qualities.end(), [](vector<int>& entry1, vector<int>& entry2) { // If power value is equal // for both elements // Sort in descending order // according to endurance value if (entry1[0] == entry2[0]) return entry2[1] < entry1[1]; else return entry1[0] < entry2[0]; }); // Keep track of maximum // endurance value in right side int ma = 0; vector<int> res; // Traverse the array players for (int i = n - 1; i >= 0; i--) { // If current endurance // value is smaller than // max then we will // increment the count int id = qualities[i][2]; if (qualities[i][1] < ma) { // Adding player // to the final array res.push_back(id); int q1 = qualities[i + 1][0] - qualities[i][0]; int q2 = ma - qualities[i][1]; // Increase the count count++; } // Else update max value ma = max(ma, qualities[i][1]); } return res;}// Driver Codeint main(){ vector<vector<int> > qualities = { { 1, 1, 0 }, { 2, 2, 1 }, { 3, 3, 2 } }; vector<int> ans = CountOfPlayers(qualities); // Print total number of players // who need training cout << ans.size() << "\n"; // Printing id of each player for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } return 0;} // This code is contributed by rakeshsahni |
Java
// Java program for above approachimport java.io.*;import java.util.*;class GFG { private static Vector<Integer> CountOfPlayers(int[][] qualities) { int count = 0; int n = qualities.length; sort(qualities); // Keep track of maximum // endurance value in right side int max = 0; Vector<Integer> res = new Vector<Integer>(); // Traverse the array players for (int i = n - 1; i >= 0; i--) { // If current endurance // value is smaller than // max then we will // increment the count int id = qualities[i][2]; if (qualities[i][1] < max) { // Adding player // to the final array res.add(id); int q1 = qualities[i + 1][0] - qualities[i][0]; int q2 = max - qualities[i][1]; // Increase the count count++; } // Else update max value max = Math.max(max, qualities[i][1]); } return res; } // Sort on the array according // to the above approach public static void sort(int arr[][]) { // Using built-in sort // function Arrays.sort Arrays.sort(arr, new Comparator<int[]>() { @Override // Compare values according to columns public int compare(int[] entry1, int[] entry2) { // If power value is equal // for both elements // Sort in descending order // according to endurance value if (entry1[0] == entry2[0]) return entry2[1] - entry1[1]; else return entry1[0] - entry2[0]; } }); } // Driver Code public static void main(String[] args) { int[][] qualities = { { 1, 1, 0 }, { 2, 2, 1 }, { 3, 3, 2 } }; Vector<Integer> ans = CountOfPlayers(qualities); // Print total number of players // who need training System.out.println(ans.size()); // Printing id of each player for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i)); System.out.print(" "); } }} |
Python3
# Python code to implement the approachfrom functools import cmp_to_keydef cmp_sort(entry1,entry2): if (entry1[0] == entry2[0]): return entry2[1] - entry1[1] else: return entry1[0] - entry2[0]def CountOfPlayers(qualities): count = 0 n = len(qualities) qualities.sort(key = cmp_to_key(cmp_sort)) # Keep track of maximum # endurance value in right side ma = 0 res = [] # Traverse the array players for i in range(n-1,-1,-1): # If current endurance # value is smaller than # max then we will # increment the count id = qualities[i][2] if (qualities[i][1] < ma): # Adding player # to the final array res.append(id) q1 = qualities[i + 1][0] - qualities[i][0] q2 = ma - qualities[i][1] # Increase the count count += 1 # Else update max value ma = max(ma, qualities[i][1]) return res# Driver Codequalities = [[1, 1, 0], [2, 2, 1], [3, 3, 2]]ans = CountOfPlayers(qualities)# Print total number of players# who need trainingprint(len(ans))# Printing id of each playerfor i in range(len(ans)): print(ans[i] , end = " ")# This code is contributed by shinjanpatra |
C#
// C# program for above approachusing System;using System.Collections.Generic;public class GFG { private static List<int> CountOfPlayers(List<List<int>> qualities) { int count = 0; int n = qualities.Count; qualities.Sort((entry1,entry2)=>{ if (entry1[0] == entry2[0]) return entry2[1] - entry1[1]; else return entry1[0] - entry2[0]; }); // Keep track of maximum // endurance value in right side int max = 0; List<int> res = new List<int>(); // Traverse the array players for (int i = n - 1; i >= 0; i--) { // If current endurance // value is smaller than // max then we will // increment the count int id = qualities[i][2]; if (qualities[i][1] < max) { // Adding player // to the readonly array res.Add(id); int q1 = qualities[i + 1][0] - qualities[i][0]; int q2 = max - qualities[i][1]; // Increase the count count++; } // Else update max value max = Math.Max(max, qualities[i][1]); } return res; } // Driver Code public static void Main(String[] args) { int[,] qualities = { { 1, 1, 0 }, { 2, 2, 1 }, { 3, 3, 2 } }; List<List<int>> qualities = new List<List<int>> (); for(int i = 0; i < qualities.GetLength(0); i++){ List<int> l = new List<int>(); l.Add(qualities[i, 0]); l.Add(qualities[i, 1]); l.Add(qualities[i, 2]); qualitie.Add(l); } List<int> ans = CountOfPlayers(qualitie); // Print total number of players // who need training Console.WriteLine(ans.Count); // Printing id of each player for (int i = 0; i < ans.Count; i++) { Console.Write(ans[i]); Console.Write(" "); } }}// This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript Program to implement // the above approach function CountOfPlayers(qualities) { let count = 0; let n = qualities.length; qualities.sort(function (entry1, entry2) { // If power value is equal // for both elements // Sort in descending order // according to endurance value if (entry1[0] == entry2[0]) return entry2[1] - entry1[1]; else return entry1[0] - entry2[0]; }) // Keep track of maximum // endurance value in right side let ma = 0; let res = []; // Traverse the array players for (let i = n - 1; i >= 0; i--) { // If current endurance // value is smaller than // max then we will // increment the count let id = qualities[i][2]; if (qualities[i][1] < ma) { // Adding player // to the final array res.push(id); let q1 = qualities[i + 1][0] - qualities[i][0]; let q2 = ma - qualities[i][1]; // Increase the count count++; } // Else update max value ma = Math.max(ma, qualities[i][1]); } return res; } // Driver Code let qualities = [[1, 1, 0], [2, 2, 1], [3, 3, 2]]; let ans = CountOfPlayers(qualities); // Print total number of players // who need training document.write(ans.length + '<br>'); // Printing id of each player for (let i = 0; i < ans.length; i++) { document.write(ans[i] + " "); } // This code is contributed by Potta Lokesh </script> |
Output
2 1 0
Time Complexity : O(NlogN ), Where N is the size of the array.
Space Complexity : O(1).
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!
