Check if Array can be Sorted under constrained swapping

Problem Statement:Given an Array of size N,Find if it is possible to sort it in non-decreasing order by doing swaps according to following rules

• Each value in array is associated with its type i.e either '1' or '0'
• Two values can be swapped with each other if and only if they are of  different types.

Return true if array can be sorted,otherwise return false

Examples:

input:n=3 

arr=[3,1,2] 

 type=[0,1,1] 

output:true 

Explanation:First swap element at position 1 & 2 Second swap element at position 2 & 3 

input:n=3 

arr=[5,15,4] 

type=[0,0,0]  

output:false

Approach:As given in the question we can only swap values of different type.If we carefully observe the question we can find that we need atleast 1 element of type '0' and 1 element of type '1'.If both these types of element are present in array then we can sort the array with swaps.So,our problem got reduced to check if there are present both type of elements in the array. 

Below is the Java implementation of the above approach:

Code

// Java program of the above approach

import java.io.*;
class Solution {
    // Function to check if array, A[] can be converted
    // into sorted array by swapping (A[i], A[j]) if B[i]
    // not equal to B[j]
    static boolean checkifSorted(int A[], int B[], int N)
    {
        
        // Stores if array A[] is sorted
        // in descending order or not
        boolean flag = false;

        // Traverse the array A[]
        for (int i = 0; i < N - 1; i++) {

            // If A[i] is greater than A[i + 1]
            if (A[i] > A[i + 1]) {

                // Update flag
                flag = true;
                break;
            }
        }
        // If array is sorted
        // in ascending order
        if (!flag) {
            return true;
        }
        // count = 2: Check if 0s and 1s
        // both present in the B[]
        int count = 0;
        // Traverse the array
        for (int i = 0; i < N; i++) {
            
            // If current element is 0
            if (B[i] == 0) {
                
                // Update count
                count++;
                break;
            }
        } 
        // Traverse the array B[]
        for (int i = 0; i < N; i++) {
            
            // If current element is 1
            if (B[i] == 1) {
                count++;
                break;
            }
        }
        // If both 0s and 1s are present
        // in the array
        if (count == 2) {
            return true;
        }
        return false;
    }
    // Driver Code
    public static void main(String[] args)
    {
        // Input array A[]
        int A[] = { 3, 1, 2 };

        // Input array B[]
        int B[] = { 0, 1, 1 };

        int N = A.length;
        // Function call
        boolean check = checkifSorted(A, B, N);

        // If true,print true
        if (check) {
            System.out.println("true");
        }
        // Else print false
        else {
            System.out.println("false");
        }
    }
}

 

Output:

true

Time Complexity:O(n)

Auxiliary Space:O(1)

Feel free to comment if you have any doubt in comments section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.

Learn how to prepare for Information Technology Based companies here