Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Implementation
3.2.
Analysis of Complexity
4.
Approach 2
4.1.
Implementation
4.2.
Analysis of Complexity
5.
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?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Online Election

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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();  
	}

}

 

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];
	}
}

 

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).

Read More - Time Complexity of Sorting Algorithms

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.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Keep Coding!!!

 

Previous article
Length Of All Prefixes That Are Also The Suffixes Of The Given String
Next article
Longest Substring Without Repeating Characters
Live masterclass