CareerCup

I think this can be solved in O(N)

class SolutionForExchangeTwoElementsForSortedArray {

    public boolean solution(int[] arr) {
        if(arr.length <= 1) {
            System.out.println("Not enough element to swap");
            return true;
        }
        boolean flag = true;
        int first = -1;
        int second = -1;

        for (int i = 1; i < arr.length; i++) {
            if (flag) {
                if (arr[i - 1] > arr[i]) {
                    first = i - 1;
                    flag = false;
                }
            } else {
                if (arr[first] <= arr[i]) {
                    second = i - 1;
                }
            }

            if (second != -1) {
                break;
            }
        }
        if(second == -1) {
            second = arr.length -1;
        }
        if (first == -1) {
            return false;
        }
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;

        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i - 1] > arr[i]) {
                return false;
            }
        }
        return true;
    }
}

public class ExchangeTwoElementsForSortedArray {

    public static void main(String[] args) {
        SolutionForExchangeTwoElementsForSortedArray mSol = new SolutionForExchangeTwoElementsForSortedArray();
        System.out.println(mSol.solution(new int[] {4,2,2,2,5}));
        System.out.println(mSol.solution(new int[] {4,2,2,2,3}));
        System.out.println(mSol.solution(new int[] {3,2,2,2,3,3,4,4,4}));
        System.out.println(mSol.solution(new int[] {3,2}));
        System.out.println(mSol.solution(new int[] {3,2,2}));
        System.out.println(mSol.solution(new int[] {3,2,4}));
        System.out.println(mSol.solution(new int[] {8,2,2,4}));
        System.out.println(mSol.solution(new int[] {8}));
    }
}

1) Copy the original array
2) Sort the copy
3) loop through the arrays and check how many corresponding elements don't match

O(NlogN) - space 2N

Make a duplicate array , sort duplicate array and compare with original array element by elements , if there are only two mismatch , then it is possible otherwise not.

The nlogn is a rather generous runtime allowance here, as it meanns we can run a heapsort or similar.

The idea here is to create a sorted version of the array, and compare to see if there are exactly m differences (in this case, m=2)

in python:

def only_m_switches(val_array, m):
    tmp_array = sorted(val_array)
    for i in range(0, len(val_array)):
        if tmp_array[i] != val_array[i]:
            m -= 1
    return m == 0

this fulfills the required space and time usage as well.

You can use quick sort to sort the array but during sorting if you need to do more than one swap just return false. Use pivot = N /2
This way you don't need additional space and most of the time don't need to sort entire array.

Assumptions:
*The method should return true/false, as the question is "is it possible to...".
*We can't affect the array insitu, since we are only characterizing it (it doesn't say "sort the array" or even "return a sorted array").
* Assuming sorting is lowest index => lowest value (numerical order starting at idx 0)

Discussion:
If swapping 2 elements results in a sorted array, it means all of the elements are in their proper place except for the 2 we need to swap.

Thus, if we just walk the array we will run into these "anomalies", which are the out-of-place elements. Naively I claim that we want two and exactly two anomalies, otherwise we can't do this.

But there is an edge-case (literally) when the out-of-place element is on either end and it belongs on the other side of the adjacent element, in which case we would only see one anomaly (either right at the beginning or at the end) and it can be swapped with the neighboring element. If either the start or end element belongs somewhere in the middle, we must have another out-of-place element with which to swap, but if there isn't an internal anomaly, then all of the elements are in the correct place and must be preserved. Allowing repeats makes the previous statement false so that would require clarification of the question.

An easy approach, then, is do a single walk of the array and notate anomalous indices. After the fact, we can return false if we got more than 2, or do some more processing to validate that the one or two out-of-place elements can be "fixed". In this example we do an array copy as a workspace for the swap, so we use an extra N space.

JAVA

public boolean canTwoSwapsSortArray(int[] arr)
{
	int numAnomaliesFound = 0;
	int[] anomalousIndices = new int[2];

	// note the terminating condition
	for ( int idx = 0; idx < arr.length - 2; idx++ )
	{
		if ( arr[idx] > arr[idx+1] )
		{
			numAnomaliesFound++;
			// we can cut it short here if we get more that 2
			if ( numAnomaliesFound > 2 )
				return false;
			else
				anomalousIndices[numAnomaliesFound-1] = idx;
		}
	}

	switch (numAnomaliesFound)
	{
		default:
			return false;
		case 1:
			// check for edge-cases
			if ( 0 == anomalousIndices[0] )
			{
				// We know the first one is greater than the 2nd
				// We need to make sure it fits between the next 2
				if (arr[0] <= arr[2] )
					return true;
			}
			// Notice the -2 here, because we didn’t actually
			// flag the last index as anomalous, we detected it
			// at the one before
			else if ( (arr.length-2) == anomalousIndices[0] )
			{
				// We know the last one is less-than the second-to-last
				// We need to make sure it fits between the previous 2
				if ( arr[(arr.length-1)] >= arr[arr.length-3] )
					return true;
			}
			else
			{
				return false;
			}
		case 2:
			// swap the elements and check
			int[] newArr = new int[arr.length];
			newArr.copy(arr);
			swap (newArr, anomalousIndices[0], anomalousIndices[1]);
			// 2nd time through N elements:
			for (int idx=0;idx<newArr.length - 2;idx++)
			{
				if ( newArr[idx] > newArr[idx+1] )
					return false;
			}
			// it worked!
			return true;
	}
}

We need the 2N space for the copy when we are checking that the swap works. However we can optimize this by just checking that the newly swapped elements would fit between their new neighbors, without actually swapping.

class CheckSortedByOneSwap{

	public static void main(String... a){
	
	CheckSortedByOneSwap obj = new CheckSortedByOneSwap();	

		System.out.println("True :: " + obj.solution(new int[] {4,2,2,2,5}));
        System.out.println("False :: " + obj.solution(new int[] {4,2,2,2,3}));
        System.out.println("True :: " + obj.solution(new int[] {3,2,2,2,3,3,4,4,4}));
        System.out.println("True :: " + obj.solution(new int[] {3,2}));
        System.out.println("True :: " + obj.solution(new int[] {3,2,2}));
        System.out.println("True :: " + obj.solution(new int[] {3,2,4}));
        System.out.println("False :: " + obj.solution(new int[] {8,2,2,4}));
        System.out.println("True :: " + obj.solution(new int[] {8}));
	
	}
	
	boolean solution(int[] arr){
	
		int len = arr.length;
		int indexForMisplaced = -1;
		int secondIndexForMisplaced = len-1;
		
		for(int i=1;i<len;i++){
			if(indexForMisplaced < 0){
				if(arr[i-1] > arr[i]){
					indexForMisplaced = i-1;
				}
			}
			else{
				if(arr[indexForMisplaced] <= arr[i]){
					secondIndexForMisplaced = i-1;
					break;
				}
			}
		}
		
		if(indexForMisplaced != -1){
			int temp = arr[indexForMisplaced];
			arr[indexForMisplaced]=arr[secondIndexForMisplaced];
			arr[secondIndexForMisplaced]=temp;
		}
		for(int i=1;i<len;i++){
			if(arr[i-1]>arr[i]){
				return false;
			}
		}
		
		return true;
	
	}
	
}

public boolean needMoreThanOneSwap(int[] a){
		boolean swappedOnce = false;
		int k = -1;
		for (int i = 0; i < a.length; i++) {
			if(i < a.length -1){
				//its not last element yet..
				if(a[i] > a[i+1]){
					if(k == -1){
						//record this index.. because we need to swap it later
						// if we hit this condition again.
						k = i;
						continue;
					}
					//need swap
					if(!swappedOnce){
						//swap
						int temp = a[k];
						a[k] = a[i+1];
						a[i+1] = temp;
						swappedOnce = true;
						k = -1;
					}else{
						//since we have already swapped once we don't want to swap again.. as
						// this means the array cannot be sorted by one swap
						return true;
					}
				}
			}
		}
		
		if(k != -1){
			//reaching here means we found array not sorted only at one index..and we couldn't swap it with.
			return true;
		}
		
		return false;
	}

public boolean needMoreThanOneSwap(int[] a){
		boolean swappedOnce = false;
		int k = -1;
		for (int i = 0; i < a.length; i++) {
			if(i < a.length -1){
				//its not last element yet..
				if(a[i] > a[i+1]){
					if(k == -1){
						//record this index.. because we need to swap it later
						// if we hit this condition again.
						k = i;
						continue;
					}
					//need swap
					if(!swappedOnce){
						//swap
						int temp = a[k];
						a[k] = a[i+1];
						a[i+1] = temp;
						swappedOnce = true;
						k = -1;
					}else{
						//since we have already swapped once we don't want to swap again.. as
						// this means the array cannot be sorted by one swap
						return true;
					}
				}
			}
		}
		
		if(k != -1){
			//reaching here means we found array not sorted only at one index..and we couldn't swap it with.
			return true;
		}
		
		return false;
	}