1366. Rank Teams by Votes

Solution1:

use map + list sort + string compare

T: O(n * mlogn), m is 26, n is votes counts

1.	Initialization: O(1)
2.	Building the rank map: O(n * m)
3.	Sorting the rank lists: O(m * nlogn)
4.	Sorting the list of characters: O(mlogm * n)
5.	Building the result string: O(m)

class Solution {
    public String rankTeams(String[] votes) {
        int voteCounts = votes.length;
        if (voteCounts == 1) {
            return votes[0];
        }

        Map<Character, List<Integer>> rank = new HashMap<>();
        for (String vote : votes) {
            for (int i = 0; i < vote.length(); i++) {
                char c = vote.charAt(i);
                rank.computeIfAbsent(c, k -> new ArrayList<>()).add((i));
            }
        }
        // here we want string to sorted list for the future sort
        //map key value
        // ex: A 11111
        //.    B 22333
        //.    C 22233
        List<Character> list = new ArrayList<>(rank.keySet());
        for (char c : list) {
            List<Integer> sorted = rank.get(c);
            Collections.sort(sorted);
            rank.put(c, sorted);
        }
        // use string compare
        list.sort((a, b) -> {
            String rank1 = rank.get(a).toString();
            String rank2 = rank.get(b).toString();
            int result = rank1.compareTo(rank2);
            if (result == 0) { // If two or more teams are still tied after considering all positions
                return a - b; // we rank them alphabetically based on their team letter.
            }
            return result;
        });

        StringBuilder sb = new StringBuilder();
        for (char c : list) {
            sb.append(c);
        }
        return sb.toString();
    }
}

/***
ABC
ACB
ABC
ACB
ACB

A 11111
B 22333
C 22233
compare each position in String, and sort by smaller one

26 team * votes(10^3)

ACB

"WXYZ",
"XYZW"

W: 14
X: 12
Y: 23
Z: 34

XWYZ

XWYZ
 */

Solution2: using bucket sort (m is at most 26)

T: O(m*n + m^2logm)

1.	Initialization: O(1)
2.	Building the rank map: O(m * n)
3.	Sorting the list of characters: O(m^2logm)
4.	Building the result string: O(m)

class Solution {
    public String rankTeams(String[] votes) {
        int voteCounts = votes.length;
        if (voteCounts == 1) { // this is an edge case! be careful!
            return votes[0];
        }

        int n = votes[0].length();
        Map<Character, int[]> rank = new HashMap<>();
        for (String vote : votes) {
            for (int i = 0; i < vote.length(); i++) {
                char team = vote.charAt(i);
                rank.putIfAbsent(team, new int[n]);
                rank.get(team)[i]++;
            }
        }

        List<Character> list = new ArrayList<>(rank.keySet());

        list.sort((a, b) -> {
            for (int i = 0; i < n; i++) {
                if (rank.get(a)[i] != rank.get(b)[i]) { // because use bucket sort, so if not equal, we return has value first
                    return rank.get(b)[i] - rank.get(a)[i]; // so means larger one is higher (in bucket sort, the position is from i = 0 to n-1)
                }
            }
            return a - b; // other equal case, return lexic order
        });

        StringBuilder sb = new StringBuilder();
        for (char c : list) {
            sb.append(c);
        }
        return sb.toString();
    }
}

/***



ABC
ACB
ABC
ACB
ACB

A 11111
B 22333
C 22233
compare each position in String, and sort by smaller one

26 team * votes(10^3)

ACB

"WXYZ",
"XYZW"

W: 14
X: 12
Y: 23
Z: 34

XWYZ

XWYZ
 */