CODEWITHSUNDEEP
data-structures
Drae
Drae

Reputation: 61

Most time efficient data structure for storing results of a two player game

Given two players where one is the winner, and one is the loser, what would be the most efficient way to store this data given that I need to

I was considering using a Hash Map of key Player, and value a list of losers, but this doesn't seem efficient when listing all of the players a player has lost to, as the time complexity is n^2

Upvotes: 2

Views: 131

Answers (1)

Anand Undavia
Anand Undavia

Reputation: 3543

While the HashMap with the key as a Player and value as either list of losers or { opponent, outcome } would be the easiest solution to implement, I would say it is not the most space efficient solution.

For each user, you will have to maintain a HashMap and that map would have duplicate entries. For example, if a player A has played with B and won, HashMap for A would have an entry of { B, "WON" } and player B will have an entry of { A, "LOST" } which is not required since we can imply that if player A has won, player B must have lost.

I would suggest using a Graph data structure to tackle the problem. A graph G = (V, E) would have V as a set of users and E as a set of Edges between users with one more property of which player won.

Here is a visual representation to get the better idea:

players as graph nodes

With this implementation, you can avoid the duplication which will be there in case of HashMap

The queries:

1. Check if a given player (X) has beaten another given player (Y)
> Perform only one level of DFS from X. Check whether the current player is Y. If the player is Y, check edge value. If the edge value is X, X has won otherwise Y has won. If the Y is not in the edge list, player X has never played with Y
Time complexity: O(E) where E is the list of Edges incident on node X.

2. List all of the players a given player (X) has beaten
> Perform one level DFS from X. Check edge value. If the edge value is X, X has won and thus, add Node at the other end of Edge to the list.
Time complexity: O(E) where E is the list of Edges incident on node X.


3. List all of the players a given player (X) has lost to
> Same as 2.


4. List all of the players a given player has played with
> Same as 2.


5. List all of the game results
> Perform a complete DFS.
Time complexity: O(E) where E is the list of Edges.

Upvotes: 1

Related Questions