HackerRank : Week of Code 31 – Accurate Sorting

By | April 12, 2017
Accurate Sorting : Hackerrank

Consider an unsorted array,A = a0, a1,a2…. , of distinct integers from 0  to n-1 . We can swap two adjacent elements in A any number of times as long as the absolute difference between these elements is 1.

For example, the diagram below depicts an array where we can swap adjacent elements 1 and 2 or  4 and 3 , but we cannot swap adjacent elements 2  and 0 or 0 and  4:

image

Answer  q queries, where each query consists of some array A. For each query, print Yes on a new line if it’s possible to sort the array in ascending order by performing the swap operation defined above; otherwise, print Noinstead.

Input Format
The first line contains a single integer denoting q. The subsequent lines describe each of the q queries in the following format:

  1. The first line contains an integer denoting n.
  2. The second line contains n space-separated integers describing the respective values of a0, a1, a2,, …. a n-1.

Output Format
For each query, print Yes on a new line if it’s possible to sort the array; otherwise, print No instead.
Sample Input 0

2
4
1 0 3 2
3
2 1 0

Sample Output 0

Yes
No

Solution

All the test cases are passed for now. Let us see for PRELIMINARY cases afterwards.
Approach: 
I have implemented bubble sort, only outer loop and checked the condition for swapping. 
In the end, i am checking if the array resulted is sorted or not, and displaying Yes 
or No.
Solution:

package weekOfCode31;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class AccurateSorting {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();

		for (int i = 0; i < t; i++) {
			int n = scan.nextInt();
			int a[] = new int[n];

			ArrayList aList = new ArrayList<>();
			ArrayList bList = new ArrayList<>();

			for (int j = 0; j < n; j++) {
				a[j] = scan.nextInt();
				aList.add(a[j]);
			}
			Collections.sort(aList);

			for (int k = 0; k < n - 1; k++) {
				int l = k + 1;
				{
					if (a[k] - a[l] == 1) {
						int temp = a[l];
						a[l] = a[k];
						a[k] = temp;
					}
				}
				l++;
			}

			for (int j : a)
				bList.add(j);

			if (aList.equals(bList))
				System.out.println("Yes");
			else
				System.out.println("No");
		}

	}

}