Problem Explanation

In this problem, we are given the list of votes and the respective times at which each vote was cast. Each voter is represented by a unique integer and the time of their vote is also a unique integer. We have to implement a function TopVotedCandidate.q(int t) which will receive a unique time "t" as input and return the candidate who was leading at time "t". In case of a tie (same number of votes), the candidate who received the most recent vote will be considered as the leader.

Let us consider an example from description,

At time t=3 [votes are 0]. The leader is 0 because there is only one vote. At time t=12 [votes are 0,1,1]. The leader is 1 because he has more votes than 0. At time t=25 [votes are 0,1,1,0,0,1]. The leader is still 1 as he is the most recent to reach 3 votes. And then we continue for 3 more queries at time 15, 24, and 8.

Solution

We will use a hashmap and a binary search for this problem. The logic behind our approach is that we use the hashmap count to keep track of the number of votes each candidate has. We use lead to keep track of the current leading candidate.

We iterate through the list of votes and update the count of the candidate and check if the vote count of the current candidate is equal to or more than the vote count of the current leader, if yes then update the lead with the current candidate number. For every time at vote i we keep track of the leading candidate in a map timeToLead.

When the function Q(int t) is called, we use binary search to find the largest time which is less or equal to t and return the leading candidate at that time using timeToLead.

This approach gives the correct output as it maintains a map of leading candidate at every vote time, and binary search provides an efficient way to search for leading candidate at a given time in logarithmic time complexity.

Python Solution

1
2python
3class TopVotedCandidate:
4
5    def __init__(self, persons, times):
6        self.leader = []
7        self.time = times
8        votes = {}
9        leader = persons[0]
10
11        for i in range(len(persons)):
12            if persons[i] in votes:
13                votes[persons[i]] += 1
14            else:
15                votes[persons[i]] = 1
16            
17            if votes[persons[i]] >= votes[leader]:
18                leader = persons[i]
19            
20            self.leader.append(leader)
21                
22    def q(self, t):
23        low, high = 0, len(self.time) - 1
24
25        while low < high:
26            mid = (low + high + 1) // 2
27            if self.time[mid] <= t:
28                low = mid
29            else:
30                high = mid - 1
31                
32        return self.leader[low]

Java Solution

1
2java
3class TopVotedCandidate {
4    private int[] times;
5    private int[] leaders;
6
7    public TopVotedCandidate(int[] persons, int[] times) {
8        this.times = times;
9        this.leaders = new int[times.length];
10
11        int leader = persons[0];
12        int[] votes = new int[persons.length];
13        votes[leader] = 1;
14
15        for (int i = 1; i < times.length; i++) {
16            votes[persons[i]]++;
17
18            if (votes[persons[i]] >= votes[leader]) {
19                leader = persons[i];
20            }
21
22            leaders[i] = leader;
23        }
24    }
25
26    public int q(int t) {
27        int start = 0;
28        int end = times.length - 1;
29
30        while (start < end) {
31            int mid = (start + end + 1) / 2;
32            if (times[mid] <= t) {
33                start = mid;
34            } else {
35                end = mid - 1;
36            }
37        }
38
39        return leaders[start];
40    }
41}

JavaScript Solution

1
2javascript
3class TopVotedCandidate {
4    constructor(persons, times) {
5        this.time = times;
6        this.leader = [];
7        
8        let votes = {};
9        let leader = persons[0];
10        
11        for (let i = 0; i < persons.length; i++) {
12            if (persons[i] in votes) {
13                votes[persons[i]] += 1;
14            } else {
15                votes[persons[i]] = 1;
16            }
17            
18            if (votes[persons[i]] >= votes[leader]) {
19                leader = persons[i];
20            }
21            
22            this.leader[i] = leader;
23        }
24    }
25    
26    q(t) {
27        let low = 0;
28        let high = this.time.length - 1;
29        
30        while (low < high) {
31            let mid = Math.floor((low + high + 1) / 2);
32            if (this.time[mid] <= t) {
33                low = mid;
34            } else {
35                high = mid - 1;
36            }
37        }
38        
39        return this.leader[low];
40    }
41}

C++ Solution

1
2cpp
3class TopVotedCandidate {
4 public:
5  TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
6    unordered_map<int, int> count;  
7    int lead = -1;
8
9    for (int i = 0; i < persons.size(); ++i) {
10      if (++count[persons[i]] >= count[lead])
11        lead = persons[i];
12      timeToLead[times[i]] = lead;
13    }
14  }
15
16  int q(int t) {
17    auto it = --upper_bound(begin(times), end(times), t);
18    return timeToLead[*it];
19  }
20
21 private:
22  const vector<int> times;
23  unordered_map<int, int> timeToLead;
24};

C# Solution

1
2csharp
3public class TopVotedCandidate {
4    private Dictionary<int,int> dict;
5    private List<int> times;
6    
7    public TopVotedCandidate(int[] persons, int[] times) {
8        this.times = new List<int>(times);
9        this.dict = new Dictionary<int,int>();
10        int leader = -1;
11        int cnt = 0;
12        Dictionary<int, int> counter = new Dictionary<int, int>();
13        for(int i = 0; i<persons.Length;i++){
14            if(!counter.ContainsKey(persons[i])){
15                counter[persons[i]] = 0;
16            }
17            counter[persons[i]]++;
18            if(counter[persons[i]]>=cnt){
19                leader = persons[i];
20                cnt = counter[persons[i]];
21            }
22            dict.Add(times[i], leader);
23        }
24    }
25    
26    public int Q(int t) {
27        int index = BinarySearch(times, t);
28        return dict[times[index]];
29    }
30    
31    private int BinarySearch(List<int> times, int t){
32        int low = 0, high = times.Count-1;
33        while(low+1 <high){
34            int mid = low + (high - low) / 2;
35            if(times[mid] <= t){
36                low = mid;
37            }
38            else{
39                high = mid;
40            }
41        }
42        if(times[high] <= t)
43            return high;
44        return low;
45    }
46}

In all these above solutions, initially in constructor we kept track of leader at the time of each vote in the respective data structures of each language. Later we used binary search to find the leader at time "t". This approach is efficient and solves the problem correctly.# Swift Solution

1
2Swift
3class TopVotedCandidate {
4    var leader: [Int]
5    var time: [Int]
6
7    init(_ persons: [Int], _ times: [Int]) {
8        self.leader = []
9        self.time = times
10        var votes = [Int: Int]()
11        var leader:Int = persons[0]
12
13        for i in 0..<persons.count {
14            votes[persons[i], default: 0] += 1
15            if votes[persons[i]]! >= votes[leader]! {
16                leader = persons[i]
17            }
18            self.leader.append(leader)
19        }
20    }
21    
22    func q(_ t: Int) -> Int {
23        var low = 0
24        var high = time.count - 1
25
26        while low < high {
27            let mid = (low + high + 1) / 2
28            if time[mid] <= t {
29                low = mid
30            } else {
31                high = mid - 1
32            }
33        }
34        return leader[low]
35    }
36}

PHP Solution

1
2php
3class TopVotedCandidate {
4    private $persons = [];
5    private $times = [];
6    
7    function __construct($persons, $times) {
8        $this->persons = $persons;
9        $this->times = $times;
10        
11        $votes = [];
12        $leader = $persons[0];
13
14        for ($i = 0; $i < count($persons); $i++) {
15            if (isset($votes[$persons[$i]])) {
16                $votes[$persons[$i]]++;
17            } else {
18                $votes[$persons[$i]] = 1;
19            }
20
21            if ($votes[$persons[$i]] >= $votes[$leader]) {
22                $leader = $persons[$i];
23            }
24
25            $this->persons[$i] = $leader;
26        }
27    }
28
29    function q($time) {
30        $left = 0;
31        $right = count($this->times) - 1;
32        
33        while ($left < $right) {
34            $mid = floor(($left + $right + 1) / 2);
35            if ($this->times[$mid] <= $time) {
36                $left = $mid;
37            } else {
38                $right = $mid - 1;
39            }
40        }
41
42        return $this->persons[$left];
43    }
44}

In these solutions, Swift and PHP, we are solving the problem in a similar manner as we have done before. In these solutions, we initially keep track of the leader at the time of each vote in the respective data structures of each language. Then we use binary search to find the leader at a specified time 't'. These solutions are effective in resolving the problem as expected.