Given an array arr[] of size N, and Q queries of the form {i, k} for which, the task is to print the most frequent element in the array after replacing arr[i] by k.
Example :
Input: arr[] = {2, 2, 2, 3, 3}, Query = {{0, 3}, {4, 2}, {0, 4}}
Output: 3 2 2
First query: Setting arr[0] = 3 modifies arr[] = {3, 2, 2, 3, 3}. So, 3 has max frequency.
Second query: Setting arr[4] = 2, modifies arr[] = {3, 2, 2, 3, 2}. So, 2 has max frequency.
Third query: Setting arr[0] = 4, modifies arr[] = {4, 2, 2, 3, 2}. So, 2 has max frequency
Input: arr[] = {1, 2, 3, 4, 3, 3} Query = {{0, 2}, {3, 2}, {2, 4}}
Output: 3 2 2
Naive Approach:
For every query, replace arr[i] by K, and traverse over the whole array and count the frequency of every array element and print the most frequent of them.
Time Complexity: O(N * Q)
Auxiliary Space: O(N)
Efficient Approach:
The above approach can be optimized by precomputing the frequencies of every array element and maintain frequency-array element pairings in a set to obtain the most frequent element in O(1). Follow the steps below to solve the problem:
- Initialize a map to store frequencies of all array elements, and a set of pairs to store frequency-element pairings. In the set, store the frequencies as negative. This ensures that the first pair stored at the beginning of the set, i.e. s.begin(), is the {-(maximum frequency), most frequent element} pairing.
- For every query, while removing the array element at ith index, do the following tasks:
- Find the frequency of arr[i] from the map, that is mp[arr[i]].
- Remove the pair {-mp[arr[i]], arr[i]} from the set.
- Update the set after decreasing the frequency of arr[i] by inserting {-(mp[arr[i] – 1), arr[i]} into the set.
- Decrease the frequency of arr[i] in the map.
- To insert K into the array for every query, do the following:
- Find the frequency of K from the map, that is mp[K].
- Remove the pair {-mp[K], K} from the set.
- Update the set after increasing the frequency of K by inserting {-(mp[K] + 1), K} into the set.
- Increase the frequency of K in the map.
- Finally for each query, extract the pair at the beginning of the set. The first element in the set denotes -(maximum frequency). Hence, the second element will be the most frequent element. Print the second element of the pair.
Below is the implementation of the above approach:
C++
// C++ program to find the most // frequent element after every // update query on the array #include <bits/stdc++.h> using namespace std; typedef long long int ll; // Function to print the most // frequent element of array // along with update query void mostFrequent(ll arr[], ll n, ll m, vector<vector<ll> > q) { ll i; // Stores element->frequencies // mappings map<ll, ll> mp; for (i = 0; i < n; i++) mp[arr[i]] += 1; // Stores frequencies->element // mappings set<pair<ll, ll> > s; // Store the frequencies in // negative for (auto it : mp) { s.insert(make_pair(-(it.second), it.first)); } for (i = 0; i < m; i++) { // Index to be modified ll j = q[i][0]; // Value to be inserted ll k = q[i][1]; // Store the frequency of // arr[j] and k auto it = mp.find(arr[j]); auto it2 = mp.find(k); // Remove mapping of arr[j] // with previous frequency s.erase(make_pair(-(it->second), it->first)); // Update mapping with new // frequency s.insert(make_pair(-((it->second) - 1), it->first)); // Update frequency of arr[j] // in the map mp[arr[j]]--; // Remove mapping of k // with previous frequency s.erase(make_pair(-(it2->second), it2->first)); // Update mapping of k // with previous frequency s.insert(make_pair(-((it2->second) + 1), it2->first)); // Update frequency of k mp[k]++; // Replace arr[j] by k arr[j] = k; // Display maximum frequent element cout << (*s.begin()).second << " " << endl; } } // Driver Code int main() { ll i, N, Q; N = 5; Q = 3; ll arr[] = { 2, 2, 2, 3, 3 }; vector<vector<ll> > query = { { 0, 3 }, { 4, 2 }, { 0, 4 } }; mostFrequent(arr, N, Q, query); } |
Java
// Java program to find the most // frequent element after every // update query on the array import java.util.*;import java.io.*;class GFG{ // Pair class represents// a pair of elementsstatic class Pair{ int first, second; Pair(int f,int s) { first = f; second = s; }}// Function to print the most // frequent element of array // along with update query static void mostFrequent(int arr[], int n, int m, ArrayList<Pair> q) { int i; // Stores element->frequencies // mappings HashMap<Integer, Integer> map = new HashMap<>(); HashMap<Integer, Pair> map1 = new HashMap<>(); for(i = 0; i < n; i++) { if(!map.containsKey(arr[i])) map.put(arr[i], 1); else map.put(arr[i], map.get(arr[i]) + 1); } // Stores frequencies->element // mappings TreeSet<Pair> set = new TreeSet<>( new Comparator<Pair>() { public int compare(Pair p1, Pair p2) { return p2.first - p1.first; } }); // Store the frequencies in // bigger to smaller for(Map.Entry<Integer, Integer> entry : map.entrySet()) { Pair p = new Pair(entry.getValue(), entry.getKey()); set.add(p); map1.put(entry.getKey(), p); } for(i = 0; i < m; i++) { // Index to be modified int j = q.get(i).first; // Value to be inserted int k = q.get(i).second; // Insert the new Pair // with value k if it was // not inserted if(map1.get(k) == null) { Pair p = new Pair(0, k); map1.put(k, p); set.add(p); } // Get the Pairs of // arr[j] and k Pair p1 = map1.get(arr[j]); set.remove(p1); Pair p2 = map1.get(k); set.remove(p2); // Decrease the frequency of // mapping with value arr[j] p1.first--; set.add(p1); // Update frequency of arr[j] // in the map map.put(arr[j], map.get(arr[j]) - 1); // Increase the frequency of // mapping with value k p2.first++; set.add(p2); // Update frequency of k if(map.containsKey(k)) map.put(k, map.get(k) + 1); else map.put(k, 1); // Replace arr[j] by k arr[j] = k; // Display maximum frequent element System.out.print( set.iterator().next().second + " "); } } // Driver Code public static void main(String []args){ int i, N, Q; N = 5; Q = 3; int arr[] = { 2, 2, 2, 3, 3 }; ArrayList<Pair> query = new ArrayList<>(); query.add(new Pair(0, 3)); query.add(new Pair(4, 2)); query.add(new Pair(0, 4)); mostFrequent(arr, N, Q, query); } }// This code is contributed by Ganeshchowdharysadanala |
Python3
# Python program to find the most# frequent element after every# update query on the arrayfrom typing import Listfrom collections import defaultdict# Function to print the most# frequent element of array# along with update querydef mostFrequent(arr: List[int], n: int, m: int, q: List[List[int]]) -> None: i = 0 # Stores element->frequencies # mappings mp = defaultdict(lambda: 0) for i in range(n): mp[arr[i]] += 1 # Stores frequencies->element # mappings s = set() # Store the frequencies in # negative for k, v in mp.items(): s.add((-v, k)) for i in range(m): # Index to be modified j = q[i][0] # Value to be inserted k = q[i][1] # Store the frequency of # arr[j] and k it = mp[arr[j]] it2 = mp[k] # Remove mapping of arr[j] # with previous frequency if (-it, arr[j]) in s: s.remove((-it, arr[j])) # Update mapping with new # frequency s.add((-(it - 1), arr[j])) # Update frequency of arr[j] # in the map mp[arr[j]] -= 1 # Remove mapping of k # with previous frequency if (-it2, k) in s: s.remove((-it2, k)) # Update mapping of k # with previous frequency s.add((-(it2 + 1), k)) # Update frequency of k mp[k] += 1 # Replace arr[j] by k arr[j] = k # Display maximum frequent element print(sorted(s)[0][1])# Driver Codeif __name__ == "__main__": N = 5 Q = 3 arr = [2, 2, 2, 3, 3] query = [[0, 3], [4, 2], [0, 4]] mostFrequent(arr, N, Q, query)# This code is contributed by sanjeev2552 |
Javascript
// JavaScript code to find the most frequent element // after every update query on the array function mostFrequent(arr, n, m, q) { let i; // Stores element->frequencies mappings let mp = new Map(); for (i = 0; i < n; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // Stores frequencies->element mappings let s = new Map(); // Store the frequencies in negative mp.forEach((value, key) => { s.set(-value, key); }); for (i = 0; i < m; i++) { // Index to be modified let j = q[i][0]; // Value to be inserted let k = q[i][1]; // Store the frequency of arr[j] and k let it = mp.get(arr[j]); let it2 = mp.get(k); // Remove mapping of arr[j] with previous frequency s.delete(-it); // Update mapping with new frequency s.set(-(it - 1), arr[j]); // Update frequency of arr[j] in the map mp.set(arr[j], mp.get(arr[j]) - 1); // Remove mapping of k with previous frequency s.delete(-it2); // Update mapping of k with previous frequency s.set(-(it2 + 1), k); // Update frequency of k mp.set(k, mp.get(k) + 1); // Replace arr[j] by k arr[j] = k; // Display maximum frequent element console.log(s.get(s.keys().next().value)); } } // Driver Code let N = 5; let Q = 3; let arr = [2, 2, 2, 3, 3]; let query = [ [0, 3], [4, 2], [0, 4] ]; mostFrequent(arr, N, Q, query); |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# program to find the most // frequent element after every // update query on the array class HelloWorld { // Function to print the most // frequent element of array // along with update query public static void mostFrequent(int[] arr, int n, int m, int[][] q) { int i = 0; // Stores element->frequencies // mappings Dictionary<int, int> mp = new Dictionary<int, int>(); for(i = 0; i < n; i++){ if (!mp.ContainsKey(arr[i])) mp.Add(arr[i], 1); else mp[arr[i]]++; } // Stores frequencies->element // mappings // SortedSet<KeyValuePair<int,int>> s = new SortedSet<KeyValuePair<int,int>>(); HashSet<KeyValuePair<int, int>> s = new HashSet<KeyValuePair<int, int>>(); // Store the frequencies in // negative foreach(KeyValuePair<int, int> it in mp) { s.Add(new KeyValuePair<int, int>(-(it.Value), it.Key)); // do something with entry.Value or entry.Key } for (i = 0; i < m; i++) { // Index to be modified int j = q[i][0]; // Value to be inserted int k = q[i][1]; // Store the frequency of // arr[j] and k if(mp.ContainsKey(arr[j])){ s.Remove(new KeyValuePair<int,int> (-(mp[arr[j]]), arr[j])); s.Add(new KeyValuePair<int,int> (-(mp[arr[j]]-1), arr[j])); } // Update frequency of arr[j] // in the map if(mp.ContainsKey(arr[j])) mp[arr[j]]--; // Store the frequency of // arr[j] and k if(mp.ContainsKey(k)){ s.Remove(new KeyValuePair<int,int> (-(mp[k]), k)); s.Add(new KeyValuePair<int,int> (-((mp[k])+1), k)); } // Console.WriteLine("hi " + i); // Update frequency of arr[j] // in the map if(mp.ContainsKey(k)) mp[k]++; else mp.Add(k, 1); // Replace arr[j] by k arr[j] = k; // Display maximum frequent element int min_ele = (int)1e5; int res =0; foreach (var item in s) { if(min_ele > item.Key){ min_ele = item.Key; res = item.Value; } } Console.Write(res + " "); } } static void Main() { int i = 0; int N = 5; int Q = 3; int[] arr = {2, 2, 2, 3, 3}; int[][] query = new int[][] { new int[] {0, 3}, new int[] {4, 2}, new int[] {0, 4} }; mostFrequent(arr, N, Q, query); }}// The code is contributed by Nidhi goel. |
Output:
3 2 2
Time Complexity: O(N + (Q * LogN))
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!