PROBLEM DESCRIPTION
Given an array arr of distinct elements of size N, the task is to rearrange the elements of the array in a zig-zag fashion so that the converted array should be in the below form:
1
| arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < . . . . arr[n-2] < arr[n-1] > arr[n].
|
NOTE: If your transformation is correct, the output will be 1 else the output will be 0.
geeksforgeeks
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution{
public void zigZag(int a[], int n){
Arrays.sort(a);
for(int i=1; i+1<n; i+=2){
swap(a, i, i+1);
}
}
public void swap(int a[], int i, int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
|
OPTIMIZATION - O(n) SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public static void zigZag(int n, int[] arr) {
// init: check if current element is less than next element (which should be true for 0th index)
boolean checkLessThan = true;
// iterate over the elements
for(int i=0; i<n-1; i++){
// we need to check if current element is less than next element
if(checkLessThan){
// if current element is not less than next element, then swap both
if( !(arr[i] < arr[i+1]) )
swap(arr, i, i+1);
// we need to check if current element is more than next element
}else{
// if current element is not more than next element, then swap both
if( !(arr[i] > arr[i+1]) )
swap(arr, i, i+1);
}
// toggle
// for next pair, the relation should be opposite
checkLessThan = !checkLessThan;
}
}
public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
|
