Given an array arr[] consisting of N integers and an array Queries[][] with each query of the form {x, y}. For each query, the task is to replace the element at index x ( 1-based indexing ) by y and find the length of the longest subsequence having no similar adjacent elements.
Examples:
Input: arr[] = {1, 1, 2, 5, 2}, Q = 2, Queries[][] = {{1, 3}, {4, 2}}
Output: 5 3
Explanation:
Initially the array is {1, 1, 2, 5, 2}.
Query 1: Modifying the value at index 1 to 3, the array modifies to {3, 1, 2, 5, 2}.
Therefore, the longest subsequence having no similar adjacent elements is {3, 1, 2, 5, 2}, which is of length 5.
Therefore, print 5 as the answer.
Query 2: Modifying the value at index 4 to 2, the array modifies to {3, 1, 2, 2, 2}.
Now Therefore, the longest subsequence having no similar adjacent elements is {3, 1, 2}, which is of length 3.
Therefore, print 2 as the answer.Input: arr[] = {1, 1, 2, 5, 2}, Q = 1, Queries[][] = {{2, 2}}
Output: 4
Explanation:
Initially the array is {1, 1, 2, 5, 2}.
Query 1: Modifying the value at index 2 to 2, the array modified to {1, 2, 2, 5, 2}.
Therefore, the longest subsequence having no similar adjacent elements is {1, 2, 5, 2}, which is of length 4.
Therefore, print the value as 4.
Naive Approach: Follow the steps below to solve the problem using the simplest possible approach:
- Add the element to the subsequence only if it is not equal to the previous element of the subsequence.
- For each query {x, y}, replace the element at index x with y.
- Keep track of the longest subsequence found at any point by a variable count.
- Traverse through the array and increment count variable by 1 whenever the current element of the sequence is not equal to the previous element of the sequence.
- After iterating the sequence once, count contains the length of longest required subsequence.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subsequence such that no// two adjacent elements are equalvoid longestSubsequence(int N, int Q, int arr[], int Queries[][2]){ for (int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i][0]; int y = Queries[i][1]; // Since x is 1-indexed, // decrement x by 1 arr[x - 1] = y; // Keep track of number of // elements in subsequence int count = 1; for (int j = 1; j < N; j++) { // If previous element is not // same as current element if (arr[j] != arr[j - 1]) { count += 1; } } // Print the desired count cout << count << ' '; }}// Driver Codeint main(){ int arr[] = { 1, 1, 2, 5, 2 }; int N = sizeof(arr) / sizeof(arr[0]); int Q = 2; int Queries[Q][2] = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the length of the// longest subsequence such that no// two adjacent elements are equalstatic void longestSubsequence(int N, int Q, int arr[], int Queries[][]){ for (int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i][0]; int y = Queries[i][1]; // Since x is 1-indexed, // decrement x by 1 arr[x - 1] = y; // Keep track of number of // elements in subsequence int count = 1; for (int j = 1; j < N; j++) { // If previous element is not // same as current element if (arr[j] != arr[j - 1]) { count += 1; } } // Print the desired count System.out.print(count +" "); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 1, 2, 5, 2 }; int N = arr.length; int Q = 2; int Queries[][] = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach# Function to find the length of the# longest subsequence such that no# two adjacent elements are equaldef longestSubsequence(N, Q, arr, Queries): for i in range(Q): # Replace element at # index x with y x = Queries[i][0] y = Queries[i][1] # Since x is 1-indexed, # decrement x by 1 arr[x - 1] = y # Keep track of number of # elements in subsequence count = 1 for j in range(1, N): # If previous element is not # same as current element if (arr[j] != arr[j - 1]): count += 1 # Print the desired count print(count, end = ' ')# Driver Codeif __name__ == "__main__": arr = [ 1, 1, 2, 5, 2 ] N = len(arr) Q = 2 Queries = [ [ 1, 3 ], [ 4, 2 ] ] # Function Call longestSubsequence(N, Q, arr, Queries)# This code is contributed by chitranayal |
C#
// C# program for // the above approachusing System; using System.Collections.Generic; class GFG{// Function to find the length of the// longest subsequence such that no// two adjacent elements are equalstatic void longestSubsequence(int N, int Q, int []arr, int [,]Queries){ for(int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i, 0]; int y = Queries[i, 1]; // Since x is 1-indexed, // decrement x by 1 arr[x - 1] = y; // Keep track of number of // elements in subsequence int count = 1; for(int j = 1; j < N; j++) { // If previous element is not // same as current element if (arr[j] != arr[j - 1]) { count += 1; } } // Print the desired count Console.Write(count +" "); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 1, 2, 5, 2 }; int N = arr.Length; int Q = 2; int[,]Queries = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries);}}// This code is contributed by jana_sayantan |
Javascript
<script>// JavaScript implementation of the above approach// Function to find the length of the// longest subsequence such that no// two adjacent elements are equalfunction longestSubsequence(N, Q, arr, Queries){ for (let i = 0; i < Q; i++) { // Replace element at // index x with y let x = Queries[i][0]; let y = Queries[i][1]; // Since x is 1-indexed, // decrement x by 1 arr[x - 1] = y; // Keep track of number of // elements in subsequence let count = 1; for (let j = 1; j < N; j++) { // If previous element is not // same as current element if (arr[j] != arr[j - 1]) { count += 1; } } // Print the desired count document.write(count +" "); }}// Driver code let arr = [ 1, 1, 2, 5, 2 ]; let N = arr.length; let Q = 2; let Queries = [[ 1, 3 ], [ 4, 2 ]]; // Function Call longestSubsequence(N, Q, arr, Queries); // This code is contributed by code_hunt.</script> |
Output:
5 3
Time Complexity: O(N*Q)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, an observation is found that the presence of an element in the required subsequence only depends on its previous element as shown below:
- Replacing the element at index x will only affect the contribution of elements at indices x and x + 1, in the final answer.
- Therefore, subtracting the contributions of these 2 indices from the variable count and recalculating contributions of these 2 indices will give the required answer in constant time.
Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the count of subsequences.
- Traverse the given array and count those elements that are different from the previous element of the array and store it in a variable count.
- Now traverse each query {x, y} and perform the following:
- If the element at index (x – 1) is different from the element at index x, then decrement count by 1.
- If the element at index (x – 1) is different from the element y, then increment count by 1.
- Similarly, if the element at index (x + 1) is different from the element at index x, then decrement count by 1.
- If the element at index (x + 1) is different from the element y, then increment count by 1.
- Print the value of count after each query as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;void longestSubsequence(int N, int Q, int arr[], int Queries[][2]){ int count = 1; // Traverse the array arr[] for (int i = 1; i < N; i++) { // If previous element is not // same as current element if (arr[i] != arr[i - 1]) { count += 1; } } // Traverse the queries for (int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i][0]; int y = Queries[i][1]; // Recalculate for index x if (x > 1) { // Subtract contribution // of element at index x if (arr[x - 1] != arr[x - 2]) { count -= 1; } // Add contribution of y if (arr[x - 2] != y) { count += 1; } } // Recalculate for index x + 1 if (x < N) { // Subtract contribution of // element at index x + 1 if (arr[x] != arr[x - 1]) { count -= 1; } // Adds contribution of y if (y != arr[x]) { count += 1; } } cout << count << ' '; // Replace the element arr[x - 1] = y; }}// Driver Codeint main(){ int arr[] = { 1, 1, 2, 5, 2 }; int N = sizeof(arr) / sizeof(arr[0]); int Q = 2; int Queries[Q][2] = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static void longestSubsequence(int N, int Q, int arr[], int Queries[][]){ int count = 1; // Traverse the array arr[] for(int i = 1; i < N; i++) { // If previous element is not // same as current element if (arr[i] != arr[i - 1]) { count += 1; } } // Traverse the queries for(int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i][0]; int y = Queries[i][1]; // Recalculate for index x if (x > 1) { // Subtract contribution // of element at index x if (arr[x - 1] != arr[x - 2]) { count -= 1; } // Add contribution of y if (arr[x - 2] != y) { count += 1; } } // Recalculate for index x + 1 if (x < N) { // Subtract contribution of // element at index x + 1 if (arr[x] != arr[x - 1]) { count -= 1; } // Adds contribution of y if (y != arr[x]) { count += 1; } } System.out.print(count + " "); // Replace the element arr[x - 1] = y; }}// Driver Codepublic static void main(String args[]){ int arr[] = { 1, 1, 2, 5, 2 }; int N = arr.length; int Q = 2; int Queries[][] = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries);}}// This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approachdef longestSubsequence(N, Q, arr, Queries): count = 1 # Traverse the array arr[] for i in range(1, N): # If previous element is not # same as current element if (arr[i] != arr[i - 1]): count += 1 # Traverse the queries for i in range(Q): # Replace element at # index x with y x = Queries[i][0] y = Queries[i][1] # Recalculate for index x if (x > 1): # Subtract contribution # of element at index x if (arr[x - 1] != arr[x - 2]): count -= 1 # Add contribution of y if (arr[x - 2] != y): count += 1 # Recalculate for index x + 1 if (x < N): # Subtract contribution of # element at index x + 1 if (arr[x] != arr[x - 1]): count -= 1 # Adds contribution of y if (y != arr[x]): count += 1 print(count, end = ' ') # Replace the element arr[x - 1] = y# Driver Codeif __name__ == "__main__" : arr = [ 1, 1, 2, 5, 2 ] N = len(arr) Q = 2 Queries = [ [ 1, 3 ], [ 4, 2 ] ] # Function Call longestSubsequence(N, Q, arr, Queries)# This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{ static void longestSubsequence(int N, int Q, int []arr, int [,]Queries){ int count = 1; // Traverse the array arr[] for(int i = 1; i < N; i++) { // If previous element is not // same as current element if (arr[i] != arr[i - 1]) { count += 1; } } // Traverse the queries for(int i = 0; i < Q; i++) { // Replace element at // index x with y int x = Queries[i, 0]; int y = Queries[i, 1]; // Recalculate for index x if (x > 1) { // Subtract contribution // of element at index x if (arr[x - 1] != arr[x - 2]) { count -= 1; } // Add contribution of y if (arr[x - 2] != y) { count += 1; } } // Recalculate for index x + 1 if (x < N) { // Subtract contribution of // element at index x + 1 if (arr[x] != arr[x - 1]) { count -= 1; } // Adds contribution of y if (y != arr[x]) { count += 1; } } Console.Write(count + " "); // Replace the element arr[x - 1] = y; }}// Driver Codepublic static void Main(string []args){ int []arr = { 1, 1, 2, 5, 2 }; int N = arr.Length; int Q = 2; int [,]Queries = { { 1, 3 }, { 4, 2 } }; // Function Call longestSubsequence(N, Q, arr, Queries);}}// This code is contributed by AnkThon |
Javascript
<script>// javascript program for the above approach function longestSubsequence( N , Q , arr , Queries) { var count = 1; // Traverse the array arr for (var i = 1; i < N; i++) { // If previous element is not // same as current element if (arr[i] != arr[i - 1]) { count += 1; } } // Traverse the queries for (var i = 0; i < Q; i++) { // Replace element at // index x with y var x = Queries[i][0]; var y = Queries[i][1]; // Recalculate for index x if (x > 1) { // Subtract contribution // of element at index x if (arr[x - 1] != arr[x - 2]) { count -= 1; } // Add contribution of y if (arr[x - 2] != y) { count += 1; } } // Recalculate for index x + 1 if (x < N) { // Subtract contribution of // element at index x + 1 if (arr[x] != arr[x - 1]) { count -= 1; } // Adds contribution of y if (y != arr[x]) { count += 1; } } document.write(count + " "); // Replace the element arr[x - 1] = y; } } // Driver Code var arr = [ 1, 1, 2, 5, 2 ]; var N = arr.length; var Q = 2; var Queries = [ [ 1, 3 ], [ 4, 2 ] ]; // Function Call longestSubsequence(N, Q, arr, Queries);// This code contributed by Princi Singh</script> |
Output:
5 3
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!
