Leetcode 1996: The Number of Weak Characters in the Game
You are given a list of characters’ properties, where each character has two main attributes: attack and defense. A character is weak if another character exists with both greater attack and defense values. Return the number of weak characters in the list.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D array 'properties' of length n (2 <= n <= 100,000), where each element is an array [attack_i, defense_i] representing the attack and defense values of the ith character.
Example: properties = [[1, 2], [2, 1], [3, 4]]
Constraints:
• 2 <= properties.length <= 10^5
• 1 <= attack_i, defense_i <= 10^5
Output: Return the number of weak characters in the list.
Example: 1
Constraints:
Goal: We need to find the weak characters by comparing each character with others to check if there exists a character with strictly greater attack and defense values.
Steps:
• 1. Sort the characters by their attack value in ascending order. If two characters have the same attack value, sort them by their defense value in descending order.
• 2. Traverse through the sorted list and keep track of the highest defense value encountered.
• 3. If a character's defense value is smaller than the highest defense value encountered so far, it is a weak character.
• 4. Count and return the number of weak characters.
Goal: The constraints ensure the problem is solvable within time limits for large inputs.
Steps:
• The input array has between 2 and 100,000 elements.
• Each attack and defense value is between 1 and 100,000.
Assumptions:
• All characters have distinct attack and defense values.
• Input: properties = [[3, 5], [6, 3], [7, 8], [4, 7]]
• Explanation: Here, the character [3, 5] is weak because there exists a character [6, 3] with strictly greater attack and defense values.
Approach: We can approach this problem by sorting the characters based on attack and using a greedy strategy to keep track of the maximum defense value seen so far.
Observations:
• The problem boils down to comparing each character with others to see if it's dominated by another one.
• Sorting the array and using a greedy approach allows us to efficiently identify weak characters.
Steps:
• 1. Sort the characters based on attack values in ascending order, and by defense values in descending order if the attack values are the same.
• 2. Initialize a variable to keep track of the maximum defense value seen while traversing the list.
• 3. Traverse the list from left to right and count the number of weak characters.
• 4. Return the count of weak characters.
Empty Inputs:
• This problem assumes that the input array will always contain at least two characters.
Large Inputs:
• The algorithm should be efficient enough to handle the largest input sizes within time limits.
Special Values:
• Ensure that the sorting order works correctly when two characters have the same attack value but different defense values.
Constraints:
• The constraints ensure that the input will always be valid and the solution will work within the given limits.
class Solution {
public:
static bool comp(vector<int> &a, vector<int> &b) {
if(a[0] == b[0]) {
return a[1] > b[1];
} else return a[0] < b[0];
}
int numberOfWeakCharacters(vector<vector<int>>& prpt) {
sort(prpt.begin(), prpt.end(), comp);
int mn = INT_MIN;
int ans = 0;
for(int i = prpt.size() - 1; i >= 0; i--) {
if(prpt[i][1] < mn) ans++;
mn = max(mn, prpt[i][1]);
}
return ans;
}
1 : Class Definition
class Solution {
Defines the `Solution` class that contains the function `numberOfWeakCharacters` and the comparator function `comp`.
2 : Access Modifier
public:
Indicates the public section of the class where the methods are accessible.
3 : Comparator Function
static bool comp(vector<int> &a, vector<int> &b) {
Defines a static comparator function `comp` that is used to sort the characters in descending order of their second element and ascending order of their first element.
4 : Comparator Logic
if(a[0] == b[0]) {
Checks if the first elements of both vectors are equal.
5 : Comparator Logic
return a[1] > b[1];
If the first elements are equal, sorts based on the second element in descending order.
6 : Comparator Logic
} else return a[0] < b[0];
If the first elements are different, sorts based on the first element in ascending order.
7 : Main Function Definition
int numberOfWeakCharacters(vector<vector<int>>& prpt) {
Defines the function `numberOfWeakCharacters` which accepts a 2D vector `prpt` representing the characters and returns the number of weak characters.
8 : Sorting
sort(prpt.begin(), prpt.end(), comp);
Sorts the 2D vector `prpt` using the custom comparator `comp` to arrange the characters in the desired order.
9 : Variable Initialization
int mn = INT_MIN;
Initializes the variable `mn` to `INT_MIN` to store the maximum second element encountered during the iteration.
10 : Variable Initialization
int ans = 0;
Initializes the variable `ans` to 0 to keep track of the count of weak characters.
11 : Loop Start
for(int i = prpt.size() - 1; i >= 0; i--) {
Starts a loop from the last element of the sorted `prpt` vector and iterates backwards.
12 : Condition Check
if(prpt[i][1] < mn) ans++;
If the second element of the current vector is less than `mn`, it means the current character is weak, and the count `ans` is incremented.
13 : Update Max Value
mn = max(mn, prpt[i][1]);
Updates `mn` to be the maximum of `mn` and the second element of the current vector, ensuring that only characters weaker than the current maximum are counted.
14 : Return Statement
return ans;
Returns the final count of weak characters.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting step, which takes O(n log n) time.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required for sorting the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus