Given a binary array arr[] of size N, the task is to check if the array arr[] can be made sorted by removing any subsequence of non-adjacent array elements. If the array can be made sorted, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {1, 0, 1, 0, 1, 1, 0}
Output: Yes
Explanation:
Remove the element at indices {1, 3, 6} modifies the given array to {1, 1, 1, 1}, which is sorted. Therefore, print Yes.Input: arr[] = {0, 1, 1, 0, 0}
Output: No
Naive Approach: The simplest approach to solve the given problem is to generate all possible subsequences of non-adjacent elements and if there exists any subsequence whose removal sorts the given array, then print “Yes”. Otherwise, print “No”.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized based on the observation that the array can’t be sorted if and only if when there exists two consecutive 1s are present at adjacent indexes i and i + 1 and two consecutive 0s are present at adjacent indexes j and j + 1 such that (j > i). Follow the steps below to solve the problem:
- Initialize a variable, say idx as -1 that stores the index if there are two consecutive 1s in the array.
- Traverse the given array and if there exists any two consecutive 1s are present in the array then store that index in the variable idx and break out of the loop. Otherwise, removing all the 1s from the array and make the array sorted, and print “Yes”.
- If the value of idx is “-1”, then print “Yes” as always removing all the 1s from the array makes the array sorted.
- Otherwise, traverse the array again from the index idx and if there exist two consecutive 0s, then print and break out of the loop. Otherwise, removing all the 0s from the array and make the array sorted, and print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to sort the array or notvoid isPossibleToSort(int arr[], int N){ // Stores the index if there are two // consecutive 1's in the array int idx = -1; // Traverse the given array for (int i = 1; i < N; i++) { // Check adjacent same elements // having values 1s if (arr[i] == 1 && arr[i - 1] == 1) { idx = i; break; } } // If there are no two consecutive // 1s, then always remove all the // 1s from array & make it sorted if (idx == -1) { cout << "YES"; return; } for (int i = idx + 1; i < N; i++) { // If two consecutive 0's are // present after two consecutive // 1's then array can't be sorted if (arr[i] == 0 && arr[i - 1] == 0) { cout << "NO"; return; } } // Otherwise, print Yes cout << "YES";}// Driver Codeint main(){ int arr[] = { 1, 0, 1, 0, 1, 1, 0 }; int N = sizeof(arr) / sizeof(arr[0]); isPossibleToSort(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to check if it is possible // to sort the array or not static void isPossibleToSort(int arr[], int N) { // Stores the index if there are two // consecutive 1's in the array int idx = -1; // Traverse the given array for (int i = 1; i < N; i++) { // Check adjacent same elements // having values 1s if (arr[i] == 1 && arr[i - 1] == 1) { idx = i; break; } } // If there are no two consecutive // 1s, then always remove all the // 1s from array & make it sorted if (idx == -1) { System.out.println("YES"); return; } for (int i = idx + 1; i < N; i++) { // If two consecutive 0's are // present after two consecutive // 1's then array can't be sorted if (arr[i] == 0 && arr[i - 1] == 0) { System.out.println("NO"); return; } } // Otherwise, print Yes System.out.println("YES"); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 0, 1, 0, 1, 1, 0 }; int N = arr.length; isPossibleToSort(arr, N); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to check if it is possible# to sort the array or notdef isPossibleToSort(arr, N): # Stores the index if there are two # consecutive 1's in the array idx = -1 # Traverse the given array for i in range(1, N): # Check adjacent same elements # having values 1s if (arr[i] == 1 and arr[i - 1] == 1): idx = i break # If there are no two consecutive # 1s, then always remove all the # 1s from array & make it sorted if (idx == -1): print("YES") return for i in range(idx + 1, N, 1): # If two consecutive 0's are # present after two consecutive # 1's then array can't be sorted if (arr[i] == 0 and arr[i - 1] == 0): print("NO") return # Otherwise, print Yes print("YES")# Driver Codeif __name__ == '__main__': arr = [ 1, 0, 1, 0, 1, 1, 0 ] N = len(arr) isPossibleToSort(arr, N)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# for the above approachusing System.IO;using System;class GFG{ // Function to check if it is possible// to sort the array or notstatic void isPossibleToSort(int[] arr, int N){ // Stores the index if there are two // consecutive 1's in the array int idx = -1; // Traverse the given array for(int i = 1; i < N; i++) { // Check adjacent same elements // having values 1s if (arr[i] == 1 && arr[i - 1] == 1) { idx = i; break; } } // If there are no two consecutive // 1s, then always remove all the // 1s from array & make it sorted if (idx == -1) { Console.WriteLine("YES"); return; } for(int i = idx + 1; i < N; i++) { // If two consecutive 0's are // present after two consecutive // 1's then array can't be sorted if (arr[i] == 0 && arr[i - 1] == 0) { Console.WriteLine("NO"); return; } } // Otherwise, print Yes Console.WriteLine("YES");}// Driver codestatic void Main(){ int[] arr = { 1, 0, 1, 0, 1, 1, 0 }; int N = arr.Length; isPossibleToSort(arr, N);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// JavaScript program for the above approach// Function to check if it is possible// to sort the array or notfunction isPossibleToSort(arr, N){ // Stores the index if there are two // consecutive 1's in the array var idx = -1; var i; // Traverse the given array for (i = 1; i < N; i++) { // Check adjacent same elements // having values 1s if (arr[i] == 1 && arr[i - 1] == 1) { idx = i; break; } } // If there are no two consecutive // 1s, then always remove all the // 1s from array & make it sorted if (idx == -1) { document.write("YES"); return; } for (i = idx + 1; i < N; i++) { // If two consecutive 0's are // present after two consecutive // 1's then array can't be sorted if (arr[i] == 0 && arr[i - 1] == 0) { document.write("NO"); return; } } // Otherwise, print Yes document.write("YES");}// Driver Code var arr = [1, 0, 1, 0, 1, 1, 0]; var N = arr.length; isPossibleToSort(arr, N);</script> |
Output:
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
