Check if Array elements in given range form Permutation by performing given updates
Given an array arr[] consisting of N distinct integers and a 2d array Q[][3] consisting of M queries of the 2 types whose operations are as follows:
- [1, P, X] update position P with X.
- [2, L, R] check if array elements over the range [L, R] forms a permutation or not.
For each query of the second type, find if the range [L, R] forms a permutation or not
Examples:
Input: arr[] = {6, 4, 1, 2, 3, 8, 10}, Q[][] = {{2, 2, 4}, {1, 2, 9}, {2, 2, 4}, {1, 2, 1}, {2, 0, 4}, {1, 0, 5}, {2, 0, 4}}
Output:
YES
NO
NO
YESExplanation:
Query 1: This is Query Type 2. The elements of the array over the range [2, 4] are {1, 2, 3} which forms a permutation. Hence, print “YES”.
Query 2: This is Query Type 1. [2, 9] We Update index 2 with 9 now arr[] becomes {6, 4, 9, 2, 3, 8, 10}.
Query 3: This is Query Type 2. The elements of the array over the range [2, 4] are [9, 2, 3] which does not forms a permutation. Hence, Print “NO”
Query 4: This is Query Type 1. [2, 1] We Update index 2 with 1 now arr[] becomes {6, 4, 1, 2, 3, 8, 10}.
Query 5: This is Query Type 2. The elements of the array over the range [0, 4] are [6, 4, 1, 2, 3] which does not forms a permutation. Hence, Print “NO”
Query 6: This is Query Type 1. [0, 5] We Update index 0 with 5 now arr[] becomes {5, 4, 1, 2, 3, 8, 10}.
Query 7: This is Query Type 2. The elements of the array over the range [0, 4] are {5, 4, 1, 2, 3} which forms a permutation. Hence, print “YES”.Input: arr[] = {1, 2, 4, 3, 9}, Q[][] = {{2, 0, 3}, {1, 0, 5}, {2, 0, 3}}
Output:
YES
NO
Naive Approach: The basic way to solve the problem is as follows:
Each query of type 1 can be handled in constant time just by updating respective index. For queries of second type, Traverse the given array over the range [L, R] and check if every element is present or not from 1 to R – L + 1. This can be done by taking the sum of all elements from L to R if it is equal to the sum of 1 + 2 + 3 + 4 + . . . . + size of subarray [L, R], then print “YES”. Otherwise, print “NO”.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using a segment tree based on the following idea:
The idea is rather than calculating the sum of elements from L to R for each query we can maintain answer for every range from L to R using Segment Tree. For Each query of type 2, sum from L to R can be found in O(log n) time by using the segment tree. Query of type 1 can be handled using segment tree in O(logn) per query.
The sum from 1 + 2 + 3 + 4 + . . . + size of subarray [L, R] can be found using the number theory formula for finding the sum of the first n natural numbers which is n * (n + 1) / 2.
Follow the steps below to solve the problem:
- Build a segment tree for the given array arr[] in O(N * logN).
- Traverse the given array of queries Q[][]
- For query of type 1 call updateValue function and pass pos (position) and value .
- For each query of the second type, initiate the size variable with the size of the subarray [L, R].
- Initiate the total_From_1_To_Size variable with n * ( n + 1) / 2.
- Initialize the variable total_From_L_To_R and get the value from the segment tree.
- If total_From_L_To_R and total_From_1_To_Size are equal then print “YES” else print “NO“.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to get the middle index // from corner indices. int getMiddleValue( int low, int high) { return low + (high - low) / 2; } // A recursive function to get the sum of values // in the given range of the array. // st --> Pointer to segment tree // node --> Index of current node in the segment tree. // low & high --> Starting and ending indices // of the segment represented by current node. // L & R --> Starting and ending indices of query range int getSumUtil( int * st, int low, int high, int L, int R, int node) { // If segment of this node is a part of given range // then return the sum of the segment if (L <= low && R >= high) return st[node]; // If segment of this node is outside the given range if (high < L || low > R) return 0; // If a part of this segment // overlaps with the given range int mid = getMiddleValue(low, high); return getSumUtil(st, low, mid, L, R, 2 * node + 1) + getSumUtil(st, mid + 1, high, L, R, 2 * node + 2); } // Recursive function to update the nodes // which have the given index in their range. void updateValueUtil( int * st, int low, int high, int i, int diff, int node) { // If the input index lies outside // the range of this segment if (i < low || i > high) return ; // If the input index is in range of this node, // then update the value of the node // and its children st[node] = st[node] + diff; if (high != low) { int mid = getMiddleValue(low, high); updateValueUtil(st, low, mid, i, diff, 2 * node + 1); updateValueUtil(st, mid + 1, high, i, diff, 2 * node + 2); } } // Function to update a value in input array // and segment tree. // It uses updateValueUtil() to update // the value in segment tree void updateValue( int arr[], int * st, int n, int i, int new_val) { // Get the difference between new and old value int diff = new_val - arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0, n - 1, i, diff, 0); } // Return sum of elements in range from index L (query // start) to R (query end). It mainly uses getSumUtil() int getSum( int * st, int n, int L, int R) { return getSumUtil(st, 0, n - 1, L, R, 0); } // Recursive function that constructs Segment Tree // for array[low..high]. int buildSegTreeUtil( int arr[], int low, int high, int * st, int node) { // If there is one element in array, // store it in current node of segment if (low == high) { st[node] = arr[low]; return arr[low]; } // If there are more than one elements, // then recur for left and right subtrees and // store the sum of values in this node int mid = getMiddleValue(low, high); st[node] = buildSegTreeUtil(arr, low, mid, st, node * 2 + 1) + buildSegTreeUtil(arr, mid + 1, high, st, node * 2 + 2); return st[node]; } // Function to construct segment tree from given array. // This function allocates memory for segment tree and // calls buildSegTreeUtil() to fill the allocated memory int * buildSegTree( int arr[], int n) { // Height of segment tree int x = ( int )( ceil (log2(n))); // Maximum size of segment tree int max_size = 2 * ( int ) pow (2, x) - 1; // Allocate memory int * st = new int [max_size]; // Fill the allocated memory st buildSegTreeUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } // Function to check if the subarray is permutation or not void findPermutation( int arr[], int N, int Q[][3], int M) { // Build segment tree from given array int * st = buildSegTree(arr, N); // Traverse the given queries for ( int i = 0; i < M; i++) { // Query type for querying int queryType = Q[i][0]; // If query is of type 1 if (queryType == 1) { // Position and value for update int pos = Q[i][1], value = Q[i][2]; // Update: set arr[pos] = value and update // corresponding segment tree nodes updateValue(arr, st, N, pos, value); } else { // Stores range L to R for // type 2 query int L = Q[i][1], R = Q[i][2]; // Size variable stores size of // [L, R] range int size = R - L + 1; // Stores total from 1 to size of // range [L, R] int total_From_1_To_Size = size * (size + 1) / 2; // Print sum of values in array // from index L to R int total_From_L_To_R = getSum(st, N, L, R); // If total from 1 to size is equal // to total from L to R then print yes if (total_From_L_To_R == total_From_1_To_Size) { cout << "YES" << endl; } else { cout << "NO" << endl; } } } } // Driver code int main() { int arr[] = { 6, 4, 1, 2, 3, 8, 10 }; int N = sizeof (arr) / sizeof (arr[0]); int Q[][3] = { { 2, 2, 4 }, { 1, 2, 9 }, { 2, 2, 4 }, { 1, 2, 1 }, { 2, 0, 4 }, { 1, 0, 5 }, { 2, 0, 4 } }; int M = sizeof (Q) / sizeof (Q[0]); // Function call findPermutation(arr, N, Q, M); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to get the middle index // from corner indices. static int getMiddleValue( int low, int high) { return low + (high - low) / 2 ; } // A recursive function to get the sum of values // in the given range of the array. // st --> Pointer to segment tree // node --> Index of current node in the segment tree. // low & high --> Starting and ending indices // of the segment represented by current node. // L & R --> Starting and ending indices of query range static int getSumUtil( int [] st, int low, int high, int L, int R, int node) { // If segment of this node is a part of given range // then return the sum of the segment if (L <= low && R >= high) return st[node]; // If segment of this node is outside the given // range if (high < L || low > R) return 0 ; // If a part of this segment // overlaps with the given range int mid = getMiddleValue(low, high); return getSumUtil(st, low, mid, L, R, 2 * node + 1 ) + getSumUtil(st, mid + 1 , high, L, R, 2 * node + 2 ); } // Recursive function to update the nodes // which have the given index in their range. static void updateValueUtil( int [] st, int low, int high, int i, int diff, int node) { // If the input index lies outside // the range of this segment if (i < low || i > high) return ; // If the input index is in range of this node, // then update the value of the node // and its children st[node] = st[node] + diff; if (high != low) { int mid = getMiddleValue(low, high); updateValueUtil(st, low, mid, i, diff, 2 * node + 1 ); updateValueUtil(st, mid + 1 , high, i, diff, 2 * node + 2 ); } } // Function to update a value in input array // and segment tree. // It uses updateValueUtil() to update // the value in segment tree static void updateValue( int [] arr, int [] st, int n, int i, int new_val) { // Get the difference between new and old value int diff = new_val - arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0 , n - 1 , i, diff, 0 ); } // Return sum of elements in range from index L (query // start) to R (query end). It mainly uses getSumUtil() static int getSum( int [] st, int n, int L, int R) { return getSumUtil(st, 0 , n - 1 , L, R, 0 ); } // Recursive function that constructs Segment Tree // for array[low..high]. static int buildSegTreeUtil( int arr[], int low, int high, int [] st, int node) { // If there is one element in array, // store it in current node of segment if (low == high) { st[node] = arr[low]; return arr[low]; } // If there are more than one elements, // then recur for left and right subtrees and // store the sum of values in this node int mid = getMiddleValue(low, high); st[node] = buildSegTreeUtil(arr, low, mid, st, node * 2 + 1 ) + buildSegTreeUtil(arr, mid + 1 , high, st, node * 2 + 2 ); return st[node]; } // Function to construct segment tree from given array. // This function allocates memory for segment tree and // calls buildSegTreeUtil() to fill the allocated memory static int [] buildSegTree( int arr[], int n) { // Height of segment tree int x = ( int )(Math.ceil(Math.log(n) / Math.log( 2 ))); // Maximum size of segment tree int max_size = 2 * ( int )Math.pow( 2 , x) - 1 ; // Allocate memory int [] st = new int [max_size]; // Fill the allocated memory st buildSegTreeUtil(arr, 0 , n - 1 , st, 0 ); // Return the constructed segment tree return st; } // Function to check if the subarray is permutation or not static void findPermutation( int [] arr, int N, int [][] Q, int M) { // Build segment tree from given array int [] st = buildSegTree(arr, N); // Traverse the given queries for ( int i = 0 ; i < M; i++) { // Query type for querying int queryType = Q[i][ 0 ]; // If query is of type 1 if (queryType == 1 ) { // Position and value for update int pos = Q[i][ 1 ], value = Q[i][ 2 ]; // Update: set arr[pos] = value and update // corresponding segment tree nodes updateValue(arr, st, N, pos, value); } else { // Stores range L to R for // type 2 query int L = Q[i][ 1 ], R = Q[i][ 2 ]; // Size variable stores size of // [L, R] range int size = R - L + 1 ; // Stores total from 1 to size of // range [L, R] int total_From_1_To_Size = size * (size + 1 ) / 2 ; // Print sum of values in array // from index L to R int total_From_L_To_R = getSum(st, N, L, R); // If total from 1 to size is equal // to total from L to R then print yes if (total_From_L_To_R == total_From_1_To_Size) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } } public static void main(String[] args) { int [] arr = { 6 , 4 , 1 , 2 , 3 , 8 , 10 }; int N = arr.length; int [][] Q = { { 2 , 2 , 4 }, { 1 , 2 , 9 }, { 2 , 2 , 4 }, { 1 , 2 , 1 }, { 2 , 0 , 4 }, { 1 , 0 , 5 }, { 2 , 0 , 4 } }; int M = Q.length; // Function call findPermutation(arr, N, Q, M); } } // This code is contributed by lokesh |
Python3
import math def getMiddleValue(low, high): return low + (high - low) / / 2 # A recursive function to get the sum of values # in the given range of the array. # st --> Pointer to segment tree # node --> Index of current node in the segment tree. # low & high --> Starting and ending indices # of the segment represented by current node. # L & R --> Starting and ending indices of query range def getSumUtil(st, low, high, L, R, node): # If segment of this node is a part of given range # then return the sum of the segment if L < = low and R > = high: return st[node] # If segment of this node is outside the given range if high < L or low > R: return 0 # If a part of this segment # overlaps with the given range mid = getMiddleValue(low, high) return getSumUtil(st, low, mid, L, R, 2 * node + 1 ) + \ getSumUtil(st, mid + 1 , high, L, R, 2 * node + 2 ) # Recursive function to update the nodes # which have the given index in their range. def updateValueUtil(st, low, high, i, diff, node): # If the input index lies outside # the range of this segment if i < low or i > high: return # If the input index is in range of this node, # then update the value of the node # and its children st[node] + = diff if high ! = low: mid = getMiddleValue(low, high) updateValueUtil(st, low, mid, i, diff, 2 * node + 1 ) updateValueUtil(st, mid + 1 , high, i, diff, 2 * node + 2 ) # Function to update a value in input array # and segment tree. # It uses updateValueUtil() to update # the value in segment tree def updateValue(arr, st, n, i, new_val): # Get the difference between new and old value diff = new_val - arr[i] # Update the value in array arr[i] = new_val # Update the values of nodes in segment tree updateValueUtil(st, 0 , n - 1 , i, diff, 0 ) # Return sum of elements in range from index L (query # start) to R (query end). It mainly uses getSumUtil() def getSum(st, n, L, R): return getSumUtil(st, 0 , n - 1 , L, R, 0 ) # Recursive function that constructs Segment Tree # for array[low..high]. def buildSegTreeUtil(arr, low, high, st, node): # If there is one element in array, # store it in current node of segment if low = = high: st[node] = arr[low] return arr[low] # If there are more than one elements, # then recur for left and right subtrees and # store the sum of values in this node mid = getMiddleValue(low, high) st[node] = buildSegTreeUtil(arr, low, mid, st, node * 2 + 1 ) + \ buildSegTreeUtil(arr, mid + 1 , high, st, node * 2 + 2 ) return st[node] # Function to construct segment tree from given array. # This function allocates memory for segment tree and # calls buildSegTreeUtil() to fill the allocated memory def buildSegTree(arr): # Allocate memory for segment tree n = len (arr) height = int (math.ceil(math.log2(n))) max_size = 2 * int (math. pow ( 2 , height)) - 1 st = [ 0 ] * max_size # Fill the allocated memory st # using the values in the given array buildSegTreeUtil(arr, 0 , n - 1 , st, 0 ) return st def findPermutation(arr, N, Q, M): # Build segment tree from given array st = buildSegTree(arr) # Traverse the given queries for i in range (M): # Query type for querying queryType = Q[i][ 0 ] # If query is of type 1 if queryType = = 1 : # Position and value for update pos, value = Q[i][ 1 ], Q[i][ 2 ] # Update: set arr[pos] = value and update # corresponding segment tree nodes updateValue(arr, st, N, pos, value) else : # Stores range L to R for # type 2 query L, R = Q[i][ 1 ], Q[i][ 2 ] # Size variable stores size of # [L, R] range size = R - L + 1 # Stores total from 1 to size of # range [L, R] total_From_1_To_Size = size * (size + 1 ) / / 2 # Print sum of values in array # from index L to R total_From_L_To_R = getSum(st, N, L, R) # If total from 1 to size is equal # to total from L to R then print yes if total_From_L_To_R = = total_From_1_To_Size: print ( "YES" ) else : print ( "NO" ) # Driver code if __name__ = = "__main__" : arr = [ 6 , 4 , 1 , 2 , 3 , 8 , 10 ] N = len (arr) Q = [[ 2 , 2 , 4 ], [ 1 , 2 , 9 ], [ 2 , 2 , 4 ], [ 1 , 2 , 1 ], [ 2 , 0 , 4 ], [ 1 , 0 , 5 ], [ 2 , 0 , 4 ]] M = len (Q) # Function call findPermutation(arr, N, Q, M) # This code is contributed by lokeshpotta20. |
C#
// C# code to implement the approach using System; class GFG { // Function to get the middle index // from corner indices. static int getMiddleValue( int low, int high) { return low + (high - low) / 2; } // A recursive function to get the sum of values // in the given range of the array. // st --> Pointer to segment tree // node --> Index of current node in the segment tree. // low & high --> Starting and ending indices // of the segment represented by current node. // L & R --> Starting and ending indices of query range static int getSumUtil( int [] st, int low, int high, int L, int R, int node) { // If segment of this node is a part of given range // then return the sum of the segment if (L <= low && R >= high) return st[node]; // If segment of this node is outside the given // range if (high < L || low > R) return 0; // If a part of this segment // overlaps with the given range int mid = getMiddleValue(low, high); return getSumUtil(st, low, mid, L, R, 2 * node + 1) + getSumUtil(st, mid + 1, high, L, R, 2 * node + 2); } // Recursive function to update the nodes // which have the given index in their range. static void updateValueUtil( int [] st, int low, int high, int i, int diff, int node) { // If the input index lies outside // the range of this segment if (i < low || i > high) return ; // If the input index is in range of this node, // then update the value of the node // and its children st[node] = st[node] + diff; if (high != low) { int mid = getMiddleValue(low, high); updateValueUtil(st, low, mid, i, diff, 2 * node + 1); updateValueUtil(st, mid + 1, high, i, diff, 2 * node + 2); } } // Function to update a value in input array // and segment tree. // It uses updateValueUtil() to update // the value in segment tree static void updateValue( int [] arr, int [] st, int n, int i, int new_val) { // Get the difference between new and old value int diff = new_val - arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0, n - 1, i, diff, 0); } // Return sum of elements in range from index L (query // start) to R (query end). It mainly uses getSumUtil() static int getSum( int [] st, int n, int L, int R) { return getSumUtil(st, 0, n - 1, L, R, 0); } // Recursive function that constructs Segment Tree // for array[low..high]. static int buildSegTreeUtil( int [] arr, int low, int high, int [] st, int node) { // If there is one element in array, // store it in current node of segment if (low == high) { st[node] = arr[low]; return arr[low]; } // If there are more than one elements, // then recur for left and right subtrees and // store the sum of values in this node int mid = getMiddleValue(low, high); st[node] = buildSegTreeUtil(arr, low, mid, st, node * 2 + 1) + buildSegTreeUtil(arr, mid + 1, high, st, node * 2 + 2); return st[node]; } // Function to construct segment tree from given array. // This function allocates memory for segment tree and // calls buildSegTreeUtil() to fill the allocated memory static int [] buildSegTree( int [] arr, int n) { // Height of segment tree int x = ( int )(Math.Ceiling(Math.Log(n) / Math.Log(2))); // Maximum size of segment tree int max_size = 2 * ( int )Math.Pow(2, x) - 1; // Allocate memory int [] st = new int [max_size]; // Fill the allocated memory st buildSegTreeUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } // Function to check if the subarray is permutation or not static void findPermutation( int [] arr, int N, int [,] Q, int M) { // Build segment tree from given array int [] st = buildSegTree(arr, N); // Traverse the given queries for ( int i = 0; i < M; i++) { // Query type for querying int queryType = Q[i,0]; // If query is of type 1 if (queryType == 1) { // Position and value for update int pos = Q[i,1], value = Q[i,2]; // Update: set arr[pos] = value and update // corresponding segment tree nodes updateValue(arr, st, N, pos, value); } else { // Stores range L to R for // type 2 query int L = Q[i,1], R = Q[i,2]; // Size variable stores size of // [L, R] range int size = R - L + 1; // Stores total from 1 to size of // range [L, R] int total_From_1_To_Size = size * (size + 1) / 2; // Print sum of values in array // from index L to R int total_From_L_To_R = getSum(st, N, L, R); // If total from 1 to size is equal // to total from L to R then print yes if (total_From_L_To_R == total_From_1_To_Size) { Console. WriteLine( "YES" ); } else { Console. WriteLine( "NO" ); } } } } public static void Main( string [] args) { int [] arr = { 6, 4, 1, 2, 3, 8, 10 }; int N = arr.Length; int [,] Q = { { 2, 2, 4 }, { 1, 2, 9 }, { 2, 2, 4 }, { 1, 2, 1 }, { 2, 0, 4 }, { 1, 0, 5 }, { 2, 0, 4 } }; int M = Q.GetLength(0); // Function call findPermutation(arr, N, Q, M); } } // This code is contributed by Aman Kumar |
Javascript
function getMiddleValue(low, high) { return low + Math.floor((high - low) / 2) } function getSumUtil(st, low, high, L, R, node) { if (L <= low && R >= high) { return st[node] } if (high < L || low > R) { return 0 } let mid = getMiddleValue(low, high) return getSumUtil(st, low, mid, L, R, 2 * node + 1) + getSumUtil(st, mid + 1, high, L, R, 2 * node + 2) } function updateValueUtil(st, low, high, i, diff, node) { if (i < low || i > high) { return } st[node] += diff if (high !== low) { let mid = getMiddleValue(low, high) updateValueUtil(st, low, mid, i, diff, 2 * node + 1) updateValueUtil(st, mid + 1, high, i, diff, 2 * node + 2) } } function updateValue(arr, st, n, i, newVal) { let diff = newVal - arr[i] arr[i] = newVal updateValueUtil(st, 0, n - 1, i, diff, 0) } function getSum(st, n, L, R) { return getSumUtil(st, 0, n - 1, L, R, 0) } function buildSegTreeUtil(arr, low, high, st, node) { if (low === high) { st[node] = arr[low] return arr[low] } let mid = getMiddleValue(low, high) st[node] = buildSegTreeUtil(arr, low, mid, st, node * 2 + 1) + buildSegTreeUtil(arr, mid + 1, high, st, node * 2 + 2) return st[node] } function buildSegTree(arr) { let n = arr.length let height = Math.ceil(Math.log2(n)) let maxSize = 2 * Math.pow(2, height) - 1 let st = new Array(maxSize).fill(0) buildSegTreeUtil(arr, 0, n - 1, st, 0) return st } function findPermutation(arr, N, Q, M) { let st = buildSegTree(arr); for (let i = 0; i < M; i++) { let queryType = Q[i][0]; if (queryType === 1) { let pos = Q[i][1], value = Q[i][2]; updateValue(arr, st, N, pos, value); } else { let L = Q[i][1], R = Q[i][2]; let size = R - L + 1; let total_From_1_To_Size = size * (size + 1) / 2; let total_From_L_To_R = getSum(st, N, L, R); if (total_From_L_To_R === total_From_1_To_Size) { console.log( "YES" ); } else { console.log( "NO" ); } } } } let arr = [6, 4, 1, 2, 3, 8, 10]; let N = arr.length; let Q = [[2, 2, 4], [1, 2, 9], [2, 2, 4], [1, 2, 1], [2, 0, 4], [1, 0, 5], [2, 0, 4]]; let M = Q.length; findPermutation(arr, N, Q, M); |
YES NO NO YES
Time complexity: O(N*logN + M*logN)
Auxiliary Space: O(N)
Related Articles:
Contact Us