Given an array arr[] consisting of N integers and 2D array queries[][] consisting of Q queries of the form {p, x}, the task for each query is to replace the element at position p with x and print the count of distinct elements present in the array.
Examples:
Input: Q = 3, arr[] = {2, 2, 5, 5, 4, 6, 3}, queries[][] = {{1, 7}, {6, 8}, {7, 2}}
Output: {6, 6, 5}
Explanation:
The total distinct elements after each query (one-based indexing):
Query 1: p = 1 and x = 7. Therefore, arr[1] = 7 and arr[] becomes {7, 2, 5, 5, 4, 6, 3}. Hence, distinct elements = 6.
Query 2: p = 6 and x = 8. Therefore, arr[6] = 8 and arr[] becomes {7, 2, 5, 5, 4, 8, 3}. Hence, distinct elements = 6.
Query 3: p = 7 and x = 2. Therefore, arr[7] = 2 and arr[] becomes {7, 2, 5, 5, 4, 8, 2}. Hence, distinct elements = 5.Input: Q = 2, arr[] = {1, 1, 1, 1}, queries[][] = {{2, 2}, {3, 3}}
Output: {2, 3}
Explanation:
The total distinct elements after each query (one-based indexing):
Query 1: p = 2 and x = 2. Therefore, arr[2] = 2 and arr[] becomes {1, 2, 1, 1}. Hence, distinct elements = 2.
Query 2: p = 3 and x = 3. Therefore, arr[3] = 3 and arr[] becomes {1, 2, 3, 1}. Hence, distinct elements = 3.
Naive approach: The simplest approach is to update the given array for each query and insert all the elements of the updated array into a Set. Print the size of the set as the count of distinct array elements.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define R 3#define C 2// Function to the total // number of distinct elements // after each query updatevoid Distinct(int arr[], int n, int p, int x){ // Update the array arr[p - 1] = x; // Store distinct elements set<int> set; for (int i = 0; i < n; i++) { set.insert(arr[i]); } // Print the size cout << set.size() << " ";}// Function to print the count of// distinct elements for each queryvoid updateArray(int arr[], int n, int queries[R][C], int q){ // Traverse the query for (int i = 0; i < q; i++) { // Function Call to update // each query Distinct(arr, n, queries[i][0], queries[i][1]); }}// Driver Codeint main(){ // Given array arr[] int arr[] = {2, 2, 5, 5, 4, 6, 3}; int N = sizeof(arr) / sizeof(arr[0]); int Q = 3; // Given queries int queries[R][C] = {{1, 7}, {6, 8}, {7, 2}}; // Function Call updateArray(arr, N, queries, Q);}// This code is contributed by gauravrajput1 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to the total number // of distinct elements after each // query update static void Distinct(int arr[], int n, int p, int x) { // Update the array arr[p - 1] = x; // Store distinct elements Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(arr[i]); } // Print the size System.out.print(set.size() + " "); } // Function to print the count of // distinct elements for each query static void updateArray( int arr[], int n, int queries[][], int q) { // Traverse the query for (int i = 0; i < q; i++) { // Function Call to update // each query Distinct(arr, n, queries[i][0], queries[i][1]); } } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 2, 2, 5, 5, 4, 6, 3 }; int N = arr.length; int Q = 3; // Given queries int queries[][] = new int[][] { { 1, 7 }, { 6, 8 }, { 7, 2 } }; // Function Call updateArray(arr, N, queries, Q); }} |
Python3
# Python3 program for the# above approach# Function to the total number# of distinct elements after# each query updatedef Distinct(arr, n, p, x): # Update the array arr[p - 1] = x; # Store distinct elements s = set(); for i in range(n): s.add(arr[i]); # Print the size print(len(s), end = " ");# Function to print count # of distinct elements for # each querydef updateArray(arr, n, queries, q): # Traverse the query for i in range(0, q): # Function Call to update # each query Distinct(arr, n, queries[i][0], queries[i][1]);# Driver Codeif __name__ == '__main__': # Given array arr arr = [2, 2, 5, 5, 4, 6, 3]; N = len(arr); Q = 3; # Given queries queries = [[1, 7], [6, 8], [7, 2]]; # Function Call updateArray(arr, N, queries, Q);# This code is contributed by shikhasingrajput |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{// Function to the total number// of distinct elements after each// query updatestatic void Distinct(int []arr, int n, int p, int x){ // Update the array arr[p - 1] = x; // Store distinct elements HashSet<int> set = new HashSet<int>(); for (int i = 0; i < n; i++) { set.Add(arr[i]); } // Print the size Console.Write(set.Count + " ");}// Function to print the count of// distinct elements for each querystatic void updateArray(int []arr, int n, int [,]queries, int q){ // Traverse the query for (int i = 0; i < q; i++) { // Function Call to update // each query Distinct(arr, n, queries[i, 0], queries[i, 1]); }}// Driver Codepublic static void Main(String[] args){ // Given array []arr int[] arr = {2, 2, 5, 5, 4, 6, 3}; int N = arr.Length; int Q = 3; // Given queries int [,]queries = new int[,] {{1, 7}, {6, 8}, {7, 2}}; // Function Call updateArray(arr, N, queries, Q);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript Program to implement// the above approachvar R = 3var C = 2;// Function to the total // number of distinct elements // after each query updatefunction Distinct(arr, n, p, x){ // Update the array arr[p - 1] = x; // Store distinct elements var set = new Set(); for (var i = 0; i < n; i++) { set.add(arr[i]); } // Print the size document.write( set.size + " ");}// Function to print the count of// distinct elements for each queryfunction updateArray(arr, n, queries, q){ // Traverse the query for (var i = 0; i < q; i++) { // Function Call to update // each query Distinct(arr, n, queries[i][0], queries[i][1]); }}// Driver Code// Given array arr[]var arr = [2, 2, 5, 5, 4, 6, 3];var N = arr.length;var Q = 3;// Given queriesvar queries = [[1, 7], [6, 8], [7, 2]];// Function CallupdateArray(arr, N, queries, Q);</script> |
Output
6 6 5
Time Complexity: O(Q*N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to store the frequency of each array element in a Map and then traverse each query and print the size of the map after each update. Follow the below steps to solve the problem:
- Store the frequency of each element in a Map M.
- For each query {p, x}, perform the following steps:
- Decrease the frequency of arr[p] by 1 in the Map M. If its frequency reduces to 0, remove that element from the Map.
- Update arr[p] = x and increment the frequency of x by 1 in the Map if it is already present. Otherwise, add element x in the Map setting its frequency as 1.
- For each query in the above steps, print the size of the Map as the count of the distinct array elements.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define Q 3// Function to store the frequency// of each element in the Mapvoid store(int arr[], int n, map<int, int> &map){ for (int i = 0; i < n; i++) { // Store the frequency of // element arr[i] map[arr[i]]++; }}// Function to update an array // and map & to find the // distinct elementsvoid Distinct(int arr[], int n, int p, int x, map<int, int> &map){ // Decrease the element // if it was previously // present in Map map[arr[p - 1]] = map[arr[p - 1]] - 1; if (map[arr[p - 1]] == 0) map.erase(arr[p - 1]); // Add the new element // to map map[x]++; // Update the array arr[p - 1] = x; // Print the count of // distinct elements cout << (map.size()) << " ";}// Function to count the distinct// element after updating each querystatic void updateQuery(int arr[], int n, int queries[Q][2], int q){ // Store the elements in map map<int,int> map; store(arr, n, map); for (int i = 0; i < q; i++) { // Function Call Distinct(arr, n, queries[i][0], queries[i][1], map); }}// Driver Codeint main(){ // Given array arr[] int arr[] = {2, 2, 5, 5, 4, 6, 3}; int N = sizeof(arr) / sizeof(arr[0]); // Given Queries int queries[Q][2] = {{1, 7}, {6, 8}, {7, 2}}; // Function Call updateQuery(arr, N, queries, Q);}// This code is contributed by gauravrajput1 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to store the frequency // of each element in the Map static void store(int arr[], int n, HashMap<Integer, Integer> map) { for (int i = 0; i < n; i++) { // Store the frequency of // element arr[i] if (!map.containsKey(arr[i])) map.put(arr[i], 1); else map.put(arr[i], map.get(arr[i]) + 1); } } // Function to update an array and // map & to find the distinct elements static void Distinct(int arr[], int n, int p, int x, HashMap<Integer, Integer> map) { // Decrease the element if it // was previously present in Map map.put(arr[p - 1], map.get(arr[p - 1]) - 1); if (map.get(arr[p - 1]) == 0) map.remove(arr[p - 1]); // Add the new element to map if (!map.containsKey(x)) { map.put(x, 1); } else { map.put(x, map.get(x) + 1); } // Update the array arr[p - 1] = x; // Print the count of distinct // elements System.out.print(map.size() + " "); } // Function to count the distinct // element after updating each query static void updateQuery( int arr[], int n, int queries[][], int q) { // Store the elements in map HashMap<Integer, Integer> map = new HashMap<>(); store(arr, n, map); for (int i = 0; i < q; i++) { // Function Call Distinct(arr, n, queries[i][0], queries[i][1], map); } } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 2, 2, 5, 5, 4, 6, 3 }; int N = arr.length; int Q = 3; // Given Queries int queries[][] = new int[][] { { 1, 7 }, { 6, 8 }, { 7, 2 } }; // Function Call updateQuery(arr, N, queries, Q); }} |
Python3
# Python3 Program to implement# the above approach# Function to store the frequency# of each element in the Mapdef store(arr, n, Map) : for i in range(n) : # Store the frequency of # element arr[i] if (arr[i] not in Map) : Map[arr[i]] = 1 else : Map[arr[i]] += 1 # Function to update an array and# map & to find the distinct elementsdef Distinct(arr, n, p, x, Map) : # Decrease the element if it # was previously present in Map Map[arr[p - 1]] = Map[arr[p - 1]] - 1 if (Map[arr[p - 1]] == 0) : del Map[arr[p - 1]] # Add the new element to map if(x not in Map) : Map[x] = 1 else : Map[x] += 1 # Update the array arr[p - 1] = x # Print the count of distinct # elements print(len(Map), end = " ") # Function to count the distinct# element after updating each querydef updateQuery(arr, n, queries, q) : # Store the elements in map Map = {} store(arr, n, Map) for i in range(q) : # Function Call Distinct(arr, n, queries[i][0], queries[i][1], Map)# Given array []arrarr = [ 2, 2, 5, 5, 4, 6, 3 ]N = len(arr)Q = 3# Given queriesqueries = [ [ 1, 7 ], [ 6, 8 ], [ 7, 2 ] ]# Function callupdateQuery(arr, N, queries, Q)# This code is contributed by divyesh072019. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to store the frequency// of each element in the Mapstatic void store(int []arr, int n, Dictionary<int, int>map){ for(int i = 0; i < n; i++) { // Store the frequency of // element arr[i] if (!map.ContainsKey(arr[i])) map.Add(arr[i], 1); else map[arr[i]] = map[arr[i]] + 1; }}// Function to update an array and// map & to find the distinct elementsstatic void Distinct(int []arr, int n, int p, int x, Dictionary<int, int>map){ // Decrease the element if it // was previously present in Map map[arr[p - 1]] = map[arr[p - 1]] - 1; if (map[arr[p - 1]] == 0) map.Remove(arr[p - 1]); // Add the new element to map if (!map.ContainsKey(x)) { map.Add(x, 1); } else { map[x]= map[x] + 1; } // Update the array arr[p - 1] = x; // Print the count of distinct // elements Console.Write(map.Count + " ");}// Function to count the distinct// element after updating each querystatic void updateQuery(int []arr, int n, int [,]queries, int q){ // Store the elements in map Dictionary<int, int> map = new Dictionary<int, int>(); store(arr, n, map); for(int i = 0; i < q; i++) { // Function Call Distinct(arr, n, queries[i, 0], queries[i, 1], map); }}// Driver Codepublic static void Main(String[] args){ // Given array []arr int[] arr = { 2, 2, 5, 5, 4, 6, 3 }; int N = arr.Length; int Q = 3; // Given queries int [,]queries = new int[,]{ { 1, 7 }, { 6, 8 }, { 7, 2 } }; // Function call updateQuery(arr, N, queries, Q);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Function to store the frequency // of each element in the Mapfunction store(arr,n,map){ for (let i = 0; i < n; i++) { // Store the frequency of // element arr[i] if (!map.has(arr[i])) map.set(arr[i], 1); else map.set(arr[i], map.get(arr[i]) + 1); }} // Function to update an array and // map & to find the distinct elementsfunction Distinct(arr,n,p,x,map){ // Decrease the element if it // was previously present in Map map.set(arr[p - 1], map.get(arr[p - 1]) - 1); if (map.get(arr[p - 1]) == 0) map.delete(arr[p - 1]); // Add the new element to map if (!map.has(x)) { map.set(x, 1); } else { map.set(x, map.get(x) + 1); } // Update the array arr[p - 1] = x; // Print the count of distinct // elements document.write(map.size + " ");}// Function to count the distinct // element after updating each queryfunction updateQuery(arr,n,queries,q){ // Store the elements in map let map = new Map(); store(arr, n, map); for (let i = 0; i < q; i++) { // Function Call Distinct(arr, n, queries[i][0], queries[i][1], map); }}// Driver Codelet arr=[2, 2, 5, 5, 4, 6, 3];let N = arr.length;let Q = 3;let queries=[[ 1, 7 ],[ 6, 8 ],[ 7, 2 ]];// Function CallupdateQuery(arr, N, queries, Q);// This code is contributed by patel2127</script> |
Output
6 6 5
Time Complexity: O(N + Q)
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!