Data Modelling & AI Data Structure & Algorithm

Replace all occurrences of X by Y for Q queries in given Array

23 June 2025

0

Given an array arr[] and an 2D array query[][] consisting of queries. For each query q, replace all occurrences of query[i][0] in arr[], with query[i][1].

Examples:

Input: arr[] = {2, 2, 5, 1} query = {{2, 4}, {5, 2}}
Output: {4, 4, 2, 1}
Explanation: Following are the operations performed in the given array according to the queries given.
For first query {2, 4}, replace all occurrences of 2 in arr[] with 4. arr[] will be updated as arr[] = {4, 4, 5, 1}.
For second query {5, 2}, replace all occurrences of 5 with 2. arr[] will be updated as arr[] = {4, 4, 2, 1}.

Input: arr[] ={2, 2, 5}, query = {{4, 5}, {2, 5}, {1, 3}, {2, 4}}
Output: {5, 5, 5}

Naive Approach: (Brute-Force solution) Naive approach would be to iterate through all the queries of query, and for each query[i][0], find all of its occurrences in arr[], and replace it with query[i][1].

Time Complexity: O(N*Q), where N is the size of arr[] and Q is size of query[][].
Auxiliary Space: O(1)

Efficient Approach: A better solution would be to use a Hashmap, that stores indexes of the element in the array. Follow the steps below to solve the given problem.

Initialize a hashmap = {}, and fill it up with array element as key, and list indicating its position in the array.
Iterate through each query q of query[][].
- If q[0] is present in the hashmap,
  - If q[1] is present in the hashmap, then extend the value of q[0] to the value of q[1] key.
  - Else, add the value to q[1] key with the value of q[0] key.
  - Delete the key-value pair for q[0] from the hashmap.
Now, create a new variable map = {}, from the values of the hashmap.
Interchange the key-value pairs, so that map will contain key-value pairs as index, and key value of hashmap.
Using this map, we can now update the original array arr, by updating values at each position of arr, with the value from map.

Below is the implementation of the above approach:

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to replace all the
// occurrences of a number with
// another given number for Q queries
void update(vector<int>& A, int N, vector<vector<int> >& Q)
{
   
    // Creating a hashmap
    map<int, vector<int> > hashmap;
    for (int i = 0; i < N; ++i) {
        hashmap[A[i]].push_back(i);
    }
 
    // Iterating with q in given queries
    for (auto q : Q) {
        if (hashmap.count(q[0])) {
            if (hashmap.count(q[1]))
                hashmap[q[1]].insert(hashmap[q[1]].end(),
                                     hashmap[q[0]].begin(),
                                     hashmap[q[0]].end());
            else
                hashmap[q[1]] = hashmap[q[0]];
            hashmap.erase(q[0]);
        }
    }
 
    // Creating map to store key value pairs
    map<int, int> new_map;
    for (auto it = hashmap.begin(); it != hashmap.end();
         ++it) {
        for (auto index : it->second)
            new_map[index] = it->first;
    }
 
    // Updating the main array with final values
    for (auto it = new_map.begin(); it != new_map.end();
         ++it)
        A[it->first] = it->second;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 2, 5, 1 };
    int N = arr.size();
    vector<vector<int> > query = { { 2, 4 }, { 5, 2 } };
    update(arr, N, query);
    for (int i = 0; i < N; ++i) {
        cout << arr[i] << " ";
    }
 
   return 0;
}
 
    // This code is contributed by rakeshsahni

Java

// Java program for above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to replace all the
  // occurrences of a number with
  // another given number for Q queries
  static void update(List<Integer> A, int N,
                     List<List<Integer> > Q)
  {
    // Creating a hashmap
    Map<Integer, List<Integer> > hashmap
      = new HashMap<>();
    for (int i = 0; i < N; ++i) {
      List<Integer> indices = hashmap.getOrDefault(
        A.get(i), new ArrayList<>());
      indices.add(i);
      hashmap.put(A.get(i), indices);
    }
 
    // Iterating with q in given queries
    for (List<Integer> q : Q) {
      if (hashmap.containsKey(q.get(0))) {
        if (hashmap.containsKey(q.get(1))) {
          hashmap.get(q.get(1)).addAll(
            hashmap.get(q.get(0)));
        }
        else {
          hashmap.put(q.get(1),
                      hashmap.get(q.get(0)));
        }
        hashmap.remove(q.get(0));
      }
    }
 
    // Creating map to store key value pairs
    Map<Integer, Integer> newMap = new HashMap<>();
    for (Map.Entry<Integer, List<Integer> > entry :
         hashmap.entrySet()) {
      for (int index : entry.getValue()) {
        newMap.put(index, entry.getKey());
      }
    }
 
    // Updating the main array with final values
    for (Map.Entry<Integer, Integer> entry :
         newMap.entrySet()) {
      A.set(entry.getKey(), entry.getValue());
    }
  }
 
  public static void main(String[] args)
  {
    List<Integer> arr = Arrays.asList(2, 2, 5, 1);
    int N = arr.size();
    List<List<Integer> > query = Arrays.asList(
      Arrays.asList(2, 4), Arrays.asList(5, 2));
    update(arr, N, query);
    System.out.print(arr.toString());
  }
}
 
// This code is contributed by lokesh.

Python3

# Python program for above approach
 
# Function to replace all the
# occurrences of a number with
# another given number for Q queries
def update(A, N, Q):
      # Creating a hashmap 
    hashmap = {a:[] for a in A}
    for i in range(N):
        hashmap[A[i]].append(i)
     
    # Iterating with q in given queries
    for q in Q:
        if q[0] in hashmap:
            if q[1] in hashmap:
                hashmap[q[1]].extend(hashmap[q[0]])
            else:
                hashmap[q[1]] = hashmap[q[0]]
            del hashmap[q[0]]
 
    # Creating map to store key value pairs
    new_map = {}
    for key, value in hashmap.items():
        for index in value:
            new_map[index] = key
             
    # Updating the main array with final values
    for key in new_map.keys():
        A[key] = new_map[key]
     
# Driver Code
if __name__ == '__main__':
  arr = [2, 2, 5, 1]
  N = len(arr)
  query = [[2, 4], [5, 2]]
  update(arr, N, query)
  print(arr)

C#

// C# program for above approach
 
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
 
    // Function to replace all the
    // occurrences of a number with
    // another given number for Q queries
    static void update(List<int> A, int N, List<List<int>> Q)
    {
        // Creating a hashmap
        var hashmap = new Dictionary<int, List<int>>();
        for (int i = 0; i < N; ++i)
        {
            if (!hashmap.ContainsKey(A[i]))
                hashmap[A[i]] = new List<int>();
            hashmap[A[i]].Add(i);
        }
 
        // Iterating with q in given queries
        for (int i = 0; i < Q.Count; i++)
        {
            if (hashmap.ContainsKey(Q[i][0]))
            {
                if (hashmap.ContainsKey(Q[i][1]))
                {
                    hashmap[Q[i][1]].AddRange(hashmap[Q[i][0]]);
                }
                else
                {
                    hashmap[Q[i][1]] = hashmap[Q[i][0]];
                }
                hashmap.Remove(Q[i][0]);
            }
        }
 
        // Creating map to store key value pairs
        var newMap = new Dictionary<int, int>();
        foreach (var entry in hashmap)
        {
            for (int j = 0; j < entry.Value.Count; j++)
            {
                newMap[entry.Value[j]] = entry.Key;
            }
        }
 
        // Updating the main array with final values
        for (int i = 0; i < A.Count; i++)
        {
            if (newMap.ContainsKey(i))
            {
                A[i] = newMap[i];
            }
        }
    }
     
    // Driver code
    public static void Main(string[] args)
    {
         
        List<int> arr = new List<int> { 2, 2, 5, 1 };
        int N = arr.Count;
        List<List<int>> query = new List<List<int>> {
            new List<int> { 2, 4 },
            new List<int> { 5, 2 }
        };
        update(arr, N, query);
        Console.WriteLine(string.Join(" ", arr));
    }
 
}

Javascript

<script>
// Javascript program for above approach
 
// Function to replace all the
// occurrences of a number with
// another given number for Q queries
function update(A, N, Q)
{
 
      // Creating a hashmap 
    let hashmap = new Map();
    for(let i = 0; i < N; i++){
        if(hashmap.has(A[i])){
          let temp = hashmap.get(A[i])
          temp.push(i)
          hashmap.set(A[i], temp)
        }else{
          hashmap.set(A[i], [i])
        }
 
    }
     
    // Iterating with q in given queries
    for(q of Q){
        if(hashmap.has(q[0])){
            if (hashmap.has(q[1])){
                let temp = hashmap.get(q[1]);
                 
                temp = [...temp, ...hashmap.get(q[0])]
                hashmap.set(q[1], temp);
            }
            else{
                hashmap.set(q[1], hashmap.get(q[0]))
            }
            hashmap.delete(q[0])
        }
    }
 
    // Creating map to store key value pairs
    let new_map = new Map()
    for(x of hashmap)
        for(index of x[1])
            new_map.set(index, x[0])
             
    // Updating the main array with final values
    for(key of new_map.keys())
        A[key] = new_map.get(key)
    document.write(`[ ${A}] `)
}
     
// Driver Code
let arr = [2, 2, 5, 1]
let N = arr.length
let query = [[2, 4], [5, 2]]
update(arr, N, query)
 
// This code is contributed by gfgking.
</script>

Output:

[4, 4, 2, 1]

Time Complexity: O(N+Q), where N is size of arr[] and Q is size of query[][].
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!

Replace all occurrences of X by Y for Q queries in given Array

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

Spotify now lets you transfer playlists from other services

EDITOR PICKS

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

POPULAR POSTS

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

POPULAR CATEGORY

ABOUT US

FOLLOW US