Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hey Ninjas, are you interested in a sports talk? But at the same time, do you want to be a good coder also? So why not try to solve a question related to a sports player? As we all know, power and endurance are essential elements for a player. Also, we know that a player with less power and endurance needs more training.
So, today, we will count the players who need training and have strictly less power and endurance than any other player.
Problem Statement
We are given a 2D array having three components [power, endurance, id]. A player needs training if their power and endurance are strictly less than the power and endurance of any other player. The job is to find the number of players who need training with their ids.
Sample Example
Let's take an example to understand the problem statement more clearly.
Input
{{1, 2, 1}, {2, 3, 2}, {3, 4, 3}}
Output
2
2 1
Explanation:
Let's start the explanation from the input pattern. We have a 2D array in the form of {{x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3}}. Here,
x is the power of a player.
y is the endurance of a player.
z is the id of a player.
Now coming to the output pattern, the first line indicates the number of players who need training. And the next line shows the ids of the player who needs training.
Suppose we have two players, X and Y. Player X needs training if Player Y exists, such as the power of Player X < Power of Player Y and endurance of Player X < endurance of Player Y.
Two players among the three need training in the above example, and the id of those are 2 and 1.
Confused about how they need training? Let's check it out.
The player with id = 1, having power = 1 and endurance = 2, is strictly less than the player with id = 3, whose power = 3 and endurance = 4.
The player with id = 2, having power = 2 and endurance = 3, is strictly less than the player with id = 3, whose power = 3 and endurance = 4.
Hence, these two players (with ids 1 and 2) need training.
As we have understood the problem statement and the example, let's move to the approach now.
Approach
To solve this problem, we will use the Greedy Algorithm. The greedy algorithm is an algorithmic pattern that follows the problem-solving approach of making the optimal choice at each stage, hoping to find a global optimum.
Let's now look at the algorithm for this approach.
Algorithm
We will compare two players at a time.
Initialize a variable which will contain the 2D array.
Call the function "PlayerCount" having the 2D array as an argument.
Initialize two variables, assign count = 0 and n = number of players.
Sort the abilities with respect to power such that if the power value is equal for both players, sort in descending order according to endurance value.
Now, initialize an integer variable that will track the maximum endurance. Also, initialize a variable that will hold the id of players who need training,
Iterate through the "players[][]" array from the right side, keeping account of the maximum previous endurance.
In the beginning, store the id of the player if it is eligible for the training.
Check if the current endurance of the player is less than the previous maximum endurance. If it is, then store the id and increase the count.
Else, update the maximum endurance.
Return the ids of players in the array who need training.
Print the size of the array.
Also, print the complete array, which holds the ids of players who need training.
Dry Run
The algorithm for the given problem statement is now clear. Let's move to the dry run with some input values.
We will take a 2D array as an input for the dry run. Let's take this in a variable named "abilities". So, abilities = {{1, 2, 1}, {2, 3, 2}, {3, 4, 3}}.
Now, we will call the function "PlayerCount". Inside the function, assign count = 0 and n = number of players, which is 3 in this example.
Next, it will come to the sort function, where it will check if the power of player 1 is equal to the power of player 2. The answer is false because the power of player 1 is 1, and the power of player 2 is 2.
Note: We will compare two players at a time.
Hence in the else part, it will return that power of player 1 is less than the power of player 2.
Take an integer variable, maximum = 0 and a vector res.
Inside the for loop, which will run from right to left, that is, from n-1 to 0.
when i = 2: n = 3, count = 0, maximum = 0 Initialize an integer variable id = abilities[i][2]. So, the id will be 3 in this iteration.
Check if abilities[i][1] is smaller than the maximum. The answer is false because abilities[i][1] = 4 and maximum = 0.
Else, update the maximum with abilities[i][1], which is 4. So, the new maximum is 4.
Check if i >= 0. The condition is true. Hence we will enter the loop again.
when i = 1: n = 2, count = 0, maximum = 4 Initialize an integer variable id = abilities[i][2]. So, id will be 2 in this iteration.
Check if abilities[i][1] is smaller than the maximum. The answer is true because abilities[i][1] = 3 and maximum = 4.
Push the current id (which is 2) into the res vector. Now, res = 2
Increase the count by 1. The new count is 1.
Check if i >= 0. The condition is true. Hence we will enter the loop again.
when i = 0: n = 1, count = 1, maximum = 4 Initialize an integer variable id = abilities[i][2]. So, id will be 1 in this iteration.
Check if abilities[i][1] is smaller than the maximum. The answer is true because abilities[i][1] = 2 and maximum = 4.
Push the current id (which is 1) into the res vector. Now, res = 2 1
Increase the count by 1. The new count is 2.
Check if i >= 0. The condition is false now. Hence we will not enter the loop again.
Return the vector res.
Print the size of res, which is 2 because there are 2 elements (2 1) inside res variable.
Print the res 2 1.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
bool compare(vector<int>, vector<int>);
vector<int> PlayerCount(vector<vector<int> >& abilities) {
int count = 0;
int n = abilities.size();
// Sort the players
sort(abilities.begin(), abilities.end(), [](vector<int>& val1, vector<int>& val2) {
if (val1[0] == val2[0])
return val2[1] < val1[1];
else
return val1[0] < val2[0];
});
// Store the maximum endurance
int maximum = 0;
vector<int> res;
for (int i = n - 1; i >= 0; i--) {
int id = abilities[i][2];
if (abilities[i][1] < maximum) {
res.push_back(id);
count++;
}
else
maximum = max(maximum, abilities[i][1]);
}
return res;
}
int main() {
vector<vector<int>> abilities
= {{1, 2, 1}, {2, 3, 2}, {3, 4, 3}};
vector<int> totalCount = PlayerCount(abilities);
// Number of Player(s) who need training
cout <<"Number of Player(s) = " << totalCount.size() << "\n";
// Id of Player(s) who need training
cout <<"Id of Player(s) = ";
for (int i = 0; i < totalCount.size(); i++) {
cout << totalCount[i] << " ";
}
return 0;
}
You can also try this code with Online C++ Compiler
import java.io.*;
import java.util.*;
class Solution {
private static Vector<Integer>
PlayerCount(int[][] abilities) {
int count = 0;
int n = abilities.length;
sort(abilities);
// Store the maximum endurance
int maximum = 0;
Vector<Integer> res = new Vector<Integer>();
for (int i = n - 1; i >= 0; i--) {
int id = abilities[i][2];
if (abilities[i][1] < maximum) {
res.add(id);
count++;
}
else
maximum = Math.max(maximum, abilities[i][1]);
}
return res;
}
// Sort the players
public static void sort(int arr[][]) {
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] val1, int[] val2) {
if (val1[0] == val2[0])
return val2[1] - val1[1];
else
return val1[0] - val2[0];
}
});
}
public static void main(String[] args) {
int[][] abilities = {{1, 2, 1}, {2, 3, 2}, {3, 4, 3}};
Vector<Integer> totalCount = PlayerCount(abilities);
// Number of Player(s) who need training
System.out.println("Number of Player(s) = "+totalCount.size());
// Id of Player(s) who need training
System.out.print("Id of Player(s) = ");
for (int i = 0; i < totalCount.size(); i++) {
System.out.print(totalCount.get(i));
System.out.print(" ");
}
}
}
You can also try this code with Online Java Compiler
The above code has an O(n * (log n)) time complexity. Here, n is the number of players. This is a result of the sorting function, which requires O(n * (log n)) time, and the O(n) time needed to loop through the list of player abilities.
Space Complexity
The space complexity will be O(1). The reason is we are using a constant space for storing the variables.
How many types of sorting algorithms are present in DSA?
There are many types of sorting algorithms. Some of them are Bubble Sort, Merge Sort, Insertion Sort, etc.
What is the time complexity of the sorting function?
O(n * (log n)) is the time complexity for the sorting function.
Define a 2D array.
A 2D array is a group of objects arranged in a grid with columns and rows that enables the storage and access of data using two indices.
Define an array.
An array is a group of elements that has the same data type stored in contiguous memory locations, accessed using an index or subscript to represent its position.
Which is the fastest sorting technique?
Quicksort is considered the quickest sorting algorithm because its time complexity is O( N * (log N)) in the best and almost average case scenarios, and in the worst case, it goes up to O (N ^ 2). Thus, it has the upper hand in most cases.
Conclusion
This article discusses the topic which will count players who need training and have strictly less power and endurance than any other player. We discussed the problem statement, sample example, algorithm, and dry run. Along with this, we have discussed the code in c++ and java and time and space complexity.
We hope this blog has helped you enhance your knowledge on the topic "count of players who need training and have strictly less power and endurance than any other player". If you want to learn more, then check out our articles.
But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
34+ registered 
