Given an array arr[] consisting of N integers and two integer values L and R, indicating the starting and ending indices of a subarray, the task is to check if there exists a non-contiguous subsequence which is same as the given subarray or not. If found to be true, print “Yes”. Otherwise, print “No”.
A non-contiguous subsequence contains at least two consecutive characters from non-consecutive indices.
Examples:
Input: arr[] = {1, 7, 12, 1, 7, 5, 10, 11, 42}, L = 3, R = 6
Output: Yes
Explanation: The non-contiguous subsequence {arr[0], arr[1], arr[5], arr[6]} is same as the subarray {arr[3], .., arr[6]}.Input: arr[] = {0, 1, 2, -2, 5, 10}, L = 1, R = 3
Naive Approach: The simplest approach is to generate all possible subsequences of the given array and check if any subsequence generated is equal to the given subarray or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Time Complexity: O(N*2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the key observation that there will always be a non-contiguous subsequence if there is at least one occurrence of the first element of the given subarray in the range [0, L – 1] and at least one occurrence of the last element of a subarray in the range [R + 1, N].
Proof of Logic:
If the 1st element of the subarray {arr[L], … arr[R]} also occurs at any index K (K < L), then one such non-contiguous subsequence can be {arr[K], arr[L + 1], …., arr[R]}.
If the last element of the subarray {arr[L], … arr[R]} also occurs at any index K (K > R), then one such non-contiguous subsequence can be strong>{arr[L], arr[L + 1], …., arr[R – 1], arr[K]}.
If none of the above two conditions are satisfied, then no such non-contiguous subsequence exists.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Utility Function to check whether// a subsequence same as the given// subarray exists or notbool checkSubsequenceUtil( int arr[], int L, int R, int N){ // Check if first element of the // subarray is also present before for (int i = 0; i < L; i++) if (arr[i] == arr[L]) return true; // Check if last element of the // subarray is also present later for (int i = R + 1; i < N; i++) if (arr[i] == arr[R]) return true; // If above two conditions are // not satisfied, then no such // subsequence exists return false;}// Function to check and print if a// subsequence which is same as the// given subarray is present or notvoid checkSubsequence(int arr[], int L, int R, int N){ if (checkSubsequenceUtil(arr, L, R, N)) { cout << "YES\n"; } else { cout << "NO\n"; }}// Driver Codeint main(){ int arr[] = { 1, 7, 12, 1, 7, 5, 10, 11, 42 }; int N = sizeof(arr) / sizeof(arr[0]); int L = 3, R = 6; // Function Call checkSubsequence(arr, L, R, N);} |
Java
// Java program for the above approach class GFG{ // Utility Function to check whether// a subsequence same as the given// subarray exists or notstatic boolean checkSubsequenceUtil(int arr[], int L, int R, int N){ // Check if first element of the // subarray is also present before for(int i = 0; i < L; i++) if (arr[i] == arr[L]) return true; // Check if last element of the // subarray is also present later for(int i = R + 1; i < N; i++) if (arr[i] == arr[R]) return true; // If above two conditions are // not satisfied, then no such // subsequence exists return false;} // Function to check and print if a// subsequence which is same as the// given subarray is present or notstatic void checkSubsequence(int arr[], int L, int R, int N){ if (checkSubsequenceUtil(arr, L, R, N)) { System.out.print("YES\n"); } else { System.out.print("NO\n"); }} // Driver codepublic static void main(String[] args){ int arr[] = { 1, 7, 12, 1, 7, 5, 10, 11, 42 }; int N = arr.length; int L = 3, R = 6; // Function Call checkSubsequence(arr, L, R, N);}} // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Utility Function to check whether# a subsequence same as the given# subarray exists or notdef checkSubsequenceUtil(arr, L, R, N): # Check if first element of the # subarray is also present before for i in range(L): if (arr[i] == arr[L]): return True # Check if last element of the # subarray is also present later for i in range(R + 1, N, 1): if (arr[i] == arr[R]): return True # If above two conditions are # not satisfied, then no such # subsequence exists return False# Function to check and print if a# subsequence which is same as the# given subarray is present or notdef checkSubsequence(arr, L, R, N): if (checkSubsequenceUtil(arr, L,R, N)): print("YES") else: print("NO") # Driver Codearr = [ 1, 7, 12, 1, 7, 5, 10, 11, 42 ]N = len(arr) L = 3R = 6 # Function CallcheckSubsequence(arr, L, R, N)# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System;class GFG{ // Utility Function to check whether// a subsequence same as the given// subarray exists or notstatic bool checkSubsequenceUtil(int[] arr, int L, int R, int N){ // Check if first element of the // subarray is also present before for(int i = 0; i < L; i++) if (arr[i] == arr[L]) return true; // Check if last element of the // subarray is also present later for(int i = R + 1; i < N; i++) if (arr[i] == arr[R]) return true; // If above two conditions are // not satisfied, then no such // subsequence exists return false;} // Function to check and print if a// subsequence which is same as the// given subarray is present or notstatic void checkSubsequence(int[] arr, int L, int R, int N){ if (checkSubsequenceUtil(arr, L, R, N)) { Console.Write("YES\n"); } else { Console.Write("NO\n"); }} // Driver codepublic static void Main(){ int[] arr = { 1, 7, 12, 1, 7, 5, 10, 11, 42 }; int N = arr.Length; int L = 3, R = 6; // Function Call checkSubsequence(arr, L, R, N); }}// This code is contributed by code_hunt |
Javascript
<script>// javascript program to implement// the above approach// Utility Function to check whether// a subsequence same as the given// subarray exists or notfunction checkSubsequenceUtil(arr, L, R, N){ // Check if first element of the // subarray is also present before for(let i = 0; i < L; i++) if (arr[i] == arr[L]) return true; // Check if last element of the // subarray is also present later for(let i = R + 1; i < N; i++) if (arr[i] == arr[R]) return true; // If above two conditions are // not satisfied, then no such // subsequence exists return false;} // Function to check and print if a// subsequence which is same as the// given subarray is present or notfunction checkSubsequence(arr, L, R, N){ if (checkSubsequenceUtil(arr, L, R, N)) { document.write("YES\n"); } else { document.write("NO\n"); }}// Driver code let arr = [ 1, 7, 12, 1, 7, 5, 10, 11, 42 ]; let N = arr.length; let L = 3, R = 6; // Function Call checkSubsequence(arr, L, R, N); // This code is contributed by souravghosh0416.</script> |
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
