Find Players With Zero or One Losses LeetCode

Problem Link:

https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/

Solution Link:

class Solution {

    public List<List<Integer>> findWinners(int[][] matches) {

        TreeMap<Integer,Integer>map1=new TreeMap<Integer,Integer>();

        TreeMap<Integer,Integer>map2=new TreeMap<Integer,Integer>();

        for(int i=0;i<matches.length;i++){

            int a=matches[i][0];

           

            if(map1.containsKey(a)){

                map1.put(a,map1.get(a)+1);

            }

            else{

                map1.put(a,1);

            }

        }

        for(int i=0;i<matches.length;i++){

            int b=matches[i][1];

           

            if(map2.containsKey(b)){

                map2.put(b,map2.get(b)+1);

            }

            else{

                map2.put(b,1);

            }

        }

        ArrayList<Integer>aa1=new ArrayList<Integer>();

        ArrayList<Integer>aa2=new ArrayList<Integer>();

        for(int a1:map1.keySet()){

            if(!map2.containsKey(a1)){

                aa1.add(a1);

            }

        }

        for(int b1:map2.keySet()){

            if(map2.get(b1)==1){

                aa2.add(b1);

            }

        }

        List<List<Integer>>list=new ArrayList<List<Integer>>();

        list.add(aa1);

        list.add(aa2);

        return list;

    }

}

Approach:

Here we will make 2 maps.

The first map will be of all the winners and the second will be of all the losers.

Winner in game will be: matches[i][0]

Loser in-game will be: matches[i][1]

So for the first map key will be the winner and the value will be the count of losers by the same player.

While for the second map the winner will be the loser ie matches[i][1] and the value will be the count of the matches that the player has lost.

So for finding out the player who has won all the matches:

1. we will traverse the first map so we get to know about all the winners and then we will see on the second map whether that player is present or not. 

If it is present then it means that the same player has lost, so it won't be part of the ArrayList 1.

So for that, we come up with the answer that we will traverse the first map, and every time we will see in the second map whether that key is present or not. If that key is present we will then add it to ArrayList 1 and if it is not then it means that the player is lost in any game.

For finding the player who has lost exactly one match:

For finding out the loser in the game we have the second map designed, in which the key is the loser player and the value is the count of matches in which that player has lost.

So for finding out exactly one match lost by a player we will simply travel to the second map and find out the key where the value will be 1.

So for that, we come up with the answer that we will traverse the second map, and every time when we see the key with value==1 then we will add on that key in ArrayList 2 and if its value is not 1 then we will not add it into the ArrayList 2.

So at last, we will return the final list in which the first element will be ArrayList 1 and the second will be ArrayList 2.

return list.

Time Complexity: O(N)[Total two times traversal of match array. In the worst case, the map size will be of all unique entries but that too will not be more than O(N). Moreover contains a Key method search in O(1) time complexity.]

Space Complexity: O(N)[Two-dimensional array is used.]

Auxiliary Space: O(N)[Two additional maps are used and in the worst case their size can be the size of the array.]

LeetCode Time:520 ms faster than 12.46%

LeetCode Memory:134.9 Mb less than 79.62%

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😀"