Picking lexicographically smaller

Viewed 330

Question : https://www.geeksforgeeks.org/find-winner-election-votes-represented-candidate-names/

Given an array of names of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidates received Max vote. If there is tie, print lexicographically smaller name.

// C++++ program to find winner in an election. 
#include "bits/stdc++.h" 
using namespace std; 

/* We have four Candidates with name as 'John', 
'Johnny', 'jamie', 'jackie'. 
The votes in String array are as per the 
votes casted. Print the name of candidates 
received Max vote. */
void findWinner(vector<string>& votes) 
{ 
    
    // Insert all votes in a hashmap 
    map<string,int> mapObj ; 
    for (auto& str : votes) 
    { 
        mapObj[str]++; 
    } 

    // Traverse through map to find the candidate 
    // with maximum votes. 
    int maxValueInMap = 0; 
    string winner; 
    for (auto& entry : mapObj) 
    { 
        string key = entry.first; 
        int val = entry.second; 
        if (val > maxValueInMap) 
        { 
            maxValueInMap = val; 
            winner = key; 
        } 

        // If there is a tie, pick lexicographically 
        // smaller. 
        else if (val == maxValueInMap && 
            winner>key) 
            winner = key; 
    } 
    cout << winner << endl; 
} 

// Driver code 
int main() 
{ 
vector<string> votes = { "john", "johnny", "jackie", 
                    "johnny", "john", "jackie", 
                    "jamie", "jamie", "john", 
                    "johnny", "jamie", "johnny", 
                    "john" }; 

findWinner(votes); 
return 0; 
} 

How is this picking the lexicographically smaller key? I couldn't understand this part of the code clearly

else if (val == maxValueInMap && 
            winner>key) 
            winner = key; 

Can someone help me with this? Thanks!

1 Answers

winner>key is a lexicographical comparison. It's true if key is lexicographically less than winner (I do think it would have been less confusing to write it the other way around key<winner).

So the code is saying that if the score just found is equal to the best score found so far and if the candidate just found is lexicographically less than the winning candidate so far, pick the new candidate. So that seems to be as required.

Related