Leetcode-1996 The number of weak characters in the game

Question

problem: You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

my solution:

class Solution {
public:
    
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int count =0;
        for(int i=0; i<properties.size(); i++){
            for(int j=0; j<properties.size(); j++){
                if((properties[j][0]>properties[i][0])&& (properties[j][1]>properties[i][1])){
                    count++;
                }
            }
        }
        return count;
    }
};

this is my solution. I don't know why this doesn't work. I basically compared from everyone in O(n^2) way and increment count if found such case.

Testcase: [[7,7],[1,2],[9,7],[7,3],[3,10],[9,8],[8,10],[4,3],[1,5],[1,5]]

My Output: 26 Expected: 6

C++ should be learnt using a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead of by solving random online puzzles. Also see [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jason, Sep 09 '22 at 14:25
The description says "2D" but then only uses a single index, meaning it's 1D. Each element is just a pair. — sweenish, Sep 09 '22 at 14:41
Please don't spam tags. This question has nothing to do with digital signature algorithm (DSA). — Evg, Sep 10 '22 at 16:25

score 2 · Answer 1 · answered Sep 09 '22 at 14:30

The problem is that your algorithm is counting all the pairs where one is "weaker" than the other, but that is not what is asked. You should count all the entries (not pairs) that are weaker than at least one other. Don't include in the count how many times you found that the same item turned out to be weaker. Just count the fact that it is weaker than some other entry.

score 0 · Answer 2 · answered Sep 09 '22 at 15:40

as it is already mentioned - your problem is that you're counting not the number of weak characters, but how many characters are stronger, i.e. you're increasing variable count multiple times per weak character, the simplest fix is to stop evaluation as soon as first stronger one is found:

class Solution {
public:
    
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int count =0;
        for(int i=0; i<properties.size(); i++){
            for(int j=0; j<properties.size(); j++){
                if ((properties[j][0] > properties[i][0]) && (properties[j][1] > properties[i][1])) {
                    count++;
                    break; // <-- HERE we need to stop
                }
            }
        }
        return count;
    }
};

this code should pass all tests, but it will fail because of timeout

to actually solve the problem - you need to change your approach to the problem, I'm not going to post fully working solution, but some tips:

what if you sort input array? so you will know that all characters past current item are >= in terms of attack power. how can you decrease number of comparisons then?
what if beside current attack/defense you will also know maximal defense power which can be found after current item?

Leetcode-1996 The number of weak characters in the game

2 Answers2