Given an array of pairs arr[][] of the form {X, Y} such that each arr[i] represents the time X at which the candidate with candidate ID Y was voted and an array of queries query[] consisting of M positive integers, the task for each query Q[i] is to find the winning candidate ID at that time Q[i] of voting.
Note: In case, there are 2 candidates with the same number of votes K at a given time, then print the candidate who got those votes first.
Examples:
Input: arr[] = {{1, 2}, {2, 2}, {4, 1}, {5, 5}, {7, 1}, {11, 1}}, query[] = {2, 8, 12}
Output: 2 2 1
Explanation:
For query[0] = 2, at time 2, the candidate with candidateID = 2 has got the maximum votes.
For query[1] = 8, at time 8, the candidates with candidateID’s = 2 and 1 have got the maximum votes i.e, 2 but since candidate with ID 2 got those before so the answer is 2.
For query[2] = 12, at time 12, the candidate with candidateID = 1 has got the maximum votes i.e, 3.Input: arr[] = {{1, 1}}, query[] = { 1 }
Output: 1
Approach: The given problem can be solved by precomputing the winner at each coming time interval in the array arr[] and store it in another array, say Ans[] in the form of {timeInterval, winnerCandidateID} and then for each query query[i] perform the Binary Search on the array Ans[] to get the winning Candidate at time query[i]. Follow the steps below to solve the problem:
- Initialize a vector, say Ans[] that stores the winner at each incoming time interval arr[i].first.
- Initialize an unordered map, say Map[] that stores the frequency of the candidate’s ID at each incoming time interval.
- Initialize a pair, say previous[] that keeps the track of the winning candidate.
- Push the first pair in the vector Ans[] and mark that as the previous.
- Iterate over the range [1, N – 1] using the variable i and perform the following steps:
- Increment the frequency of the current candidate arr[i].second by 1 in the map Map.
- If the current candidate wins till now, then update the pair previous.
- Insert the previous in the vector Ans[].
- Iterate over the range [0, M) using the variable i and perform the following steps:
- For each query, perform a binary search on the vector of pairs Ans[] to find the winning candidate.
- Perform the binary search on the time i.e, the first value of the vector of pairs Ans[] and find the largest value which is less than equal to query[I], and print the corresponding candidateID.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// Function to perform binary search// to find the candidate with most votes// for a particular timeint binarySearch(vector<pair<int, int> >& Ans, int low, int high, int value){ // Base Cases if (value <= Ans[low].first) return Ans[low].second; if (value >= Ans[high].first) return Ans[high].second; int winningCandidate; while (low <= high) { // Find the mid int mid = low + (high - low) / 2; // If the value at mid is the // result if (Ans[mid].first == value) { winningCandidate = Ans[mid].second; break; } // Update the ranges else if (Ans[mid].first < value) { winningCandidate = Ans[mid].second; low = mid + 1; } else { high = mid - 1; } } return winningCandidate;}// Function to find the winner for each queryvoid findWinner(pair<int, int> arr[], int N, int query[], int M){ // Map to store the frequency unordered_map<int, int> Map; // Stores the winning candidate till // a particular time vector<pair<int, int> > Ans; // Starting Reference pair<int, int> previous = { arr[0].first, arr[0].second }; Ans.push_back(previous); Map[arr[0].second]++; // Iterate over the range for (int i = 1; i < N; i++) { // Increase the frequency Map[arr[i].second]++; // Update the reference if another // candidate gets more votes than // the one considered if (Map[arr[i].second] > Map[previous.second]) { previous.second = arr[i].second; } previous.first = arr[i].first; // Push into the vector Ans.push_back(previous); } // Iterate over the range for (int i = 0; i < M; i++) { cout << binarySearch(Ans, 0, N - 1, query[i]) << ' '; }}// Driver Codeint main(){ pair<int, int> arr[] = { { 1, 2 }, { 2, 2 }, { 4, 1 }, { 5, 5 }, { 7, 1 }, { 11, 1 } }; int query[] = { 2, 8, 12 }; int N = 6; int M = 3; findWinner(arr, N, query, M); return 0;} |
Java
import java.util.*;public class Main {static class Pair<T, U> { private T key; private U value; public Pair(T key, U value) { this.key = key; this.value = value; } public T getKey() { return key; } public U getValue() { return value; }} public static int binarySearch(List<Pair<Integer, Integer>> Ans, int low, int high, int value) { // Base Cases if (value <= Ans.get(low).getKey()) { return Ans.get(low).getValue(); } if (value >= Ans.get(high).getKey()) { return Ans.get(high).getValue(); } int winningCandidate = 0; while (low <= high) { // Find the mid int mid = low + (high - low) / 2; // If the value at mid is the // result if (Ans.get(mid).getKey() == value) { winningCandidate = Ans.get(mid).getValue(); break; } // Update the ranges else if (Ans.get(mid).getKey() < value) { winningCandidate = Ans.get(mid).getValue(); low = mid + 1; } else { high = mid - 1; } } return winningCandidate; } public static void findWinner(Pair<Integer, Integer>[] arr, int N, int[] query, int M) { // Map to store the frequency Map<Integer, Integer> Map = new HashMap<>(); // Stores the winning candidate till // a particular time List<Pair<Integer, Integer>> Ans = new ArrayList<>(); // Starting Reference Pair<Integer, Integer> previous = new Pair<>(arr[0].getKey(), arr[0].getValue()); Ans.add(previous); Map.put(arr[0].getValue(), 1); // Iterate over the range for (int i = 1; i < N; i++) { // Increase the frequency Map.put(arr[i].getValue(), Map.getOrDefault(arr[i].getValue(), 0) + 1); // Update the reference if another // candidate gets more votes than // the one considered if (Map.get(arr[i].getValue()) > Map.get(previous.getValue())) { previous = new Pair<>(arr[i].getKey(), arr[i].getValue()); } // Push into the list Ans.add(previous); } // Iterate over the range for (int i = 0; i < M; i++) { System.out.print(binarySearch(Ans, 0, N - 1, query[i]) + " "); }}public static void main(String[] args) { Pair<Integer, Integer>[] arr = new Pair[6]; arr[0] = new Pair<>(1, 2); arr[1] = new Pair<>(2, 2); arr[2] = new Pair<>(4, 1); arr[3] = new Pair<>(5, 5); arr[4] = new Pair<>(7, 1); arr[5] = new Pair<>(11, 1); int[] query = { 2, 8, 12 }; int N = 6; int M = 3; findWinner(arr, N, query, M);}} |
Python3
# Python 3 program for the above approachfrom collections import defaultdict# Function to perform binary search# to find the candidate with most votes# for a particular timedef binarySearch(Ans, low, high, value): # Base Cases if (value <= Ans[low][0]): return Ans[low][1] if (value >= Ans[high][0]): return Ans[high][1] while (low <= high): # Find the mid mid = low + (high - low) // 2 # If the value at mid is the # result if (Ans[mid][0] == value): winningCandidate = Ans[mid][1] break # Update the ranges elif (Ans[mid][0] < value): winningCandidate = Ans[mid][1] low = mid + 1 else: high = mid - 1 return winningCandidate# Function to find the winner for each querydef findWinner(arr, N, query, M): # Map to store the frequency Map = defaultdict(int) # Stores the winning candidate till # a particular time Ans = [] # Starting Reference previous = [arr[0][0], arr[0][1]] Ans.append([previous[0], previous[1]]) Map[arr[0][1]] += 1 # Iterate over the range for i in range(1, N): # Increase the frequency Map[arr[i][1]] += 1 # Update the reference if another # candidate gets more votes than # the one considered if (Map[arr[i][1]] > Map[previous[1]]): previous[1] = arr[i][1] previous[0] = arr[i][0] # Push into the vector Ans.append([previous[0], previous[1]]) # Iterate over the range for i in range(M): print(binarySearch( Ans, 0, N - 1, query[i]), end=' ')# Driver Codeif __name__ == "__main__": arr = [[1, 2], [2, 2], [4, 1], [5, 5], [7, 1], [11, 1]] query = [2, 8, 12] N = 6 M = 3 findWinner(arr, N, query, M) # This code is contributed by ukasp. |
C#
using System;using System.Collections.Generic;// Generic pair class definitionpublic class Pair<T, U> { // Class members private T key; private U value; // Constructor public Pair(T key, U value) { this.key = key; this.value = value; } // Getter methods public T Key { get { return key; } } public U Value { get { return value; } }}class GFG { // This function performs binary search operation public static int BinarySearch(List<Pair<int, int> > Ans, int low, int high, int value) { // Base Cases if (value <= Ans[low].Key) { return Ans[low].Value; } if (value >= Ans[high].Key) { return Ans[high].Value; } int winningCandidate = 0; while (low <= high) { // Find the mid int mid = low + (high - low) / 2; // If the value at mid is the result if (Ans[mid].Key == value) { winningCandidate = Ans[mid].Value; break; } // Update the ranges else if (Ans[mid].Key < value) { winningCandidate = Ans[mid].Value; low = mid + 1; } else { high = mid - 1; } } return winningCandidate; } public static void FindWinner(Pair<int, int>[] arr, int N, int[] query, int M) { // Dictionary to store the frequency Dictionary<int, int> Map = new Dictionary<int, int>(); // List to store the winning candidate till a // particular time List<Pair<int, int> > Ans = new List<Pair<int, int> >(); // Starting Reference Pair<int, int> previous = new Pair<int, int>(arr[0].Key, arr[0].Value); Ans.Add(previous); Map[arr[0].Value] = 1; // Iterate over the range for (int i = 1; i < N; i++) { // Increase the frequency if (Map.ContainsKey(arr[i].Value)) { Map[arr[i].Value]++; } else { Map[arr[i].Value] = 1; } // Update the reference if another candidate // gets more votes than the one considered if (Map[arr[i].Value] > Map[previous.Value]) { previous = new Pair<int, int>(arr[i].Key, arr[i].Value); } // Add to the list Ans.Add(previous); } // Iterate over the range for (int i = 0; i < M; i++) { Console.Write( BinarySearch(Ans, 0, N - 1, query[i]) + " "); } } // Driver code public static void Main(string[] args) { Pair<int, int>[] arr = { new Pair<int, int>(1, 2), new Pair<int, int>(2, 2), new Pair<int, int>(4, 1), new Pair<int, int>(5, 5), new Pair<int, int>(7, 1), new Pair<int, int>(11, 1) }; int[] query = { 2, 8, 12 }; int N = 6; int M = 3; FindWinner(arr, N, query, M); }}// This code is contributed by phasing17. |
Javascript
// JS program to implement the approach// Function to perform binary search// to find the candidate with most votes// for a particular timefunction binarySearch(Ans, low, high, value) { // Base Cases if (value <= Ans[low][0]) { return Ans[low][1]; } if (value >= Ans[high][0]) { return Ans[high][1]; } while (low <= high) { // Find the mid let mid = low + Math.floor((high - low) / 2); // If the value at mid is the result if (Ans[mid][0] === value) { return Ans[mid][1]; } // Update the ranges if (Ans[mid][0] < value) { low = mid + 1; winningCandidate = Ans[mid][1]; } else { high = mid - 1; } } return winningCandidate;}// Function to find the winner for each queryfunction findWinner(arr, N, query, M) { // Map to store the frequency let Map = {}; // Stores the winning candidate till // a particular time let Ans = []; // Starting Reference let previous = [arr[0][0], arr[0][1]]; Ans.push([previous[0], previous[1]]); if (!Map[arr[0][1]]) { Map[arr[0][1]] = 0; } Map[arr[0][1]] += 1; // Iterate over the range for (let i = 1; i < N; i++) { // Increase the frequency if (!Map[arr[i][1]]) { Map[arr[i][1]] = 0; } Map[arr[i][1]] += 1; // Update the reference if another // candidate gets more votes than // the one considered if (Map[arr[i][1]] > Map[previous[1]]) { previous[1] = arr[i][1]; } previous[0] = arr[i][0]; // Push into the vector Ans.push([previous[0], previous[1]]); } // Iterate over the range for (let i = 0; i < M; i++) { process.stdout.write(binarySearch(Ans, 0, N - 1, query[i]) + " "); }}// Driver Codeconst arr = [[1, 2], [2, 2], [4, 1], [5, 5], [7, 1], [11, 1]];const query = [2, 8, 12];const N = 6;const M = 3;// Function callfindWinner(arr, N, query, M);// This code is contributed by phasing17 |
Output:
2 2 1
Time Complexity: O(max(N, M*log(N)))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
