Problem
We are given an array in which we have equal number of positive and negative elements.
We have to rearrange this array such that all positive and negative elements are at alternate positions and also, respective order should be maintained. N i.e. the size of array can be: 1<=N<=106 . No additional data structure can be used
INPUT:
1 2 3 -1 -2 -3
OUTPUT:
1 -1 2 -2 3 -3
My code was accepted but it exceeded the time limit for a case. How can I make my code more efficient by reducing its time complexity?
My code:
import java.util.*;
class A{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
a[i]=s.nextInt();
rearrange(a);
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
public static void rotateright(int a[],int l,int r)
{
int temp=a[r];
for(int i=r;i>l;i--)
{
a[i]=a[i-1];
}
a[l]=temp;
}
public static void rearrange(int a[])
{
int n=a.length;
int i=0,j=0;
while(i<n)
{
if(i%2==0) //even index should have positive element
{
if(a[i]>0) //already positive
i++;
else //for negative
{
j=i+1;
while(j<n) //finding next positive
{
if(a[j]>0)
break;
j++;
}
rotateright(a,i,j); //making even index positive
i++;
}
}
else //odd index should have negative element
{
if(a[i]<0) //already negative
i++;
else //for positive
{
j=i+1;
while(j<n) //finding next negative
{
if(a[j]<0)
break;
j++;
}
rotateright(a,i,j); //making odd index negative
i++;
}
}
}
}
}
Solution
Worst case
Picturing the worst case helps understanding the problem.
The test failing probably uses an array of size n containing n/2 positive numbers followed by n/2 negative numbers (or vice-versa).
Current implementation
Note that when you find an element out of place, you are iterating twice through the indices, until you find the correct element: one time two found its position, another to move all elements in between.
You can combine both operations into one. Still this algorithm resembles the insertion sort. It will be quadratic in the worst case that I described (more specifically, (n/2)^2).
Using extra space
One efficient way to solve this is to build the correct array from the beginning. This requires O(1) of extra space.
You create 3 arrays: one to buffer positive numbers, other to buffer negative numbers, and a 3rd one with the final result.
When reading from stdin:
- Place the number in the 3rd array if it matches the position, otherwise store it in the appropriate array;
- If the number matches, try to use numbers stored in the positive/negative numbers arrays to keep filing the 3rd array (using FIFO).
What we are doing is essentially merging 3 sorted arrays: stdin, the array with positive numbers and the array with negative numbers.
This should run linearly, requiring 2 writes per number out of place.
Performance
I see two slow elements in this code:
- Finding the next index to rotate the sub-array
- Rotating the array
The current implementation starts searching for the next index of a positive or negative element always from the current index.
That’s not optimal.
Consider an example input where the array starts with N negative numbers followed by N positive numbers.
As you scan from left to right, every step you search from nearly the beginning until nearly half-way, perform a rotation,
then search again. For such input, the search is quadratic.
You can do better, by tracking the last known positions of positive and negative numbers,
so that when you need to find the next out-of-order number,
the search can continue where it left off.
In my tests this improvement seems to reduce the time of the computation to half for this kind of inputs.
As for rotating the array,
I’m afraid there won’t be a magic bullet without using extra storage.
A small improvement is possible by replacing the manual rotation with System.arraycopy:
int temp = arr[right];
System.arraycopy(arr, left, arr, left + 1, right - left);
arr[left] = temp;
Don’t repeat yourself
In rearrange,
i++ happens at the end of all branches of execution.
It would be better to extract the i++ to the end of the outer while loop.
That way you cannot accidentally forget it in one of the branches.
Next, you can convert the outer while loop to a counting for loop.
The result will be more compact and probably easier to read.
In Java, variables are block-scoped.
So you don’t need to initialize int j up front,
it’s better to do that in the smallest necessary scope.
(Note that with my suggestion above to track the last known positive and negative indexes, this point is moot, because int nextNegativeIndex and int nextPositiveIndex will be necessary to declare at the top of the function, to track throughout the loop.)
Style
It’s good to use descriptive variable names,
as I did above in the rewritten rotateright method.
Also, the common convention in Java is to use camelCase for method and variable names,
so rotateRight would be better.
The common convention in Java is to place opening { on the same line as the statement.
And it’s recommended to always use a { ... } with if, while statements.
Like this, and I suggest to adopt this writing style:
j = i + 1;
while (j < n) {
if (a[j] > 0) {
break;
}
j++;
}
rotateright(a, i, j);
i++;
It looks like the main improvement is to use the infromation you get between “finding an item that is out of place” (a positive on odd index or negative on even index) and looking for the first item to put into that place. In your current solution you’re always resetting everything to the spot right after that out of place element. But we know that everthing in between is either positive or negative. So how do we use that information?
The idea is to go through the array exactly once and do 1 of 2 things:
1) check if this is an out of place item
2) if we already have an out of place item, check if the new one should be put in that previously found place.
This results in the following solution:
public static void rearrange(int arr[]){
int outOfPlace = -1;
for(int index = 0; index < arr.length; index ++){
if(outOfPlace == -1){ //looking for the first out of place index
if (((arr[index] < 0) && (index % 2==0))
|| ((arr[index] >= 0) && (index % 2)==1)) {
outOfPlace = index;
}
} else { // previously found an out of place index and now looking what to put there
if ((((outOfPlace % 2) == 0) && (arr[index] >= 0))
|| (((outOfPlace % 2) == 1) && (arr[index] < 0))) {
rotateright(arr, outOfPlace, index);
if(outOfPlace + 1 < index){
outOfPlace += 2;
} else {
outOfPlace = -1;
}
}
}
}
}
Notice that in step 2 after having replaced the item, we know the next “wrong” item is either 2 spaces further (if it’s a list of all positive/negative numbers) or we hit the current spot and go back to step 1.
If this is still too slow I’m out of ideas.
Here a “count” variable is used to notify the number of negative numbers and to execute swapping of negative and positive numbers. I guess this code looks simple and ideal. If any drawbacks are found in terms of logic or performance please do correct and optimize.
#include <stdio.h>
// prototype for swap
void swap(int *a, int *b);
int count=0;
// The main function that rearranges elements of given array. It puts
// negative elements at even indexes (0, 2, ..) and positive numbers at
// odd indexes (1, 3, ..).
void rearrange(int arr[], int n)
{
// The following few lines are similar to partition process
// of QuickSort. The idea is to consider 0 as pivot and
// divide the array around it.
int j = -1,i;
for (int i = 0; i < n; i++)
{
if (arr[j] < 0)
{
i++;
swap(&arr[j], &arr[i]);
}
}
// Now all positive numbers are at end and negative numbers at
// the beginning of array. Initialize indexes for starting point
// of positive and negative numbers to be swapped i,e i have used i and j
// with count variable for limiting the number of swaps to be done.
// The outcome after the above step will be { -1 -2 -3 -4 5 6 7 8 }
// Increment the negative index by 2 and positive index by 1, i.e.,
// swap every alternate negative number with next positive number
for(i=count; i<n-1; i++)
{
for(j=0; i<n-1; j++)
{
swap(&arr[j+1] , &arr[i]);
j = j + 2; //index pointing for negative numbers are incremented
break; // to come out of inner loop after swapping of positive
// and negative elements
}
}
}
// A utility function to swap two elements
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
count++;
}
// A utility function to print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%4d ", arr[i]);
}
// Driver program to test above functions
int main()
{
int arr[] = {-1, -2, 5, -3, 6, 7, -4, 8};
int n = sizeof(arr)/sizeof(arr[0]);
rearrange(arr, n);
printArray(arr, n);
return 0;
}
Output:
-1 5 -3 6 -2 7 -4 8