Given a binary array arr[] of size N and a 2D array Q[][] containing K queries of the following two types:
- 1 : Print the length of the longest subarray consisting of 1s only.
- 2 X : Flip the element at the Xth index (1-based indexing) i.e change the element to ‘1’ if the current element is ‘0’ and vice versa.
Examples:
Input: N = 10, arr[] = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1}, K=3, Q[][] = {{1}, {2, 3}, {1}}
Output: 3 6
Explanation:
Query 1: Length of the longest subarray of 1s only is 3.
Query 2: Flip the character ‘0’ at index 2 to ‘1’. Therefore, arr[] modifies to {1, 1, 1, 1, 1, 1, 0, 0, 1, 1}.
Query 3: Length of the longest subarray of 1s only is 6.Input: N = 7, arr[] = {1, 1, 1, 1, 1, 1, 0}, K=3, Q[][]={{1}, {2, 7}, {1}}
Output: 6 7
Explanation:
Query 1: Length of the longest subarray of 1s only is 6.
Query 2: Flip the character ‘0’ at position 7. Therefore, the array arr[] modifies to {1, 1, 1, 1, 1, 1, 1}.
Query 3: Length of the longest subarray of 1s only is 7.
Naive Approach: The simplest approach to solve the problem is to traverse the array arr[] for each query and perform the given operations.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the longest subarray// consisting of 1s onlyint longestsubarray(int a[], int N){ // Stores the maximum length of // subarray containing 1s only int maxlength = 0, sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is '1' if (a[i] == 1) { // Increment length sum++; } // Otherwise else { // Reset length sum = 0; } // Update maximum subarray length maxlength = max(maxlength, sum); } return maxlength;}// Function to perform given queriesvoid solveQueries(int arr[], int n, vector<vector<int> > Q, int k){ // Stores count of queries int cntQuery = Q.size(); // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { cout << longestsubarray(arr, n) << " "; } else { // Flip the character arr[Q[i][1] - 1] ^= 1; } }}// Driver Codeint main(){ // Size of array int N = 10; // Given array int arr[] = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } }; // Number of queries int K = 3; solveQueries(arr, N, Q, K);} |
Java
// Java Program for the above approach import java.util.*;public class Main{ // Function to calculate the longest subarray // consisting of 1s only static int longestsubarray(int a[], int N) { // Stores the maximum length of // subarray containing 1s only int maxlength = 0, sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is '1' if (a[i] == 1) { // Increment length sum++; } // Otherwise else { // Reset length sum = 0; } // Update maximum subarray length maxlength = Math.max(maxlength, sum); } return maxlength; } // Function to perform given queries static void solveQueries(int arr[], int n, Vector<Vector<Integer>> Q, int k) { // Stores count of queries int cntQuery = Q.size(); // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q.get(i).get(0) == 1) { System.out.print(longestsubarray(arr, n) + " "); } else { // Flip the character arr[Q.get(i).get(1) - 1] ^= 1; } } } public static void main(String[] args) { // Size of array int N = 10; // Given array int arr[] = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries Vector<Vector<Integer>> Q = new Vector<Vector<Integer>>(); Vector<Integer> v1 = new Vector<Integer>(); Vector<Integer> v2 = new Vector<Integer>(); Vector<Integer> v3 = new Vector<Integer>(); v1.add(1); v2.add(2); v2.add(3); v3.add(1); Q.add(v1); Q.add(v2); Q.add(v3); // Number of queries int K = 3; solveQueries(arr, N, Q, K); }}// This code is contributed by divyesh072019 |
Python3
# Python Program for the above approach# Function to calculate the longest subarray# consisting of 1s onlydef longestsubarray(a, N) : # Stores the maximum length of # subarray containing 1s only maxlength = 0 sum = 0 # Traverse the array for i in range(N): # If current element is '1' if (a[i] == 1) : # Increment length sum += 1 # Otherwise else : # Reset length sum = 0 # Update maximum subarray length maxlength = max(maxlength, sum) return maxlength# Function to perform given queriesdef solveQueries(arr, n, Q, k) : # Stores count of queries cntQuery = len(Q) # Traverse each query for i in range(cntQuery): if (Q[i][0] == 1) : print(longestsubarray(arr, n), end = " ") else : # Flip the character arr[Q[i][1] - 1] ^= 1 # Driver Code# Size of arrayN = 10# Given arrayarr = [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1] # Given queriesQ = [[1], [ 2, 3 ], [1]] # Number of queriesK = 3solveQueries(arr, N, Q, K)# This code is contributed by sanjoy_62 |
C#
// C# Program for the above approach using System;using System.Collections.Generic;class GFG { // Function to calculate the longest subarray // consisting of 1s only static int longestsubarray(int[] a, int N) { // Stores the maximum length of // subarray containing 1s only int maxlength = 0, sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is '1' if (a[i] == 1) { // Increment length sum++; } // Otherwise else { // Reset length sum = 0; } // Update maximum subarray length maxlength = Math.Max(maxlength, sum); } return maxlength; } // Function to perform given queries static void solveQueries(int[] arr, int n, List<List<int>> Q, int k) { // Stores count of queries int cntQuery = Q.Count; // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { Console.Write(longestsubarray(arr, n) + " "); } else { // Flip the character arr[Q[i][1] - 1] ^= 1; } } } // Driver code static void Main() { // Size of array int N = 10; // Given array int[] arr = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries List<List<int>> Q = new List<List<int>>(); Q.Add(new List<int> { 1 }); Q.Add(new List<int> { 2, 3 }); Q.Add(new List<int> { 1 }); // Number of queries int K = 3; solveQueries(arr, N, Q, K); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript Program for the above approach// Function to calculate the longest subarray// consisting of 1s onlyfunction longestsubarray(a, N){ // Stores the maximum length of // subarray containing 1s only var maxlength = 0, sum = 0; // Traverse the array for (var i = 0; i < N; i++) { // If current element is '1' if (a[i] == 1) { // Increment length sum++; } // Otherwise else { // Reset length sum = 0; } // Update maximum subarray length maxlength = Math.max(maxlength, sum); } return maxlength;}// Function to perform given queriesfunction solveQueries(arr, n, Q, k){ // Stores count of queries var cntQuery = Q.length; // Traverse each query for (var i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { document.write( longestsubarray(arr, n) + " "); } else { // Flip the character arr[Q[i][1] - 1] ^= 1; } }}// Driver Code// Size of arrayvar N = 10;// Given arrayvar arr = [1, 1, 0, 1, 1, 1, 0, 0, 1, 1 ];// Given queriesvar Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];// Number of queriesvar K = 3;solveQueries(arr, N, Q, K);</script> |
Output:
3 6
Time Complexity: (N * K)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using Segment Tree data structure. The given problem can be solved based on the following observations:
- It can be easily observed that one need at least three things for merging two nodes of a Segment Tree. Therefore, 3 segment trees are required, say MAX[], pref[], and suf[]. MAX[]: Stores the length of the longest subarray consisting only of 1s, pre[] and suf[] will store the longest length of prefix and suffix respectively.
- Merging of two nodes can be done using the following:
- MAX[i] = max(MAX[2*i], max(MAX[2*i + 1], suf[2*v + 1] + pref[2*i]))
- pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm – tl + 1) * pref[v * 2 + 1])
- suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == tr – tm))
- Here i, 2*i, 2*i + 1 are the current node, left child and right child respectively, and tl, tr is the current range
Follow the steps below to solve the problem:
- For the query of type 1, print the root node, MAX[1] of the segment tree which contains the longest length of subarray consisting of only 1’s only in the range [1, N]
- For the query of type 2, Flip the given position and update the segment tree.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;#define INF 1000000// Arrays to store prefix sums, suffix// and MAX's node respectivelyint pref[500005];int suf[500005];int MAX[500005];// Function to construct Segment Treevoid build(int a[], int tl, int tr, int v){ if (tl == tr) { // MAX array for node MAX MAX[v] = a[tl]; // Array for prefix sum node pref[v] = a[tl]; // Array for suffix sum node suf[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(a, tl, tm, v * 2); build(a, tm + 1, tr, v * 2 + 1); // Calculate MAX node MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]); suf[v] = max( suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == tr - tm)); }}// Function to update Segment Treevoid update(int a[], int pos, int tl, int tr, int v){ if (tl > pos || tr < pos) { return; } // Update at position if (tl == tr && tl == pos) { MAX[v] = a[pos]; pref[v] = a[pos]; suf[v] = a[pos]; } else { // Update sums from bottom to the // top of Segment Tree int tm = (tl + tr) / 2; update(a, pos, tl, tm, v * 2); update(a, pos, tm + 1, tr, v * 2 + 1); // Update MAX tree MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); // Update pref tree pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]); // Update suf tree suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == tr - tm) * suf[v * 2]); }}// Function to perform given queriesvoid solveQueries(int arr[], int n, vector<vector<int> > Q, int k){ // Stores count of queries int cntQuery = Q.size(); build(arr, 0, n - 1, 1); // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { // Print longest length of subarray in [1, N] cout << MAX[1] << " "; } else { // Flip the character arr[Q[i][1] - 1] ^= 1; update(arr, Q[i][1] - 1, 0, n - 1, 1); } }}// Driver Codeint main(){ // Size of array int N = 10; // Given array int arr[] = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } }; // Number of queries int K = 3; solveQueries(arr, N, Q, K);} |
Java
// Java Program for the above approachimport java.util.*;class GFG{static final int INF = 1000000;// Arrays to store prefix sums, suffix// and MAX's node respectivelystatic int []pref = new int[500005];static int []suf = new int[500005];static int []MAX = new int[500005];// Function to construct Segment Treestatic void build(int a[], int tl, int tr, int v){ if (tl == tr) { // MAX array for node MAX MAX[v] = a[tl]; // Array for prefix sum node pref[v] = a[tl]; // Array for suffix sum node suf[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(a, tl, tm, v * 2); build(a, tm + 1, tr, v * 2 + 1); // Calculate MAX node MAX[v] = Math.max(MAX[v * 2], Math.max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); pref[v] = Math.max(pref[v * 2], pref[2 * v] + (pref[2 * v] == (tm - tl + 1)?1:0) * pref[v * 2 + 1]); suf[v] = Math.max( suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0)); }}// Function to update Segment Treestatic void update(int a[], int pos, int tl, int tr, int v){ if (tl > pos || tr < pos) { return; } // Update at position if (tl == tr && tl == pos) { MAX[v] = a[pos]; pref[v] = a[pos]; suf[v] = a[pos]; } else { // Update sums from bottom to the // top of Segment Tree int tm = (tl + tr) / 2; update(a, pos, tl, tm, v * 2); update(a, pos, tm + 1, tr, v * 2 + 1); // Update MAX tree MAX[v] = Math.max(MAX[v * 2], Math.max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); // Update pref tree pref[v] = Math.max(pref[v * 2], pref[2 * v] + (pref[2 * v] == (tm - tl + 1)?1:0) * pref[v * 2 + 1]); // Update suf tree suf[v] = Math.max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == (tr - tm)?1:0) * suf[v * 2]); }}// Function to perform given queriesstatic void solveQueries(int arr[], int n, int[][] Q, int k){ // Stores count of queries int cntQuery = Q.length; build(arr, 0, n - 1, 1); // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { // Print longest length of subarray in [1, N] System.out.print(MAX[1]+ " "); } else { // Flip the character arr[Q[i][1] - 1] ^= 1; update(arr, Q[i][1] - 1, 0, n - 1, 1); } }}// Driver Codepublic static void main(String[] args){ // Size of array int N = 10; // Given array int arr[] = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries int [][]Q = { { 1 }, { 2, 3 }, { 1 } }; // Number of queries int K = 3; solveQueries(arr, N, Q, K);}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 Program for the above approachINF = 1000000# Arrays to store prefix sums, suffix# and MAX's node respectivelypref = [0 for i in range(500005)]suf = [0 for i in range(500005)]MAX = [0 for i in range(500005)]# Function to construct Segment Treedef build(a, tl,tr,v): global MAX global pref global suf if (tl == tr): # MAX array for node MAX MAX[v] = a[tl] # Array for prefix sum node pref[v] = a[tl] # Array for suffix sum node suf[v] = a[tl] else: tm = (tl + tr) // 2 build(a, tl, tm, v * 2) build(a, tm + 1, tr, v * 2 + 1) # Calculate MAX node MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])) pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1)* pref[v * 2 + 1]) suf[v] = max(suf[v * 2 + 1],suf[2 * v + 1]+suf[v * 2] * (suf[2 * v + 1] == tr - tm))# Function to update Segment Treedef update(a,pos,tl,tr,v): global pref global suf global MAX if (tl > pos or tr < pos): return # Update at position if (tl == tr and tl == pos): MAX[v] = a[pos] pref[v] = a[pos] suf[v] = a[pos] else: # Update sums from bottom to the # top of Segment Tree tm = (tl + tr) // 2 update(a, pos, tl, tm, v * 2) update(a, pos, tm + 1, tr, v * 2 + 1) # Update MAX tree MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])) # Update pref tree pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]) # Update suf tree suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == tr - tm) * suf[v * 2])# Function to perform given queriesdef solveQueries(arr, n, Q, k): global MAX # Stores count of queries cntQuery = len(Q) build(arr, 0, n - 1, 1) # Traverse each query for i in range(cntQuery): if (Q[i][0] == 1): # Print longest length of subarray in [1, N] print(MAX[1],end = " ") else: # Flip the character arr[Q[i][1] - 1] ^= 1 update(arr, Q[i][1] - 1, 0, n - 1, 1)# Driver Codeif __name__ == '__main__': # Size of array N = 10 # Given array arr = [1, 1, 0, 1, 1, 1, 0, 0, 1, 1] # Given queries Q = [[1], [2, 3], [1]] # Number of queries K = 3 solveQueries(arr, N, Q, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# Program for the above approachusing System;class GFG{ static readonly int INF = 1000000;// Arrays to store prefix sums, suffix// and MAX's node respectivelystatic int []pref = new int[500005];static int []suf = new int[500005];static int []MAX = new int[500005];// Function to construct Segment Treestatic void build(int []a, int tl, int tr, int v){ if (tl == tr) { // MAX array for node MAX MAX[v] = a[tl]; // Array for prefix sum node pref[v] = a[tl]; // Array for suffix sum node suf[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(a, tl, tm, v * 2); build(a, tm + 1, tr, v * 2 + 1); // Calculate MAX node MAX[v] = Math.Max(MAX[v * 2], Math.Max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); pref[v] = Math.Max(pref[v * 2], pref[2 * v] + (pref[2 * v] == (tm - tl + 1)?1:0) * pref[v * 2 + 1]); suf[v] = Math.Max( suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0)); }}// Function to update Segment Treestatic void update(int []a, int pos, int tl, int tr, int v){ if (tl > pos || tr < pos) { return; } // Update at position if (tl == tr && tl == pos) { MAX[v] = a[pos]; pref[v] = a[pos]; suf[v] = a[pos]; } else { // Update sums from bottom to the // top of Segment Tree int tm = (tl + tr) / 2; update(a, pos, tl, tm, v * 2); update(a, pos, tm + 1, tr, v * 2 + 1); // Update MAX tree MAX[v] = Math.Max(MAX[v * 2], Math.Max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); // Update pref tree pref[v] = Math.Max(pref[v * 2], pref[2 * v] + (pref[2 * v] == (tm - tl + 1)?1:0) * pref[v * 2 + 1]); // Update suf tree suf[v] = Math.Max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == (tr - tm)?1:0) * suf[v * 2]); }}// Function to perform given queriesstatic void solveQueries(int []arr, int n, int[,] Q, int k){ // Stores count of queries int cntQuery = Q.GetLength(0); build(arr, 0, n - 1, 1); // Traverse each query for (int i = 0; i < cntQuery; i++) { if (Q[i, 0] == 1) { // Print longest length of subarray in [1, N] Console.Write(MAX[1] + " "); } else { // Flip the character arr[Q[i, 1] - 1] ^= 1; update(arr, Q[i, 1] - 1, 0, n - 1, 1); } }}// Driver Codepublic static void Main(String[] args){ // Size of array int N = 10; // Given array int []arr = { 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 }; // Given queries int [,]Q = { { 1,0 }, { 2, 3 }, { 1,0 } }; // Number of queries int K = 3; solveQueries(arr, N, Q, K);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript Program for the above approachlet INF = 1000000// Arrays to store prefix sums, suffix// and MAX's node respectivelylet pref = new Array(500005);let suf = new Array(500005);let MAX = new Array(500005);// Function to construct Segment Treefunction build(a, tl, tr, v){ if (tl == tr) { // MAX array for node MAX MAX[v] = a[tl]; // Array for prefix sum node pref[v] = a[tl]; // Array for suffix sum node suf[v] = a[tl]; } else { let tm = Math.floor((tl + tr) / 2); build(a, tl, tm, v * 2); build(a, tm + 1, tr, v * 2 + 1); // Calculate MAX node MAX[v] = Math.max(MAX[v * 2], Math.max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); pref[v] = Math.max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]); suf[v] = Math.max( suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == tr - tm)); }}// Function to update Segment Treefunction update(a, pos, tl,tr, v){ if (tl > pos || tr < pos) { return; } // Update at position if (tl == tr && tl == pos) { MAX[v] = a[pos]; pref[v] = a[pos]; suf[v] = a[pos]; } else { // Update sums from bottom to the // top of Segment Tree let tm = Math.floor((tl + tr) / 2); update(a, pos, tl, tm, v * 2); update(a, pos, tm + 1, tr, v * 2 + 1); // Update MAX tree MAX[v] = Math.max(MAX[v * 2], Math.max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])); // Update pref tree pref[v] = Math.max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]); // Update suf tree suf[v] = Math.max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == tr - tm) * suf[v * 2]); }}// Function to perform given queriesfunction solveQueries(arr, n, Q, k){ // Stores count of queries let cntQuery = Q.length; build(arr, 0, n - 1, 1); // Traverse each query for (let i = 0; i < cntQuery; i++) { if (Q[i][0] == 1) { // Print longest length of subarray in [1, N] document.write(MAX[1] + " "); } else { // Flip the character arr[Q[i][1] - 1] ^= 1; update(arr, Q[i][1] - 1, 0, n - 1, 1); } }}// Driver Code// Size of arraylet N = 10;// Given arraylet arr = [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 ];// Given querieslet Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];// Number of querieslet K = 3;solveQueries(arr, N, Q, K);// This code is contributed by shinjanpatra</script> |
Output:
3 6
Time Complexity: O(max(K*log(N), N*log(N)))
Auxiliary Space: O(4*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!
