Given an array of positive and negative integers, rearrange it so that you have positive integers at one end and negative integers at the other

Question

Recently, I came across a question about a Microsoft interview for software engineers.

Given an array of positive and negative integers, reinstall it so that you have positive integers at one end and negative integers at the other , but keep their order of appearance in the original array.

For example, this [1, 7, -5, 9, -12, 15]
The answer will be as follows: [-5, -12, 1, 7, 9, 15]

This should be done in O (n).

We could easily do this in O (n), but I cannot think of how we can maintain the order of the elements, as in the original array. If we forget about the complexity of O (n), can someone tell me how we can keep the order of the elements without taking into account the complexity of space and time.

EDIT . In the real question, we also need to have the spatial complexity O (1).

Answer 1

To achieve this result in constant space (but in quadratic time), you can use the two-queue approach by placing one queue at each end of the array (similar to the Dutch national flag algorithm). Reading elements from left to right: adding an element to the left queue means leaving it alone, adding an element to the desired queue means transferring all elements not in the queue from left to one, and placing the added element at the end. Then, to combine the queues, simply reorder the items in the second queue.

Performs the operation O (n) (moving elements on the left) up to O (n) times, which gives the operating time O (n²).

Using a method similar to merge sorting, you can achieve lower complexity O (n log n): cut the array into two halves, sort them recursively in the form [NP] [NP] , then change the first P to the second N in O (n) time (it gets a little complicated when they don't have exactly the same size, but it's still linear).

I have absolutely no idea how to do this before O (n) time.

EDIT : In fact, your list of links is correct. If the data is provided as a doubly linked list, you can implement a strategy with two queues in O (n) time, O (1):

 sort(list): negative = empty positive = empty while (list != empty) first = pop(list) if (first > 0) append(positive,first) else append(negative,first) return concatenate(negative,positive) 

With an implementation of a linked list that holds pointers to the first and last elements, then pop, append and concatenate are O (1) operations, so the overall complexity is O (n). As for space, none of the operations allocate any memory (append just uses the memory released by pop), so O (1) as a whole.

Answer 2

Here is a version of the spatial solution O (n) of time O (1), the assumed maxValue * (maxValue + 1) is less than Integer.MAX_VALUE, where maxValue is the result of the value maxmum minus minmum value in the array. It uses the source array as a temporary array to store the result.

 public static void specialSort(int[] A){ int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for(int i=0; i<A.length; i++){ if(A[i] > max) max = A[i]; if(A[i] < min) min = A[i]; } //Change all values to Positive for(int i=0; i<A.length; i++) A[i]-= min; int newMax = max-min+1; //Save original negative values into new positions int currNegativeIndex = 0; for(int i=0; i<A.length; i++) if(A[i]%newMax < (-min)) A[currNegativeIndex++] += (A[i]%newMax)*newMax; //Save original positive values into new positions int currPositiveIndex = currNegativeIndex; for(int i=0; i<A.length; i++) if(A[i]%newMax > (-min)) A[currPositiveIndex++] += (A[i]%newMax)*newMax; //Recover to original value for(int i=0; i<A.length; i++){ A[i] = A[i]/newMax + min; } } 

Answer 3

I'm not sure I understood the question correctly, as the answer seems too simple:

• Go through the array and count the negative numbers - O (n)
• Create a new array of size O (n)
• Go through the original array and put the numbers in the new array. Use a known number of negative numbers to compensate for the positive - O (n)

Here is a quick way to do this in Python. It is slightly different from the above, first creating an array for negatives, and then adding positive values. So it is not so effective, but still O (n).

 >>> a = [1,7,-5,9,-12,15] >>> print [x for x in a if x < 0] + [y for y in a if y >= 0] [-5, -12, 1, 7, 9, 15] 

Edit: Well, now with O (1) space complexity, it becomes much more complicated. I'm interested in how to achieve this in O (n) time complexity. If this helps, here is a way to hold O (1) complexity, but it takes O (n ^ 2) time complexity:

• Start with the leftmost negative number. Go through the array until you find the next negative number.
• In the new cycle, we exchange a negative number for a positive number to the left of it. Do this until you reach other negative numbers. This ensures that the order of the numbers remains unchanged.
• Rince and repeat until you reach the end of the array when looking for a new negative number.

Answer 4

This can be done in O (n) and the space O (1).

We need to scan 3 times through the array and carefully change some values.

Assumption: the maximum value in an array with size N must be less than (N+1) * Integer.MAX_VALUE .

We need this assumption, since we are good at changing some positive values ​​in the array.

• In the first scan, find # negative and positive values ​​and the maximum
• In the second scan, we create a negative section of the array as follows:

We start at the beginning of the array, and we “ swap ” the first positive number found (for example, in index i ) with the first negative number found (for example, j ). Since negative numbers are considered relative to their location, the swap will be fine.

The problem is positive numbers, because there may be some other positive numbers between i and j . To deal with this problem, we must somehow encode the index of a positive number in this value before replacing it. So, we can understand where it was in the first paragraph. We can do this with a[i]=(i+1)*(max)+a[i] .

• In the third scan, we create a positive section of the array. at the end of the second scan, a negative array is created, and positive numbers are shifted to the right, but their location may be incorrect. Therefore, we go and correct their position, since this information was encoded by their value.

Here is the code:

 import java.util.Arrays; public class LinearShifting { public static void main(String[] args) { // TODO Auto-generated method stub int[] a = {-1,7,3,-5,4,-3,1,2}; sort(a); System.out.println(Arrays.toString(a)); //output: [-1, -5, -3, 7, 3, 4, 1, 2] } public static void sort(int[] a){ int pos = 0; int neg = 0; int i,j; int max = Integer.MIN_VALUE; for(i=0; i<a.length; i++){ if(a[i]<0) neg++; else pos++; if(a[i]>max) max = a[i]; } max++; if(neg==0 || pos == 0) return;//already sorted i=0; j=1; while(true){ while(i<=neg && a[i]<0) i++; while(j<a.length && a[j]>=0) j++; if(i>neg || j>=a.length) break; a[i]+= max*(i+1); swap(a,i,j); } i = a.length-1; while(i>=neg){ int div = a[i]/max; if(div == 0) i--; else{ a[i]%=max; swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1); } } } private static void swap(int[] a, int i , int j){ int t = a[i]; a[i] = a[j]; a[j] = t; } } 

Answer 5

Edit (5/29/2015): I overlooked the requirement to maintain the order of appearance, so the answer below does not satisfy all the requirements of the question. However, I leave the original answer for general interest.

---

This is a special version of the very important quicksort routine, known as the "partition". Definition: an array A containing N numeric entries is divided by the value K in the index p if A [i] K for 0 <= i <p and A [j]> = K for p <= j <N if all entries less than K (which means p = N) or not less than K (which means p = 0). For the problem under consideration, we will partition the array around K = 0.

You can split an unsorted array into any K value O (n) times by accessing each record in the array only once, using O (1) extra memory. Informally, you go through an array from both ends, moving values ​​that are on the wrong side. Perform a swap when one inappropriate value is found on each side of the array, and then continues step by step. Now C ++ code:

 // Assume array A[] has size N int K = 0; // For particular example partitioning positive and negative numbers int i = 0, j = N-1; // position markers, start at first and last entries while(1) { // Break condition inside loop while(i < N && A[i] < K) i++; // Increase i until A[i] >= K while(j >= 0 && A[j] >= K) j--; // Decrease j until A[j] < K if(i < j) swap(A[i],A[j]); else break; } // A[] is now partitioned, A[0]...A[j] < K, unless i==0 (meaning all entries >= K). 

Note that if all elements are equal to K (in this case, zero), I never increase and j = 0 at the end. A statement of the problem suggests that this will never happen. The section is very fast and efficient, and this efficiency is the reason why quicksort is the most popular sorting procedure for large arrays. The swap function can be std :: swap in C ++ or you can easily write your own:

 void swap(int& a, int& b) { int temp = a; a = b; b = temp; } 

Or just for fun, the numbers can be replaced with a place without temporary memory, although remember to overflow:

 // This code swaps a and b with no extra space. Watch out for overflow! a -= b; b += a; a = b - a; 

There are many separation options for special cases, such as a tripartite section for [elements <K] [elements == K] [elements> K]. The quick sort algorithm recursively solves the section, and the value of the K section is usually the first record in the current basement or calculated from several records (for example, the median of three). See Textbooks: Sedgewick and Wayne Algorithms (4th ed., P. 288) or The Art of Computer Programming. 3 from Knut (2nd ed., P. 113).

Answer 6

You can use 2 queues and combine them. Thus, you repeat only once in the first array and after each additional queue.

 negatives = [] positives = [] for elem in array: if elem >= 0: positives.push(elem) else negatives.push(elem) result = array(negatives, positives) 

Answer 7

Here is a solution with two iterations:
Let say that the length is n.
And I will use C as code, ignore syntax errors.

 solution[n]; for (i= 0,j=0 ; i < n ; i++ ) { if (array[i] < 0) solution[j++] = array[i]; } for (i = n-1,j=n-1 ; ; i > 0 ; i--) { if (array[i] >= 0) solution[j--] = array[i]; } 

The idea is to deal with it once and write all the negatives that we encounter.
Then go to it a second time from the end and write positive results from end to beginning.

Answer 8

This solution has the time complexity O (n) and the complexity of the space O (1)

Idea:

• track the index of the last negative item seen (lastNegIndex).

• loop through the array to find the negative elements preceded by the positive element.

• If such an element is found, swap it between the last NegIndex and the current index by one. Then update lastNegIndex (this will be the next index).

Here is the code:

 public void rightRotate(int[] a, int n, int currentIndex, int lastNegIndex){ int temp = a[currentIndex]; for(int i = currentIndex; i > lastNegIndex+ 1; i--){ a[i] = a[i-1]; } a[lastNegIndex+1] = temp; } public void ReArrange(int[] a, int n){ int lastNegIndex= -1; int index; if(a[0] < 0) lastNegIndex = 0; for(index = 1; index < n; index++){ if (a[index] < 0 && a[index - 1] >= 0) { rightRotate(a, n, index, lastNegIndex); lastNegIndex = lastNegIndex + 1; } } } 

Answer 9

If the structure at the beginning should not be an array, it is even simpler.

If you have the source numbers in a linked list, this is easy.

You can reconfigure the linked list, each time indicate a minus next to the next negative and positive next to the next positive.

Again, C as code, ignore the syntax. (may require zero checking here and there, but this is an idea)

 Cell firstPositive; Cell* lastPoisitive; lastPoisitive = &firstPositive; Cell firstNegative; Cell* lastNegative; lastNegative = &firstNegative; Cell* iterator; for(Iterator = list.first ; Iterator != null ; Iterator = Iterator->next) { if (Iterator->value > 0 ) lastPoisitive->next = Iterator; else lastPoisitive->next = Iterator; } list.first = firstNegative->next; list.last.next = firstPositive->next; 

Answer 10

If the goal is O (1) space (in addition to the elements themselves, which are considered freely variable) and O (NlgN), divide the problem into the task of creating arrays, which are known to have the form pnPN, where p and P are zero or more positive numbers, and n and N are 0 or more negative numbers, into arrays of the form pPnN. Any two-element array will automatically have this form. For two arrays of this form, find the first negative number, the next positive number and the last positive number, and "unscrew" the middle two sections of the array (it is easy to make in constant space the time proportional to the size of the array to be "unscrewed"). The result is an array of the form pPnN. Two consecutive such arrays form a larger array of the pnPN form.

To do things in a constant space, start by combining all the elements and putting them in a PN shape. Then do all quartets of elements, then all octets, etc. To the total size of the array.

Answer 11

Just an idea .. Consider a simpler task:

For an array where the first part ( Np ) contains only positive numbers and the last part ( Nn ): only negative ones. How to exchange these parts while maintaining a relative order?

The simplest solution is to use inversion:

 inverse(array, Np + Nn); // whole array inverse(array, Nn); // first part inverse(array+Nn, Np); // second part 

It has the time complexity O (n) and the complexity of the space O (1).

Answer 12

I highly doubt that O (n) time and O (1) is possible with an array . Some of them offer a linked list, but for this you need a special linked list in which you have direct access to the nodes, i.e. language inline lists will not work.

Here, my idea uses a custom doubly linked list that satisfies limited complexity, using as an example the following options: [1, 7, -5, 9, -12, 15]:

Scroll through the list if you see a negative result, cut it off and add the negatives in front at the end. Each operation is O (1), so the total time is O (n). Combined list operations are performed in place so that O (1) space.

More details:

 last_negative_node = null; at -5: cut off -5 by setting 7.next = 9, then add -5 to front by -5.next = 1, then update last_negative_node = 5 // O(1), the linked list is now [-5, 1, 7, 9, -12, 15] at -12: cut off -12 by setting 9.next = 15, then add -12 to front by -12.next = last_negative_node.next, then update last_negative_node.next = -12, then update last_negative_node = -12 //O(1), the linked list is now [-5, -12, 1, 7, 9, 15] no more negatives so done. 

Answer 13

O (n) Java solution

  private static void rearrange(int[] arr) { int pos=0,end_pos=-1; for (int i=0;i<=arr.length-1;i++){ end_pos=i; if (arr[i] <=0){ int temp_ptr=end_pos-1; while(end_pos>pos){ int temp = arr[end_pos]; arr[end_pos]=arr[temp_ptr]; arr[temp_ptr]=temp; end_pos--; temp_ptr--; } pos++; } } 

Answer 14

Here is the qiwangcs JavaScript implementation :

 function specialSort(A){ let min = Number.MAX_SAFE_INTEGER, max = -Number.MAX_SAFE_INTEGER; for(let i=0; i<A.length; i++){ if(A[i] > max) max = A[i]; if(A[i] < min) min = A[i]; } //Change all values to Positive for(let i=0; i<A.length; i++) A[i]-= min; const newMax = max-min+1; //Save original negative values into new positions let currNegativeIndex = 0; for(let i=0; i<A.length; i++) if(A[i]%newMax < (-min)) A[currNegativeIndex++] += (A[i]%newMax)*newMax; //Save original positive values into new positions let currPositiveIndex = currNegativeIndex; for(let i=0; i<A.length; i++) if(A[i]%newMax > (-min)) A[currPositiveIndex++] += (A[i]%newMax)*newMax; //Recover to original value for(let i=0; i<A.length; i++){ A[i] = Math.floor(A[i]/newMax) + min; } } // Demo const A = [-3,-7,2,8,-5,-2,4]; specialSort(A); console.log(A); 

Answer 15

I think this would work: here is a simple way that constant space (but quadratic time). Let's say that the array is the length N. Walk along the array from i = 0 to i = N-2 of the element I and I + 1. If element I is positive and element I + 1 is negative, replace them. Then repeat this process.

Each pass through the array will cause the negatives to drift to the left (and positive deviations to the right), sort of like sorting bubbles until (after a sufficient number of passes) they are all in the right place.

Also, I think it would work: it is also constant space (but quadratic time). Let's say P is the number of positive results. Scanning from left to right, when you find a positive x, stop scanning and “delete it” by moving all the elements after they remain on one. Then put x at the end of the array. Repeat the scan procedure P times to move all positives.

Answer 16

First, count the number k negative elements. Then you know that the first k numbers of the array (the first part of the array) must be negative. The following N - k elements must be positive after sorting the array.

You save two counters of the number of elements that observe these conditions in both parts of the array, and increase it at each step until you find out that one part is in order (the counter is equal to the size of this part). Then the other part is also OK.

This requires storage of O (1) and takes O (N) time.

Implementation in C ++:

 #include <iostream> #include <vector> using namespace std; void swap(vector<int>& L, int i, int j) { int tmp = L[i]; L[i] = L[j]; L[j] = tmp; } void signSort(vector<int>& L) { int cntNeg = 0, i = 0, j = 0; for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) { if (*it < 0) ++cntNeg; } while (i < cntNeg && cntNeg + j < L.size()) { if (L[i] >= 0) { swap(L, i, cntNeg + j); ++j; } else { ++i; } } } int main(int argc, char **argv) { vector<int> L; L.push_back(-1); L.push_back(1); L.push_back(3); L.push_back(-2); L.push_back(2); signSort(L); for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) { cout << *it << endl; } return 0; } 

Answer 17

This code works with O (n) complexity and O (1) space. No need to declare another array.

 #include <stdio.h> int* sort(int arr[], int size) { int i; int countNeg = 0; int pos = 0; int neg = 0; for (i = 0; i < size; i++) { if (arr[i] < 0) pos++; } while ((pos < (size-1)) || (neg < size-(pos-1))) { if ((arr[pos] < 0) && (arr[neg] > 0)) { arr[pos] = arr[pos] + arr[neg]; arr[neg] = arr[pos] - arr[neg]; arr[pos] = arr[pos] - arr[neg]; pos++; neg++; continue; } if ((arr[pos] < 0) && (arr[neg] < 0)) { neg++; continue; } if ((arr[pos] > 0) && (arr[neg] > 0)) { pos++; continue; } if ((arr[pos] > 0) && (arr[neg] < 0)) { pos++; neg++; continue; } } return arr; } void main() { int arr[] = { 1, 7, -5, 9, -12, 15 }; int size = sizeof(arr) / sizeof(arr[0]); sort(arr, size); int i; for (i = 0; i < size; i++) { printf("%d ,", arr[i]); } printf(" \n\n"); } 

Answer 18

 #include <iostream> using namespace std; void negativeFirst_advanced (int arr[ ], int size) { int count1 =0, count2 =0; while(count2<size && count1<size) { if(arr[count1]>0 && arr[count2]<0) { int temp = arr[count1]; arr[count1] = arr[count2]; arr[count2] = temp; } if (arr[count1]<0) count1++; if (arr [count2]>0) count2++; } } int main() { int arr[6] = {1,7,-5,9,-12,15}; negativeFirst_advanced (arr, 6); cout<<"["; for (int i =0; i<6;i++) cout<<arr[i]<<" , "; cout<<"]"; system("pause"); return 0; } 

Answer 19

Python, ( , K. K = 0, , ):

 def kPart(s, k): if len(s) == 1: return s else: if s[0] > k: return kPart(s[1:], k) + [s[0]] else: return [s[0]] + kPart(s[1:], k) 

Answer 20

O (1) , .

 void divide (int *arr, int len) { int positive_entry_seen = 0; for (int j = 0; j < len ; j++) { if (arr[j] >= 0 ) { positive_entry_seen = 1; } else if ((arr[j] < 0 ) && positive_entry_seen) { int t = arr[j]; int c = j; while ((c >= 1) && (arr[c-1] >= 0)) { arr[c] = arr[c-1]; c--; } arr[c] = t; } } } 

Answer 21

, O (n). . , , , , .

  int main() { int arr[] = {1,-2,3,4,-5,1,-9,2}; int j,temp,size; size = 8; for (int i = 0; i <size ; i++){ j = i; //Positive left, negative right //To get opposite, change it to: (arr[j] < 0) && (arr[j-1] > 0) while ((j > 0) && (arr[j] >0) && (arr[j-1] < 0)){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; j--; } } //Printing for(int i=0;i<size;i++){ cout<<arr[i]<<" "; } return 0; } 

Answer 22

, O (n) .

  int left = 0; int right = arr.length - 1; while (left < right) { while (arr[left] >= 0) { left++; } while (arr[right] < 0) { right--; } if (left < right) { ArrayUtility.swapInArray(arr, left, right); } ArrayUtility.printArray(arr); 

Answer 23

QuickSort. O (n2), - O (1). .

 def sortSeg(intArr) intArr.each_with_index do |el, idx| # if current element is pos do nothing if negative, # shift positive elements of arr[0..i-1], # to one position to their right */ if el < 0 jdx = idx - 1; while (jdx >= 0 and intArr[jdx] > 0) intArr[jdx + 1] = intArr[jdx]; jdx = jdx - 1; end # Insert negative element at its right position intArr[jdx + 1] = el; end end end 

Answer 24

 int [] input = {1, 7, -5, 9, -12, 15}; int [] output = new int [input.length]; int negativeIdx = 0; int positiveIdx = input.length - 1; for(int i = 0; i < input.length ; i++) { if(input[i] < 0) { output [negativeIdx++] = input[i]; } else { output [positiveIdx--] = input[i]; } } System.out.println (Arrays.toString(output)); 

Exit:

 [-5, -12, 15, 9, 7, 1] 

Answer 25

, O (n),

 int count = 0; //data is the array/vector in sort container having given input. if(data[0] < 0) count++; for(int i = 1; i < n; i++) { if(data[i] < 0) { int j = i; while(j> count) { data[j-1] += data[j]; data[j] = (data[j-1]-data[j]); data[j-1] -= data[j]; j--; } count++; } } 

https://gist.github.com/Shravan40/8659568

Answer 26

. .

  int[] n={2,-3,1,5,-10,-8}; int k=0; for(int i=1;i<n.length;i++) { int temp=0; if(n[i]<0) { temp=n[k]; n[k]=n[i]; n[i]=temp; k++; } } for(int j=0;j<n.length;j++) { System.out.println(n[j]); } 

Answer 27

Hope this helps. O (n ^ 2)

 #include <stdio.h> int main() { int a[] = {-3, 2, -5, 9, -2, -8, 6, 8, -1, 6}; int length = (sizeof(a) / sizeof(int)); int i, j = 0; printf("Size of array: %d\n", sizeof(a)); for (i = 0; i < length; i++) { if (i % 2 == 0 && a[i] < 0) { for (j = i + 1; j < length; j++) { if (a[j] > 0) { int t = a[i]; a[i] = a[j]; a[j] = t; break; } } } else if (i % 2 == 1 && a[i] > 0) { for (j = i + 1; j < length; j++) { if (a[j] < 0) { int t = a[i]; a[i] = a[j]; a[j] = t; break; } } } } for (i = 0; i < length; i++) { printf("Value at %d: %d\n", i, a[i]); } return 0; } 

1 , , , ,

2

Answer 28

- ,

 int[] singleArray= {300, -310, 320, 340, 350, -330, 420, 370, -360, 390, 340, -430, 320, -463, 450}; public double[] getPositive_SingleArray() { double minValue = 0; double positiveValue=0; int count=0; for (int i = 0; i < singleArrayData.length; i++) { if ( singleArrayData[i]>0) count++; } positiveSingleArrayData=new double[count]; int k=0; for (int i = 0; i < singleArrayData.length; i++) { if ( singleArrayData[i]>0){ positiveSingleArrayData[k] = singleArrayData[i]; k++; } } System.out.println("single array of positve values "+Arrays.toString(positiveSingleArrayData)); return positiveSingleArrayData; } 

Answer 29

, .

 int main() { int array[TAM], num, i=0, j=0; printf("Ingrese arreglo: "); for(i=0; i < TAM -1 && num != 0; i++) { scanf("%d", &num); array[i]=num; } for(i=0; array[i] != 0 ; i++) { j++; } Alternar(array, j); //MOSTRAR for(i=0; i < j; i++) { printf("%d ", array[i]); } return 0; } void Alternar(int array[], int j) { int i=0, aux, pasadas=1; for(pasadas=1; pasadas < j; pasadas++) { for(i=0; i < j - pasadas ; i++) { if(array[i] > 0 && array[i+1] < 0) { aux = array[i]; array[i] = array[i+1]; array[i+1] = aux; } } } } 

Answer 30

Heapsort : http://en.wikipedia.org/wiki/Sorting_algorithm