Find the Winner

Easy
0/40
Average time to solve is 10m
profile
Contributed by
40 upvotes
Asked in companies
AdobeExpedia Group

Problem statement

You have been given an array/list of “VOTES” which contains the name of the candidates where each entry represents the name of the candidate who got the vote.

You are supposed to find the name of the candidate who received the maximum number of votes. If there is a tie, then print the lexicographically smaller name.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer ‘N’ denoting the total number of votes cast.

Each of the next ‘N’ lines contains the name of the candidate who received the vote.
Output Format : 
For each test case, print the name of the candidate who received the maximum number of votes.

Print the output of each test case in a separate line.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 50
1 <= ‘N’ <= 10^3
1 <= |NAME| <= 20

Where ‘N’ is the number of votes cast and |NAME| denotes the length of the candidate’s name. 

Time Limit: 1 sec
Sample Input 1 :
2
4
John
Tim
Marry
John
2
Rahul
Ankur
Sample output 1 :
John
Ankur
Explanation For Sample intput 1 :
For the first test case, “John” has received the maximum number of votes (2 votes).

For the second test case, both “Rahul” and “Ankur” has received one vote each since “Ankur” is lexicographically smaller than “Rahul”, print “Ankur”.
Sample Input 2 :
2
1
Arya
2
Atul
Atul
Sample output 2 :
Arya
Atul
Explanation For Sample intput 2 :
For the first test case, “Arya” is the only candidate in the election who has received the maximum number of votes.  

For the second test case, “Atul” has received all the votes.
Hint

Can you think of counting the votes of each candidate?

Approaches (2)
Brute Force

The basic idea of this approach is to iterate through each candidate and count the number of votes he/she has received. We will keep track of the candidate with maximum votes. 

  

Here is the algorithm : 

  

  1. Create a variable “WINNER” which stores the name of the winning candidate and also create a variable “MAXVOTE” which stores the count of the vote the winning candidate has received.
  2. Iterate through the given array/list of votes using a variable ‘I’.
    • Create a nested loop to count the number of votes the candidate has received.
    • Update the “WINNER” and “MAXVOTE” if the current candidate has received more votes than the “MAXVOTE”. Also, in case “MAXVOTE” is equal to the votes received by the current candidate, update the “WINNER” as the lexicographically smaller name.
Time Complexity

O(N*(N+W)), Where ‘N’ is the length of the given array/list of votes. And ‘W’ is the maximum length of the candidate name.

 

Since we running a nested loop where each loop runs for ‘N’ times and then comparing the names of the candidate at each iteration, so the overall time complexity will be O(N*(N+W)).

Space Complexity

O(W), Where ‘W’ is the maximum length of the candidate name.

 

Since we are using extra space to store the name of the winning candidate, so the overall space complexity will be O(W).

Code Solution
(100% EXP penalty)
Find the Winner
Full screen
Console