TheJobOverflow | Publicis Sapient | SDE

Question: Publicis Sapient | SDE | 12 December

Entering edit mode

Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on...

Note: O(1) extra space is allowed. Also, try to modify the input array as required.

Input: First line of input conatins number of test cases T. First line of test case contain an integer denoting the array size N and second line of test case contain N space separated integers denoting the array elements.

Output: Output the modified array with alternated elements.

Constraints:

1 <=T<= 100
1 <=N<= 107
1 <=arr[i]<= 107

Example:
Input:
2
6
1 2 3 4 5 6
11 
10 20 30 40 50 60 70 80 90 100 110

Output:
6 1 5 2 4 3
110 10 100 20 90 30 80 40 70 50 60

ADD COMMENT • link

Entering edit mode

@smartyshubhendu has pointed out a neat solution which I think is optimal if you are not allowed to take any extra space! (Haven't proved, prove me wrong)

However, we are allowed O(1) extra space.
So we can do better.

But lets first get context w.r.t. constant space constraint imposed.

We can easily find final position of i^th integer in given sequence easily.
Assuming 1-index, if i > n-i then i^th integer is going to be counted as (n-i)^th smallest integer else i^th largest intger.
So final position of i^th Smallest = i + i
and final position of i^th Largest = i + i - 1.

So we can find final position of every integer, however we have to use O(1) space so how do we make use of above simple formula? By proving above function makes cyclic function of length = N. Lets first see the simple algorithm in work first,

Lets take an example sequence. 
1 2 3 4 5 6

Let orig_pos be the extra O(1) space that we take.

Step 1
swap(6,1), orig_pos of 1= 1 
6 2 3 4 5 1

Step 2
final position of 1 should be position-2
swap(1,2), orig_pos of 2 = 4
6 1 3 4 5 2

Step 3
final position of 2 should be position-4
swap(2,4), orig_pos of 4 = 4
6 1 3 2 5 4

Step 4
final position of 4 should be position-5
swap(4,5), orig_pos of 5 = 5
6 1 3 2 4 5

Step 5
final position of 5 should be position-3
swap(5,3), orig_pos of 3 = 6
6 1 5 2 4 3

Now we terminate as final position of 3 = original position.

ADD COMMENT • link 4.3 years ago manas_kv 80

Entering edit mode

Its based on observation skill.
For every index i -> [0,N-1]

Pseudo Code

if (i%2==0) {
      reverse array [i,N-1] 
}
else if(i%4==1) {
      swap array[i] and arr[N-1] 
}

Time Complexity O(N²)
Space Complexity O(1)

ADD COMMENT • link

Similar Posts

Loading Similar Posts

Time Complexity	O(N)
Space Complexity	O(1)