I started working on this problem a while ago, and ran into the issue of keeping track of unique pairs of cows that are valid for two-cow teams winning.
What’s the most efficient way to keep track of the pairs of cows? I’m currently using Java.
I’ve run into this problem in a few other problems, and have done some pretty inconvenient solutions (2d arrays), so I’m just wondering if there’s a better way to do it.
In this problem, the bounds are pretty small, so I don’t think an efficient solution is necessary. What other problems are you having trouble with optimization?
Perhaps a TreeSet
could suffice.
Since the bounds are low, the question is not really about efficiency but what’s the easiest solution.
First to make sure you count unique pairs: for each pair (a, b) if b>a swap a and b so that a < b.
Some options in Java are:
-
boolean[26][26]
visited array where you convert each character to an int, and another frequency counter
-
Hash/TreeSet<Integer>
where you combine two characters into an int with binary e.g. (a<<8) + b
-
Map<Char, Set<Char> >
visited
-
Set<Pair<Char, Char> >
where you make your own Pair class
-
Set<String>
where you concatenate two characters into a String
I would go with either option 1 or 2 above, the other solutions could be useful for other problems but are overkill here. 2D arrays are not that bad to work with.