Sort an array by swapping adjacent elements from indices that contains ‘1’ in a given string
Given an array arr[] of size N and a binary string S, the task is to check if it is possible to sort the array arr[] by swapping adjacent array elements, say arr[i] and arr[i + 1] if S[i] is equal to ‘1’. If it is possible, then print “Yes”. Otherwise, print “No”.
Examples :
Input: N = 6, arr[] = {2, 5, 3, 4, 6}, S = “01110”
Output: Yes
Explanation:
Indices that can be swapped are {1, 2, 3}.
Swapping arr[1] and arr[2] modifies the array arr[] to {1, 2, 3, 5, 4, 6}.
Swapping arr[3] and arr[4] modifies the array arr[] to {1, 2, 3, 4, 5, 6}.Input : N = 6, arr[] = {1, 2, 5, 3, 4, 6}, S = “01010”
Output : No
Approach: Take a look at some pair (i, ?j) in the array arr[] such that i?<?j and initial arr[i]?>?arr[j]. That means that all the swaps from i to j?-?1 should be allowed. Then it’s easy to notice that it’s enough to check only i and i?+?1 as any other pair can be deducted from this. Follow the steps below to solve the problem:
- Iterate over the range [0, N – 1] and perform the following steps:
- If S[i] is ‘1’, then initialize a variable, say j, as equal to i.
- Iterate over the range till s[j] is equal to ‘1′ and j is less than the length of the string s. Increase the value of j by 1.
- Sort the subarray in the array arr[] from i to j+1.
- Iterate over the range [0, N – 2] and perform the following steps:
- If the value of arr[i] is greater than arr[i + 1], then print No and break the loop and return.
- Print Yes as the array is sorted by swapping the allowed indices.
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 arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s void checkIfPossibleToSort( int n, int arr[], string s) { // Sort the parts of array // where swaps are allowed for ( int i = 0; i < n - 1; i++) { if (s[i] == '1' ) { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == '1' ) { j++; } // Sort the subarray sort(arr + i, arr + j + 1); i = j; } } // Check if the array remains unsorted for ( int i = 0; i < n - 1; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { printf ( "No\n" ); return ; } } printf ( "Yes\n" ); } // Driver Code int main() { // Given Input int n = 6; int arr[] = { 2, 5, 3, 4, 6 }; string s = "01110" ; // Function Call checkIfPossibleToSort(n, arr, s); return 0; } |
Java
// Java program for the above approach import java.util.Arrays; class GFG{ // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s public static void checkIfPossibleToSort( int n, int arr[], String s) { // Sort the parts of array // where swaps are allowed for ( int i = 0 ; i < n - 1 ; i++) { if (s.charAt(i) == '1' ) { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s.charAt(j) == '1' ) { j++; } // Sort the subarray Arrays.sort(arr, i, j); i = j; } } // Check if the array remains unsorted for ( int i = 0 ; i < n - 2 ; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1 ]) { System.out.println( "No" ); return ; } } System.out.println( "Yes" ); } // Driver Code public static void main(String args[]) { // Given Input int n = 6 ; int arr[] = { 2 , 5 , 3 , 4 , 6 }; String s = "01110" ; // Function Call checkIfPossibleToSort(n, arr, s); } } // This code is contributed by gfgking |
Python3
# Python3 program for the above approach # Function to check if it is possible # to sort the array arr[] by swapping # array elements from indices containing # adjacent pairs of 1s in the string s def checkIfPossibleToSort(n, arr, s): # Sort the parts of array # where swaps are allowed for i in range (n - 1 ): if s[i] = = '1' : j = i # Iterate over the range # till s[j] is equal to '1' while s[j] = = '1' : j + = 1 # sort the array arr = arr[:i] + sorted (arr[i:j + 1 ]) + arr[j + 1 :] i = j # Check if the array remains unsorted for i in range (n - 2 ): # If found to be true, then it is # not possible to sort the array if arr[i] > arr[i + 1 ]: print ( "No" ) return print ( "Yes" ) # Driver code # Given input n = 6 arr = [ 2 , 5 , 3 , 4 , 6 ] s = "01110" # function call checkIfPossibleToSort(n, arr, s) # This code is contributed by Parth Manchanda |
C#
// C# program for the above approach using System; class GFG{ // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s public static void checkIfPossibleToSort( int n, int []arr, String s) { // Sort the parts of array // where swaps are allowed for ( int i = 0; i < n - 1; i++) { if (s[i] == '1' ) { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == '1' ) { j++; } // Sort the subarray Array.Sort(arr, i, j); i = j; } } // Check if the array remains unsorted for ( int i = 0; i < n - 2; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { Console.Write( "No" ); return ; } } Console.Write( "Yes" ); } // Driver Code public static void Main(String []args) { // Given Input int n = 6; int []arr = { 2, 5, 3, 4, 6 }; String s = "01110" ; // Function Call checkIfPossibleToSort(n, arr, s); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for the above approach // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s function checkIfPossibleToSort(n, arr, s) { // Sort the parts of array // where swaps are allowed for (let i = 0; i < n - 1; i++) { if (s[i] == "1" ) { let j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == "1" ) { j++; } // Sort the subarray arr = [ ...arr.slice(0, i), ...arr.slice(i, j + 1).sort((a, b) => a - b), ...arr.slice(j + 1, arr.length - 1), ]; i = j; } } // Check if the array remains unsorted for (let i = 0; i < n - 1; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { document.write( "No<br>" ); return ; } } document.write( "Yes\n" ); } // Driver Code // Given Input let n = 6; let arr = [2, 5, 3, 4, 6]; let s = "01110" ; // Function Call checkIfPossibleToSort(n, arr, s); // tHIS CODE IS CONTRIBUTED BY _SAURABH_JAISWAL. </script> |
Yes
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Contact Us