link : https://practice.geeksforgeeks.org/problems/convert-array-into-zig-zag-fashion1638/1#
Given an array Arr (distinct elements) of size N. Rearrange the elements of array in zig-zag fashion. The converted array should be in form a < b > c < d > e < f. The relative order of elements is same in the output i.e you have to iterate on the original array only.
Example 1:
Input:
N = 7
Arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: 3 7 4 8 2 6 1
Explanation: 3 < 7 > 4 < 8 > 2 < 6 > 1
Example 2:
Input:
N = 4
Arr[] = {1, 4, 3, 2}
Output: 1 4 2 3
Explanation: 1 < 4 > 2 < 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function zigZag() which takes the array of integers arr and n as parameters and returns void. You need to modify the array itself.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 105
0 <= Arr[i] <= 106
Solution:
We on an overall level wanted to make the odd index maximum than it's adjacent even index peers, and with the even index we need to make those minimum.
If such situation arises, then we are good but if odd index element is min than even (or vice versa) we need to alter the array upon that spot
The idea here to alter is to keep the elements intact, so the best way to do is to swap the adjacent index (and not to increase or decrease the value of array elements).
This could be done in one iteration only, and hence could expect the time complexity of O(N) and space complexity of O(1).
//User function Template for Java
class Solution{
public void zigZag(int a[], int n){
// Code your solution here.
// 0 < 1 > 2 < 3 > 4
// wanting odd index to be max
for (int i = 0; i < n-1; i++) {
if (i % 2 == 0) {
// need to min
if (a[i] > a[i+1]) swap(a, i, i+1);
} else {
// need to max
if (a[i] < a[i+1]) swap(a, i, i+1);
}
}
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
This solution works as in the current or next iteration, the odd index would have the higher value. The best possible way to track this is by taking a sorted array and dry run upon it.
Alternative solution:
public class ToggleSolution {
void zigZag(int arr[], int n) {
boolean isGreater = false;
for(int i = 0; i < n-1; i++) {
if(!isValid(arr, i, i+1, isGreater))
swap(arr, i, i+1);
isGreater = !isGreater;
}
}
boolean isValid(int[] a, int i, int j, boolean isGreater) {
return (a[i] > a[j]) == isGreater;
}
void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void main(String[] args) {
int[] a =
// {1,2,3,4,5,6,7};
{4, 3, 7, 8, 6, 2, 1};
// {1, 4, 3, 2};
new ToggleSolution().zigZag(a, a.length);
System.out.println(Arrays.toString(a));
}
}
Let me know which solution is a clean and proper!
Top comments (0)