3
\$\begingroup\$

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<=\$10^6\$ . 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++;
            }
        }
    }
}
}
\$\endgroup\$
4
  • \$\begingroup\$ This would be so much easier if you could just make a copy of the array and then input the numbers in the right spot in the original again ... \$\endgroup\$
    – Imus
    Feb 8 '18 at 9:29
  • \$\begingroup\$ @Imus We can't use an additional array. \$\endgroup\$ Feb 8 '18 at 9:36
  • \$\begingroup\$ Rotateright method is important as it is the only way of maintaining the relative order. \$\endgroup\$ Feb 8 '18 at 9:39
  • \$\begingroup\$ I have already tried using 2 different pointers for maintaining the next positive and negative elements in order to reduce the time of searching the next positive or negative element every time. I didn't update the code here because it didn't work too for that testcase. And thanks for your suggestions in my code, will work on it. \$\endgroup\$ Feb 11 '18 at 18:15
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I can't use additional data structure that's what question's requirement is. If it was allowed, I would have done it already. And yes, you are right about my current implementation, combining both operation can do the job in time limit but I can't find a way. Can you? \$\endgroup\$ Feb 8 '18 at 9:03
  • \$\begingroup\$ As you posted it here I don't see that requirement. Can you also provide us with the link of the original question so we can check the wording? \$\endgroup\$
    – Imus
    Feb 8 '18 at 9:06
  • \$\begingroup\$ @Imus I updated my question. The original question do not give any further information. And I can't give you a link as it is a question from a site which will ask for login before displaying the question page. \$\endgroup\$ Feb 8 '18 at 9:29
  • \$\begingroup\$ perhaps it's a site that many of us already have logins on? \$\endgroup\$
    – Alnitak
    Feb 8 '18 at 12:31
  • \$\begingroup\$ No. its a private teaching institute in New Delhi, India \$\endgroup\$ Feb 8 '18 at 17:45
1
\$\begingroup\$

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++;
\$\endgroup\$
2
  • \$\begingroup\$ I had already suggested the arraycopy earlier but that wont help here. It's only better when copying large blocks, but worse when it's only a couple of elements. And for every large block to copy there will some time later always be smaller blocks to copy as well. \$\endgroup\$
    – Imus
    Feb 12 '18 at 6:51
  • \$\begingroup\$ @Imus I clearly mentioned it's a small improvement. I explained an important improvement in the paragraph just before that. \$\endgroup\$
    – janos
    Feb 12 '18 at 8:50
0
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ You seemed to be confused when I asked about "my other answer". My original is now deleted as it wasn't useful at all. Please try this solution instead. If this does not work, you may want to consult your teachers / fellow students about the speed requirements beïng really strict. \$\endgroup\$
    – Imus
    Feb 8 '18 at 17:18
  • \$\begingroup\$ Your solution , for input: 1 2 3 -1 -2 -3 giving output:1 3 2 -1 -3 -2 Expected output: 1 -1 2 -2 3 -3. Yes, I think I should consult my teacher now. \$\endgroup\$ Feb 8 '18 at 17:44
  • \$\begingroup\$ Hmm, can you try again with my edited version? Must have made a copy paste mistake somewhere that had the < flipped ... This one should work \$\endgroup\$
    – Imus
    Feb 9 '18 at 7:17
  • \$\begingroup\$ it is giving correct answer but on submission getting time limit exceeded for last case which I am getting for my code too. \$\endgroup\$ Feb 9 '18 at 13:15
  • \$\begingroup\$ Then all that's left is to either consult your teacher on what else you can improve (or if the test is wrong). Or you could cheat and use a second array to turn it into linear time complexity. \$\endgroup\$
    – Imus
    Feb 9 '18 at 13:31
0
\$\begingroup\$

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   
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Is this intended to be a new question? This looks like C but the question uses Java. If you have a question please ask a new question rather than posting an answer to another one. \$\endgroup\$
    – Null
    Jun 26 '18 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.