Zigzag Arrangement

Question

Given an array with possible repeating elements you have to rearrange such that elements are alternatively decreasing and increasing (strict increase/decrease). For example, suppose the given array is 1 1 2 3 4 5 one possible answer would be 2 1 3 1 5 4.
Assumption: Solution do exist for any given input.
Hint: Try to avoid sorting.

Comments

Sir can we do it by swapping

Suppose we have an array{ 1 5 4 3}

If two element of is not in zigzag arrangement then swap them otherwise Not need

Here 1st and 2nd are already in zigzag arrangement so no need to swap.

Now suppose current position is a[2] then swap a[2] and a[3]

So array will be {1 5 3 4}

---

And when elements repeat?

---

see it once , is it going right direction?

---

do nothing just increment the array compare 2 repeated element with next element.

{1 1 1 3}

Compare first and second so do nothing

Compare second third and so do nothing

and so on

Ot:{1 1 1 3}

---

Good one but consider for

1 2 3 3 3 4 5

---

But see if there is repeating element where it is placed @Manoj

---

In the output no repeating elements must come adjacent.

---

what is problem with it 1 2 3 3 3 4 5

See what I done

first take two pointer

first pointer taking 1st element and second pointer searching an element greater than that

if got then swap it and put it in a different array i.e. b[] and then delete those two element from first array

Similarly other elements too

---

The elements must be alternatively decreasing and increasing  

For 1 2 3 3 3 4 5, one possible solution is

3 1 3 2 4 3 5

---

sir,,,using sorting we can not find the solution ????

i tried u just check once..

1) sort the array in ascending order..

2) find the mid point

loop

3)from end of array print element and then decrease the index till mid point

4) from the starting print one element and then increase the index till midpoint-1

5) goto loop

for  example we have 1 2 3 4 5|||| 6 7 8 9 10

10 1 9 2 8 3 7 4 6 5

it will also work when elments are repeated

plz clarify...did i understood the question or not...

---

@Tauhin see what sir ask to get before ur comment

---

@ srestha  from 3 to 1 it decreasing and from 1 to 3 itz increasing and from 3 to 2 itz again decreasing...and so on....is it right...or i am on wrong track...

Answer 1

A simple algorithm- iterate over the array and comparing consecutive elements as in bubble sort and swapping if the required condition is violated. 

In case elements are repeated, swap the one with the next distinct number. 

Should run in $O(n)$. 

import java.io.*;
public class Zigzag{

	int findg(Integer[] array, int el, int index){
		int i = index;
		while((i < array.length) && (array[i] == el)) 
			i++;
		if(i < array.length)
			return i;
		i = 0;
		while(array[i] == el)
			i++;
			return i;

	}
	void rearrange(Integer[] array) {
		for(int i = 0; i< array.length-1; i++)
		{
			if(array[i] == array[i+1])
			{
				int ind = findg(array, array[i],  i+2);
				if(array[ind] > array[i])
				{
					array[i%2 == 0? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 0? i+1: i];
				}
				else{
					array[i%2 == 1? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 1? i+1: i];
				} 
			}
			else if(((array[i] < array[i+1]? 1: 0) ^ (i%2)) > 0)
			{
				int tmp = array[i];
				array[i] = array[i+1];
				array[i+1] = tmp;
			}
			 
		}
		
	}
	void printArray(Integer[] array){
		for(int i = 0; i < array.length; i++)
		{
			System.out.print(array[i]+" ");

		}
	}


	public static void main(String args[]) {

		Zigzag myArray = new Zigzag(); //Initialize class
		Integer[] array = new Integer[args.length];
		int i = 0;
		for(String word:args)
			array[i++]=Integer.parseInt(word);
		myArray.rearrange(array);
		myArray.printArray(array);

	}

}

Comments

Sir could u plz tell me what this code is doing? If there is repeating element this code replacing 1st element of repeating element . is it not?

if(array[ind] > array[i])

{ array[i%2 == 0? i: i+1] = array[ind];

array[ind] = array[i%2 == 0? i+1: i]; }

---

Not always the first element being repeated is replaced. The code is replacing the odd position if new element is larger and even position if it is smaller. There is one catch in the code which breaks the order of n complexity.