Table of contents

Introduction

Problem Statement

Approach 1

3.1.

Implementation

3.2.

Analysis of Complexity

Approach 2

4.1.

Implementation

4.2.

Analysis of Complexity

Frequently Asked Questions

5.1.

What do you mean by TreeMap in Java?

5.2.

What are the time complexities for different approaches to finding the people leading in the election?

5.3.

What do you mean by the Binary Search algorithm?

Conclusion

Last Updated: Mar 27, 2024

Medium

Online Election

Q: What do you mean by TreeMap in Java?

Treemap is sorted according to the natural ordering of its keys. It is an unsynchronized class that stores unique values, and the main difference between HashMap and TreeMap is that HashMap is an unordered collection. At the same time, TreeMap is sorted in the ascending order of its keys.

Q: What are the time complexities for different approaches to finding the people leading in the election?

Time Complexity is O(nlogn +logn) if we use TreeMap. Time Complexity is O(n + logn) if you use HashMap.

Q: What do you mean by the Binary Search algorithm?

It is a searching algorithm used to search an element in a sorted array in O(logn) time.

Author Deleted User

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

This problem is based on one of the famous topics of Data Structures and Algorithms. I.e., HashTable and Binary Search. The hashtable class implements the hashtable, which maps keys to values. Hashtable contains unique values, and null values are not allowed. Java Hashtable class is synchronized.

Binary search is a searching technique used to search in the sorted elements in O(logn) time.

Online Election is a problem where we have to find the number of people leading in votes at a particular time.

We will see different approaches to solving this problem.

Let's move on to our problem statement.

Problem Statement

We are given two integer arrays persons and times. Elections are going on in the city where the ith vote is cast for the person[i] at times[i].

Now for each query at time t, find the leading candidate in the election at time t.

Note:

In the case of a tie, the most recent vote wins.

Two methods will be implemented one will be for initializing and the other for the query.

Let's understand this problem more clearly with the help of an example, as it is a little confusing.,

["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]

The first list is the query. Now we have a list of lists. The very first list is a list of persons voted and the second list is the time of voting.

[0,1,1, 0, 0, 1, 0]

[0,5,10,15,20,25,30]

This means at time t=0, a vote was cast for person 0, and at time t=5, one vote was cast for person 1, and so on.

Does the question say that we have to ask who the leading candidate is at t=11 or t=13 or t=2?.

I hope this clears the question as it did for me.

Now let's take t=11.

Now, t=11 is not on the list of times. It falls between t=10 and t=15.

Proposition: If it is not present in times, then the leading candidate at t will be the same candidate who has been leading at time t' where t' < t and t' is the largest element in times that satisfies the inequality.

Proof: Say t= 11. Now we know that 11 is not in time. The largest number smaller than 11 in times is 10. Till 10 person 1 is leading[0,1,1]. Person 1 will lead in 11 as well because the next voting occurs at t=15. Person 1 will keep leading at times 10,11,12,13,14 and may start trailing as the vote is cast at t=15.

So when given a time t, our job becomes first to find the time t'. As time is constantly increasing, we use the binary search here.

Approach 1

The first approach we will be discussing is TreeMap. TreeMap provides efficient means of storing key-value pairs in sorted order. You can check examples related to this over here.

Implementation

import java.util.TreeMap;

public class TopVotedCandidate {

// time and leading candidate
	private TreeMap<Integer, Integer> tm =  new TreeMap<>();

	public TopVotedCandidate(int[] persons,  int[] times) {

// count[i]: count of votes for persons[i].
		int[] count =  new int[persons.length];  

		for (int i =  0, max = -1; i < times.length; ++i) {
// at times[i], persons[i] got a vote.
			++count[persons[i]];  

// is persons[i] leading?
			if (max <= count[persons[i]]) {
				 

// update leading count.
				max = count[persons[i]];  

// update leading candidate.
				tm.put(times[i], persons[i]);  
			}
		}
	}
	public int q(int t) {
// fetch the corresponding information.
		return tm.floorEntry(t).getValue();  
	}

}

You can also try this code with Online Java Compiler

Run Code

Analysis of Complexity

Time Complexity: The time complexity for the constructor TopVotedCandidates is O(nlogn), and for the query is O(logn).

Space Complexity: The space complexity is O(n).

Approach 2

The following approach that will be discussed is the more efficient one than the previous approach. We will be using HashMap for the constructor TopVotedCandidates and Binary Search for the query.

Implementation

import java.util.HashMap;
import java.util.Map;

public class TopVotedCandidate {

// time and leading candidate
	private Map<Integer, Integer> map =  new HashMap<>();  
	private int[] times;
	private int[] count;
	public TopVotedCandidate(int[] persons,  int[] times) {

		this.times = times;
		// count[i]: count of votes for persons[i].
		count =  new int[persons.length +  1];  
		for (int i =  0, winner = -1; i < times.length; ++i) {

			// at times[i], persons[i] got a vote.
			++count[persons[i]];  

			// is persons[i] leading? update winner.
			if (map.isEmpty() || count[winner] <= count[persons[i]]) {
				 
				winner = persons[i];  
			} 
			// update time and winner.
			map.put(times[i], winner);
		}
	}

	public int q(int t) {

		int i =  0, j = times.length;

		while (i < j) {
			int mid = i + (j - i) /  2;

			if (times[mid] <= t) {
				i = mid +  1;
			}
			else {

				j = mid;
			}
		}
		return count[i -  1];
	}
}

You can also try this code with Online Java Compiler

Run Code

Analysis of Complexity

Time Complexity: The time complexity for the constructor is O(n) and for query is O(logn).

Space Complexity: The space complexity is O(n).

Frequently Asked Questions

What do you mean by TreeMap in Java?

Treemap is sorted according to the natural ordering of its keys. It is an unsynchronized class that stores unique values, and the main difference between HashMap and TreeMap is that HashMap is an unordered collection. At the same time, TreeMap is sorted in the ascending order of its keys.

What are the time complexities for different approaches to finding the people leading in the election?

Time Complexity is O(nlogn +logn) if we use TreeMap.

Time Complexity is O(n + logn) if you use HashMap.

What do you mean by the Binary Search algorithm?

It is a searching algorithm used to search an element in a sorted array in O(logn) time. You can check out more examples related to this over here.

Conclusion

In this article, we discussed the Online Election problem and how we can build an approach for it:

For this problem, we have used two methods. The first one is for initializing and the other for the query, which will assist us in identifying the leading people in the election.

The first approach we used is TreeMap and the second one is Binary Search, which helps find the highest number of votes awarded to which person at a particular time in the election.

You can use Coding Ninjas Studio to practice various DSA questions typically asked in interviews. It will help you in mastering efficient coding techniques.