Given an array arr[] consisting of N integers, consisting only of 0‘s initially and queries Q[][] of the form {L, R, C}, the task for each query is to update the subarray [L, R] with value C. Print the final array generated after performing all the queries.
Examples:
Input: N = 5, Q = {{1, 4, 1}, {3, 5, 2}, {2, 4, 3}}
Output: 1 3 3 3 2
Explanation:
Initially, the array is {0, 0, 0, 0, 0}
Query 1 modifies the array to {1, 1, 1, 1, 0}
Query 2 modifies the array to {1, 1, 2, 2, 2}
Query 3 modifies the array to {1, 3, 3, 3, 2}Input: N = 3, Q = {{1, 2, 1}, {2, 3, 2}}
Output: 1 2 2
Explanation:
Initially, the array is {0, 0, 0}
Query 1 modifies the array to {1, 1, 0}
Query 2 modifies the array to {1, 2, 2}
Approach: The idea is to use Disjoint Set Union to solve the problem.Follow the steps below to solve the problem:
- Initially, all the array elements will be considered as separate sets and parent of itself and will store the next array element with value 0.
- First, store the query and process the queries in reverse order from last to first because the value assigned to each set will be final.
- After processing the first query, elements with the changed value will point to the next element. This way on executing a query, we only have to assign values to the non-updated sets in the subarray [l, r]. All other cells already contain their final values.
- Find the left-most non-updated set, and update it, and with the pointer, move to the next non-updated set to the right.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Maximum possible size of array #define MAX_NODES 100005 // Stores the parent of each element int parent[MAX_NODES]; // Stores the final array values int final_val[MAX_NODES]; // Structure to store queries struct query { int l, r, c; }; // Function to initialize the // parent of each vertex void make_set(int v) { // Initially parent // of each node points // to itself parent[v] = v; } // Function to find the representative // of the set which contain element v int find_set(int v) { if (v == parent[v]) return v; // Path compression return parent[v] = find_set(parent[v]); } // Function to assign a // parent to each element void Initialize(int n) { for (int i = 0; i <= n; i++) make_set(i + 1); } // Function to process the queries void Process(query Q[], int q) { for (int i = q - 1; i >= 0; i--) { int l = Q[i].l, r = Q[i].r, c = Q[i].c; for (int v = find_set(l); v <= r; v = find_set(v)) { final_val[v] = c; parent[v] = v + 1; } } } // Function to print the final array void PrintAns(int n) { for (int i = 1; i <= n; i++) { cout << final_val[i] << " "; } cout << endl; } // Driver Code int main() { int n = 5; // Set all the elements as the // parent of itself using make_set Initialize(n); int q = 3; query Q[q]; // Store the queries Q[0].l = 1, Q[0].r = 4, Q[0].c = 1; Q[1].l = 3, Q[1].r = 5, Q[1].c = 2; Q[2].l = 2, Q[2].r = 4, Q[2].c = 3; // Process the queries Process(Q, q); // Print the required array PrintAns(n); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Maximum possible size of array static final int MAX_NODES = 100005; // Stores the parent of each element static int []parent = new int[MAX_NODES]; // Stores the final array values static int []final_val = new int[MAX_NODES]; // Structure to store queries static class query { int l, r, c; }; // Function to initialize the // parent of each vertex static void make_set(int v) { // Initially parent // of each node points // to itself parent[v] = v; } // Function to find the representative // of the set which contain element v static int find_set(int v) { if (v == parent[v]) return v; // Path compression return parent[v] = find_set(parent[v]); } // Function to assign a // parent to each element static void Initialize(int n) { for(int i = 0; i <= n; i++) make_set(i + 1); } // Function to process the queries static void Process(query Q[], int q) { for(int i = q - 1; i >= 0; i--) { int l = Q[i].l, r = Q[i].r, c = Q[i].c; for(int v = find_set(l); v <= r; v = find_set(v)) { final_val[v] = c; parent[v] = v + 1; } } } // Function to print the final array static void PrintAns(int n) { for(int i = 1; i <= n; i++) { System.out.print(final_val[i] + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { int n = 5; // Set all the elements as the // parent of itself using make_set Initialize(n); int q = 3; query []Q = new query[q]; for(int i = 0; i < Q.length; i++) Q[i] = new query(); // Store the queries Q[0].l = 1; Q[0].r = 4; Q[0].c = 1; Q[1].l = 3; Q[1].r = 5; Q[1].c = 2; Q[2].l = 2; Q[2].r = 4; Q[2].c = 3; // Process the queries Process(Q, q); // Print the required array PrintAns(n); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program to implement # the above approach MAX_NODES = 100005 # Stores the parent of each element parent = [0] * MAX_NODES # Stores the final array values final_val = [0] * MAX_NODES # Structure to store queries # Function to initialize the # parent of each vertex def make_set(v): # Initially parent # of each node points # to itself parent[v] = v # Function to find the representative # of the set which contain element v def find_set(v): if (v == parent[v]): return v # Path compression parent[v] = find_set(parent[v]) return parent[v] # Function to assign a # parent to each element def Initialize(n): for i in range(n + 1): make_set(i + 1) # Function to process the queries def Process(Q, q): for i in range(q - 1, -1, -1): l = Q[i][0] r = Q[i][1] c = Q[i][2] v = find_set(l) while v <= r: final_val[v] = c parent[v] = v + 1 v = find_set(v) # Function to print the final array def PrintAns(n): for i in range(1, n + 1): print(final_val[i], end = " ") # Driver Code if __name__ == '__main__': n = 5 # Set all the elements as the # parent of itself using make_set Initialize(n) q = 3 Q = [[0 for i in range(3)] for i in range(q)] # Store the queries Q[0][0] = 1 Q[0][1] = 4 Q[0][2] = 1 Q[1][0] = 3 Q[1][1] = 5 Q[1][2] = 2 Q[2][0] = 2 Q[2][1] = 4 Q[2][2] = 3 # Process the queries Process(Q, q) # Print the required array PrintAns(n) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Maximum possible size of array static readonly int MAX_NODES = 100005; // Stores the parent of each element static int []parent = new int[MAX_NODES]; // Stores the readonly array values static int []final_val = new int[MAX_NODES]; // Structure to store queries class query { public int l, r, c; }; // Function to initialize the // parent of each vertex static void make_set(int v) { // Initially parent // of each node points // to itself parent[v] = v; } // Function to find the representative // of the set which contain element v static int find_set(int v) { if (v == parent[v]) return v; // Path compression return parent[v] = find_set(parent[v]); } // Function to assign a // parent to each element static void Initialize(int n) { for(int i = 0; i <= n; i++) make_set(i + 1); } // Function to process the queries static void Process(query []Q, int q) { for(int i = q - 1; i >= 0; i--) { int l = Q[i].l, r = Q[i].r, c = Q[i].c; for(int v = find_set(l); v <= r; v = find_set(v)) { final_val[v] = c; parent[v] = v + 1; } } } // Function to print the readonly array static void PrintAns(int n) { for(int i = 1; i <= n; i++) { Console.Write(final_val[i] + " "); } Console.WriteLine(); } // Driver Code public static void Main(String[] args) { int n = 5; // Set all the elements as the // parent of itself using make_set Initialize(n); int q = 3; query []Q = new query[q]; for(int i = 0; i < Q.Length; i++) Q[i] = new query(); // Store the queries Q[0].l = 1; Q[0].r = 4; Q[0].c = 1; Q[1].l = 3; Q[1].r = 5; Q[1].c = 2; Q[2].l = 2; Q[2].r = 4; Q[2].c = 3; // Process the queries Process(Q, q); // Print the required array PrintAns(n); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program to implement // the above approach // Maximum possible size of array let MAX_NODES = 100005; // Stores the parent of each element let parent = new Array(MAX_NODES); // Stores the final array values let final_val = new Array(MAX_NODES); // Structure to store queries class query { constructor() { let l, r, c; } } // Function to initialize the // parent of each vertex function make_set(v) { // Initially parent // of each node points // to itself parent[v] = v; } // Function to find the representative // of the set which contain element v function find_set(v) { if (v == parent[v]) return v; // Path compression return parent[v] = find_set(parent[v]); } // Function to assign a // parent to each element function Initialize(n) { for(let i = 0; i <= n; i++) make_set(i + 1); } // Function to process the queries function Process(Q,q) { for(let i = q - 1; i >= 0; i--) { let l = Q[i].l, r = Q[i].r, c = Q[i].c; for(let v = find_set(l); v <= r; v = find_set(v)) { final_val[v] = c; parent[v] = v + 1; } } } // Function to print the final array function PrintAns(n) { for(let i = 1; i <= n; i++) { document.write(final_val[i] + " "); } document.write("<br>"); } // Driver Code let n = 5; // Set all the elements as the // parent of itself using make_set Initialize(n); let q = 3; let Q = new Array(q); for(let i = 0; i < Q.length; i++) Q[i] = new query(); // Store the queries Q[0].l = 1; Q[0].r = 4; Q[0].c = 1; Q[1].l = 3; Q[1].r = 5; Q[1].c = 2; Q[2].l = 2; Q[2].r = 4; Q[2].c = 3; // Process the queries Process(Q, q); // Print the required array PrintAns(n); // This code is contributed by unknown2108 </script> |
Output:
1 3 3 3 2
Time complexity: O(log N)
Auxiliary Space: O(MAX_NODES)
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!
