Most frequent element in Array after replacing given index by K for Q queries
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 elements static 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 array from typing import List from collections import defaultdict # Function to print the most # frequent element of array # along with update query def 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 Code if __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)