forked from larissalages/code_problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1366.cpp
More file actions
31 lines (28 loc) · 1.02 KB
/
1366.cpp
File metadata and controls
31 lines (28 loc) · 1.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
string rankTeams(vector<string>& votes) {
//rank matrix
int i,j,n= votes.size(),k= votes[0].size();
vector<vector<int>> rank(26, vector<int>(k,0));
for (i=0;i< n;i++){
for (j=0;j<k;j++){
rank[votes[i][j]-'A'][j]++;
}
}
string res= votes[0];
sort(res.begin(),res.end(),[&rank](char &a, char &b){
int i=0;//index for both the rows of that 2 teams
int n= rank[a-'A'].size();
while (i<n && rank[a-'A'][i]==rank[b-'A'][i]){
i++;//lkeep on going till there is a mismatch of votes
}
if (i==n)
return a<b;//if everything is equal, arrange them alphabetically
return rank[a-'A'][i]>rank[b-'A'][i];
});
return res;
}
};
//==========================================================
//Time complexity of the algorithm asymptotically: O(n(k+log(n)))
//Space complexity: O(n*k)