Google Interview Question
InternsCountry: CHINA
Interview Type: Phone Interview
Time: O(N), Space O(N)
public static void sortNegPosSwap(int[] arr)
{
int[] neg = new int[arr.length];
int numNeg = 0;
int currNeg = -1;
int numNegSoFar = 0;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] < 0)
{
neg[numNeg++] = arr[i];
}
}
for(int i = arr.length - 1; i >= 0; i--)
{
if(numNegSoFar != 0 && arr[i] >= 0)
{
arr[i + numNegSoFar] = arr[i];
}
if(arr[i] < 0)
{
numNegSoFar++;
}
}
for(int i = 0; i < numNeg; i++)
{
arr[i] = neg[i];
}
}
@Jason, I like this. Simple and O(n log n). I researched web and nobody claims to have O(n) time and O(1) space algorithm.
Why O(nlogn) solution when you are using O(N) extra space?
If you are given O(N) extra space then you can do it in O(N) time.
1. Scan the input array and count no. of positive elements (countP) and negative elements (countN).
2. Populate output array (extra space) .
scan input array from left to right
for i = 0 to i = size-1.
3. if arr[i] > 0 then output[countN] = arr[i]; countN++
4. if arr[i] < 0 then output[countP] = arr[i]; countP++
Please take care of boundary cases when there are no -ve or +ve elements in the array.
Time O(N) and space O(1)
public class PosiNegSort {
/**
* @param args
*/
public static void main(String[] args) {
int [] nums = {-1, 2, 4, -8, 10, 9, 100, -3, 2};
for(int i : posiNegSort(nums))
System.out.print(i + " ");
}
public static int[] posiNegSort(int [] nums){
int p = 0;
int q = 0;
while ( q < nums.length){
while (nums[p] < 0)
p++;
q = p;
while(q < nums.length && nums[q] > 0 )
q++;
if (q == nums.length)
break;
for(int i = q; i > p; i--){
int t =nums[i-1];
nums[i-1] = nums[i];
nums[i] = t;
}
}
return nums;
}
}
@doug,
if you have an array like this {1, 2, 3, 4, 5, -5, -4, -3, -2, -1}
Time is (N^2) for worse case, but still a good solution.
please let me know if this has any prob ?
/*
============================================================================
Author : novice_programmer
Description : Given an array which has n integers. It has both positive and negative integers.Now you need to sort this array in such a way that,the negative integers should be in the front,and the positive integers should at the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.Required running time complexity is O(N) and the space complexity is O(1)
Created Date : 26-JAN-2014
===========================================================================
*/
#include<stdio.h>
void sort_array(int arr[],int n)
{
int count =0;
int temp1=0;
int pos_to_fill_with_positive_num=0;
int pos1=0;
int pos2=0;
int just_moved =0;
int num_remaining=0;
for(int i=0;i<n;i++)
{
if(arr[i]<;0)
{
count++;
}
}
pos1 = count;
num_remaining=count;
for(int i=0;i<n;i++)
{
if(arr[i]<;0)
{
temp1=arr[pos2];
arr[pos2]=arr[i];
arr[i]=temp1;
pos2++;
if(pos1>=i && i>count)
{pos1++;
just_moved=1;
}
num_remaining--;
}
else
{
if(pos2==count)
break;
else if((i>=count) && (i<pos1) &&(!just_moved))
continue;
else if(just_moved)
{
just_moved=0;
temp1=arr[i];
arr[i]=arr[pos2];
arr[pos2]=temp1;
}
else
{
if(i<count)
{
temp1=arr[pos1];
arr[pos1]=arr[i];
if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
arr[pos_to_fill_with_positive_num]=temp1;
else if(pos_to_fill_with_positive_num<count)
arr[++pos_to_fill_with_positive_num]=temp1;
else
{
pos_to_fill_with_positive_num=pos2;
arr[pos_to_fill_with_positive_num]=temp1;
}
pos_to_fill_with_positive_num++;
pos1++;
}
else
{
temp1=arr[pos1];
arr[pos1]=arr[pos_to_fill_with_positive_num];
arr[pos_to_fill_with_positive_num]=temp1;
pos_to_fill_with_positive_num++;
pos1++;
}
}
}
if(num_remaining==0)
break;
}
}
void main()
{
int n = 9;
int arr[9]={-1,1,3,4,6,-3,1,-2,2};
//int arr[7]={-1,3,-2,4,5,-5,9};
//int arr[5]={-1,1,3,-2,2};
printf("\input array:");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
sort_array(arr,n);
printf("\noutput array");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
}
There is a paper showing O(n) time and O(1) space algorithm "Stable minimum space partitioning in linear time." This shouldn't be an interview question.
diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf
You shouldn't use recursion otherwise the required space won't be O(1). If you implement the same method iteratively it would be O(1) space though.
@varun merge can be done in place, so this is a O(1) space solution if we do not consider function call stack.
public int[] negSort(int[] data)
{
int negCount = 0;
int[] sorted = new int[data.Length];
for (int i = 0; i < data.Length; i++)
{
if (data[i] < 0)
{
sorted[negCount++] = data[i];
}
}
for(int i=0; i< data.Length; i++)
{
if (data[i] > 0) sorted[negCount++] = data[i];
}
return sorted;
}
If there is no repetitions then binary search tree with pre-order traversal will deliver. Again space is the con.
I really like your idea of divide and conquer. However, instead of your merging algorithm I used bubbling of positive integers from the left part to the right. I believe the space complexity is O(1), however, I really don't know the time complexity.
def lastNegIdx(arr,left,right):
for x in reversed(xrange(left,right+1)):
if arr[x]<0:
return x
def _merge(array,lIdx,middle,rIdx):
# no need to do anything if first part negative only or second only positive
if array[middle] < 0 or array[middle+1] > 0:
return
lastPositiveIdx = middle
lastNegativeIdx = lastNegIdx(array,middle+1,rIdx)
while array[lastPositiveIdx] > 0:
for x in range(lastPositiveIdx,lastNegativeIdx):
array[x],array[x+1]=array[x+1],array[x]
lastPositiveIdx-=1
lastNegativeIdx-=1
def _sortNegFirst(array,lIdx,rIdx):
if rIdx-lIdx <= 1:
return
middle = (rIdx+lIdx) / 2
print middle
_sortNegFirst(array,lIdx,middle)
_sortNegFirst(array,middle+1,rIdx)
_merge(array,lIdx,middle,rIdx)
def sortNegFirst(array):
_sortNegFirst(array,0,len(array)-1)
package util;
public class SachinTest {
private static Node head;
public static void main(String[] args) {
init();
print();
System.out.println("----------------");
Node indexNode = head;
Node temp = head;
Node focusNode = null;
while (temp != null) {
focusNode = temp.next;
if (temp.data > 0 && focusNode != null && focusNode.data < 0) {
Node adjacentNode = indexNode.next;
Node futureNode = focusNode.next;
indexNode.next = focusNode;
focusNode.next = adjacentNode;
temp.next = futureNode;
indexNode = focusNode;
continue;
}
temp = temp.next;
}
print();
}
private static void init() {
head = new Node(-1);
Node element1 = new Node(2);
Node element2 = new Node(-4);
Node element3 = new Node(-8);
Node element4 = new Node(3);
Node element5 = new Node(-10);
Node element6 = new Node(11);
Node element7 = new Node(5);
Node element8 = new Node(-21);
Node element9 = new Node(-13);
head.next = element1;
element1.next = element2;
element2.next = element3;
element3.next = element4;
element4.next = element5;
element5.next = element6;
element6.next = element7;
element7.next = element8;
element8.next = element9;
}
static void print() {
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
}
@varun, your solution does not work at all, it doesn't even address the problem.
Lets use the easiest example: [1,-1,2,-2] on your algo:
countP = 2, countN = 2
scanning input from left to right, 1 is > 0 so output[2] = 1. Increment countN for some reason. Next, -1 > 0 so output[2] = -1. Then increment countP for some reason. You already lost the first 1 in the input by overwriting it in your output.
let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
if num < 0 {
finalOutput.append(num)
}
else {
finalOutput.append(num)
}
}
finalOutput.append(contentsOf:subOutput2)
print(finalOutput)
let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
if num < 0 {
finalOutput.append(num)
}
else {
finalOutput.append(num)
}
}
finalOutput.append(contentsOf:subOutput2)
print(finalOutput)
O(nlogn) average case time, O(1) space solution:
1. count negative numbers, let's say K
2. find the first negative with index k > K
3. keep 2 pointers i,j , i tracking positives from the start, j tracking negatives starting from k. swap A[i], A[j] and switch their signs (A[i] = -A[j], A[j] = -A[i])
4. repeat steps 1,2,3 for A[0:K] and A[K,N] seperately
5. fix all signs (we know that the K first should be negatives and the rest positives)
I didn't analyze it any further,
anyone with an idea about worst case complexity?
Can some one explain what does it mean "relative position should not be changed."? Please also can some one give multiple examples to show how the output should be since the Question is not very clear.
Thanks
Unfortunately, the time complexity in worst case is O(n^2). The formula is:
T(n) = O(n) + T(k) + T(n - k), where k is the number of the negatives. So, if there is only one negative, the formula will change to T(n) = O(n) + T(n - 1) + O(1) = T(n -1) + O(n) = O(n^2).
eg. 1 2 3 4 5 6 -1
This is O(nlogn). but it can be modified in such a way that one part of the recursive tree is already sorted and you have again repeat same algo for another part.
for better performance sort longest array(+ve or -ve ) and put in recurrence the other array.
eg.
if negative count is smaller
startSearch = 0;
i = first positive index
j = first positive index where it supposed to be
swap(a[i][, a[j]);
if(a[i] < 0){
startSearch = i+1
a[i] = -a[i];
}
i = next positive index;
j++;
if(i == first index positive supposed to){
i = startSearch;
}
after this code positive array will be stable in order with only +ve numbers.
repeat same for another array where only negative should be but still not in order. the number in this array is again -ve and +ve. use same algo.
thus only one tree computation is happening same as finding nth element in randomized partition.
Method 1: O(n log(n)) for arrays
Too complicated to code but leads to O(n log n) for arrays
Start with an array A = [a1 b1 a2 b2 a3 b3 a4 b4 .... ak bk]
where ai and bi are subarrays of positive and negative numbers.
assume ni = len(ai) and mi = len(bi)
Observation:
[a1 b1] --> [b1 a1] in O(max(ni, mi)) which is obtained by repeatedly swaping the first, second, ... elements.
For ni = mi it is obvious. For ni > mi, do it for the first mi, then ignore the first mi since they are in place, do it [ni - mi, mi] positive ones and put them in order. Repeat until you finish after ni swaps.
So recursively do this:
Take [a1 b1 a2 b2] -> [b1 a1 a2 b2] -> [b1 b2 a1 a2]
this is done in max(n1, m1) + max(n1 + n2, m2) < 2n1 + n2 + m1 + m2
For k pairs of [ai bi], we find k / 2 new pairs pairs.
Reapeat the procedure. Note that in the second run, your new value of n1 is (n1 + n2) from previous step.
The same for m1.
For k pairs we need the time complexity T(k) = k / 2 * (2n1 + n2 + m1 + m2) + T(k / 2).
Put averages here: (E[ni] = E[mi] = n / k.
ET(k) = k / 2 * (5 n / k) + ET(k / 2) = 2.5 n + ET(k / 2).
For k / 2, the sizes of ni and mi are doubled. So we have
ET[k] = 2.5 n + 2.5 n + .... + 2.5 log2(k) times.
Then ET[k] = O(nlog(k)).
Finally, average over "k". Note that k is O(n) for random arrays. Therefore, the overall complexity = O(n log(n))
Repeat it for all the k / 2 pairs.
////////////////////
Method 2: For arrays, simple code O(n^2)
void special_sort(int* arr, int length)
{
// Sweep from back to front
// If a number is negative and its previous number is positive, swap them
// continue sweeping until no swaps are made
bool swapped = false;
while(swapped)
{
swapped = true;
for (int k = length - 1; k > -1; k--)
{
if (k > 0)
{
if (arr[k] < 0)
{
if (arr[k - 1] > 0)
{
int tmp = arr[k - 1];
arr[k - 1] = arr[k];
arr[k] = tmp;
swapped = false;
}
}
}
}
}
}
Method 3: Data stored in linked list O(n)
struct LinkedList {
int value;
LinkedList* next;
};
LinkedList* special_sort(LinkedList* arr)
{
// If the first element is not negative, insert a negative number
// Set pos_last_neg as pointer to the first elemnt of array
// Sweep through the list (using pointer pos)
// if the number is negative and pos != pos_last_neg->next, move the element at pos to pos_last_neg;
LinkedList* head = new LinkedList;
head->value = -10000000;
head->next = arr;
LinkedList* last_neg = head;
LinkedList* pos = head->next;
LinkedList* prev = last_neg;
while(pos != nullptr)
{
if (pos->value < 0)
{
if (prev != last_neg)
{
// There are some positive elements in between
LinkedList *p1 = pos;
prev->next = pos->next;
pos->next = last_neg->next;
last_neg->next = pos;
last_neg = pos;
pos = prev->next;
pos = prev->next;
continue;
}
}
prev = pos;
pos = pos->next;
}
return head->next;
}
void main()
{
LinkedList* head = GetLinkedListFromArray({......});
PrintList(head);
head = special_sort(head);
PrintList(head);
}
import java.util.Arrays;
public class NegativeAndPositive {
private static final int[] array = new int[] { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };
public static void main(String[] args) {
for (int i = 0, j = array.length - 1; i < j;) {
if (array[i] < 0) {
i++;
continue;
}
if (array[j] > 0) {
j--;
continue;
}
swap(i, j);
}
System.out.println(Arrays.toString(array));
}
private static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
import java.util.Arrays;
public class NegativeAndPositive {
private static final int[] array = new int[] { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };
public static void main(String[] args) {
for (int i = 0, j = array.length - 1; i < j;) {
if (array[i] < 0) {
i++;
continue;
}
if (array[j] > 0) {
j--;
continue;
}
swap(i, j);
}
System.out.println(Arrays.toString(array));
}
private static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
So you only have to swap the last item in a run of positives or negatives. So you only have to keep an index of the last index of the previous signage run. The following code is O(N) and has O(1) space.
I don't handle the 0 case, because it is unclear what to do with that case.
int lastRunIndex = 0;
while (array[lastRunIndex] < 0 && lastRunIndex < array.Length) { lastRunIndex++; };
for (int i = lastRunIndex; i < array.Length; i++)
{
if (array[i] < 0 == array[lastRunIndex] < 0)
continue;
else
{
int temp = array[i];
array[i] = array[lastRunIndex];
array[lastRunIndex] = temp;
lastRunIndex++;
}
}
we need two arrays ary1, ary2 ; both size of n, for positive values and negative values
traverse the target array
if current value is negative
write it to ary1
else write it to ary2
rewrite target array first with ary1 then with ary2
The fact that ary1 and ary2 are built up as we read the target array from bgn to end guarantees that relative positions between values of the same sign would not change
O(n) and O(n)
void sort(int arr[], int n) {
int dup[n];
memcpy(dup, arr, sizeof(int) * n);
int nextNonNeg = 0;
int i = 0;
for (i, nextNonNeg; i < n; i++, nextNonNeg++)
if (arr[i] > 0)
break;
for (i; i < n; i++) {
if (arr[i] < 0) {
swap(arr, i, nextNonNeg);
nextNonNeg++;
}
}
int lastNeg = n-1;
i = n-1;
for (i, lastNeg; i >= 0; i--, lastNeg--)
if (dup[i] < 0)
break;
for (i; i >= 0; i--) {
if (dup[i] > 0) {
swap(dup, i, lastNeg);
lastNeg--;
}
}
for (int i = 0; i < n; i++)
if (arr[i] > 0)
arr[i] = dup[i];
}
int main() {
int arr[] = { -1, 1, 3, -2, 2, -3, -88, -5, 55, -9 };
int n = 10;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
sort(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
Nice! This is quite possibly the best solution possible, as doing it with O(1) memory is impossible.
public class SpecialSort {
public static void main(String[] args) {
int[] data = {-1, 1, 3, -2, 2};
int length = data.length - 1;
int[] specialSort = specialSort(data, length);
for(int i=0; i<specialSort.length; i++){
System.out.printf("%d ", specialSort[i]);
}
}
private static int[] specialSort(int[] data, int length) {
for(int i=0; i<length-1; i++){
for(int k=0; k<length-i; k++){
if(data[k] > 0 && data[k+1] < 0){
int temp = data[k];
data[k] = data[k+1];
data[k+1] = temp;
}
}
}
return data;
}
}
Definitely there are O(n) time complexity and O(1) space complexity algorithms. At least there are two.
The first one uses cycle leader algorithm, check following links
geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/
The second one is
geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/
For the second, the algorithm in link is O(N^2), but it's very easy to change is to O(N)
The n^2 solution would be:
Keep trace of a first met positive number = P. If you find a negative number = N, and P is set, then store P into T, insert value of N into positon P, shift the table right from P to N positon, insert T into P+1.
Can we really do it in O(n) without extra space?
public class NegativePositiveSort
{
public static void main(String[] args) {
int[] array = {-1,1,3,-2,2};
int positiveIndex=-1;
int negativeIndex=-1;
// Find 1st positive index
for(int i=0;i<array.length;i++) {
if(array[i]>=0) { positiveIndex=i; break;}
}
// Find 1st negative index after positive index
for(negativeIndex=positiveIndex+1;negativeIndex<array.length && array[negativeIndex]>=0;negativeIndex++);
while(positiveIndex>-1 && negativeIndex<array.length) {
swap(array,positiveIndex,negativeIndex);
positiveIndex++;
for(negativeIndex=positiveIndex+1;negativeIndex<array.length && array[negativeIndex]>=0;negativeIndex++);
}
for(int i=0;i<array.length;i++) System.out.print(array[i]+",");
}
public static void swap(int[] array, int tgt, int src) {
while(src>tgt) {
array[src-1] = array[src] ^ array[src-1];
array[src] = array[src] ^ array[src-1];
array[src-1] = array[src] ^ array[src-1];
src--;
}
}
}
This should work. how to compute the time complexity ?
void sortRelative(int[] m){
int insertNegative = 0;
for (int index = 0; index < m.length; index++){
if (m[index] < 0 && m[insertNegative] >= 0){
int temp = m[index];
for (int k = index; k > insertNegative; k--){
m[k] = m[k-1];
}
m[insertNegative++] = temp;
} else {
if (m[insertNegative] < 0){
insertNegative++;
}
}
}
}
Take this
[1, -1, 2, -2,...,k, -k]
In order to move the first negative to the first position you need to shift 1 positive to the right. Now you get
[-1, 1, 2, -2,...k, -k]
To move the second negative to the second postition you need to shift 2 positives to the right. Finally, to shift the kth negative to the kth position you need to shift k positives to the right.
In total that is 1 + 2 +... + k = k*(k-1)/2 = O(k^2) = O(n^2) (since k = n/2 ) operations.
@fire It's very easy for general cases.
If u have a single level loop in ur program then it is o(n). If there is a loop inside the loop(2 level), then its O(n^2). If inner loop executes only log n times(approx) then it is O(nlogn). If u hav loop inside loop inside loop then its O(n^3) and so on.
//Author : A.Nasimunni
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter the length of the array : ");
scanf("%d",&n);
int a[n],b[n];
int i=0;
printf("\n\n\tEnter the elements into array \n");
for(i=0;i<n;i++)
{printf("\t\t Enter : ");
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}
for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}
for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}
//Author : A.Nasimunni
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter the length of the array : ");
scanf("%d",&n);
int a[n],b[n];
int i=0;
printf("\n\n\tEnter the elements into array \n");
for(i=0;i<n;i++)
{printf("\t\t Enter : ");
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}
for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}
for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}
import java.util.ArrayList;
class Test {
public static void main(String[] args){
int[] arr = {-1, 1, 3, -2, 2,5,-7,-6};
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<arr.length;i++){
if(arr[i]<0){
list.add(arr[i]);
}
}
for(int i=0;i<arr.length;i++){
if(arr[i]>0){
list.add(arr[i]);
}
}
System.out.println(list);
}
}
public int[] sortInOrder(int[] data){
int pos=0;
int negPos=0;
for (pos=0;pos<data.length;) {
if(data[pos]>=0){
while(negPos<data.length && data[negPos]>=0 ){
negPos++;
}
if(negPos==data.length)
break;
while(negPos>pos){
int temp=data[negPos];
data[negPos]=data[negPos-1];
data[negPos-1] = temp;
negPos--;
}
}
negPos++;
pos++;
}
return data;
}
public int[] sortInOrder(int[] data){
int pos=0;
int negPos=0;
for (pos=0;pos<data.length;) {
if(data[pos]>=0){
while(negPos<data.length && data[negPos]>=0 ){
negPos++;
}
if(negPos==data.length)
break;
while(negPos>pos){
int temp=data[negPos];
data[negPos]=data[negPos-1];
data[negPos-1] = temp;
negPos--;
}
}
negPos++;
pos++;
}
return data;
}
public int[] sortInOrder(int[] data){
int pos=0;
int negPos=0;
for (pos=0;pos<data.length;) {
if(data[pos]>=0){
while(negPos<data.length && data[negPos]>=0 ){
negPos++;
}
if(negPos==data.length)
break;
while(negPos>pos){
int temp=data[negPos];
data[negPos]=data[negPos-1];
data[negPos-1] = temp;
negPos--;
}
}
negPos++;
pos++;
}
return data;
}
If 0 exists, partition around it..Otherwise, insert a 0 and then partition around it. Please confirm if it's possible to add a 0 to the array in O(1) space.
You don't need to physically add the zero. But it won't work. Remember that this is an array and insertion not possible. You can only swap.
Ex: {1 -1 2 -2} turns into {-1 -2 2 1}
Code on C#, I think this is O(n)
class Program
{
static void Main(string[] args)
{
int[] array = new int[] { -1, 1, 3, -2, 2 };
SortPosNeg(array);
Console.WriteLine();
foreach (var i in array)
{
Console.Write(i + " ");
}
Console.ReadLine();
}
static void SortPosNeg(int[] array)
{
int totalNegatives = 0;
foreach (var i in array)
{
if (i < 0)
totalNegatives++;
}
//create arrays for neg and pos
int[] negArray = new int[totalNegatives];
int[] posArray = new int[array.Length - totalNegatives];
int negHelper = 0;
int posHelper = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] < 0)
{
negArray[negHelper] = array[i];
negHelper++;
}
else
{
posArray[posHelper] = array[i];
posHelper++;
}
}
//put all negatives from 0 though totalNegative - 1
for(int i = 0; i < totalNegatives; i++)
{
array[i] = negArray[i];
}
for (int i = 0; i < posArray.Length - 1; i++)
{
array[totalNegatives + i] = posArray[i];
}
}
}
int main() {
int arr[7] = {-1,-1,-3,-3,-2,-2,-8};
int size = sizeof(arr)/sizeof(*arr);
cout<<size<<endl;
int n=0;
for(int i=0;i<size;i++) {
if(arr[i]<0) {
int temp = arr[i];
int j=i;
while(j>n){
arr[j] = arr[j-1];
j--;}
arr[n++]= temp;}}
for(int i=0;i<size;i++) {
cout<<arr[i]<<" "; }
return 0;}
public class array2 {
public static void printarray(String name,int [] src)
{
System.out.println(name);
for(int i=0;i<src.length;i++)
{
System.out.print(src[i]+" ");
}
}
public static void main(String args[])
{
int src[]={-1,1,3,-2,2,6,9,7,4,-2,-7,-9,-10};
printarray("Source",src);
int i,j=0;
int a[]=new int[src.length];
for(i=0;i<src.length;i++)
{
if(src[i]<0)
{
a[j]=src[i];
j++;
}
}
for(i=0;i<src.length;i++)
{
if(src[i]>=0)
{
a[j]=src[i];
j++;
}
}
System.out.println();
printarray("Final",a);
}
}
public class array2 {
public static void printarray(String name,int [] src)
{
System.out.println(name);
for(int i=0;i<src.length;i++)
{
System.out.print(src[i]+" ");
}
}
public static void main(String args[])
{
int src[]={-1,1,3,-2,2,6,9,7,4,-2,-7,-9,-10};
printarray("Source",src);
int i,j=0;
int a[]=new int[src.length];
for(i=0;i<src.length;i++)
{
if(src[i]<0)
{
a[j]=src[i];
j++;
}
}
for(i=0;i<src.length;i++)
{
if(src[i]>=0)
{
a[j]=src[i];
j++;
}
}
System.out.println();
printarray("Final",a);
}
}
The idea here is when we encounter a positive number in the slot we're examining, we find the next negative number, store it in a temp variable, then shuffle over all the positives. Finally, insert the saved negative number into the current slot.
i.e. if we had: [ -1, <1>, 2, 3, 4, -2, ..]
When we encounter the 1, we search forward til we find the index of the -2, and we store that value. We then copy between our current index and that index:
[ -1, <1>, 1, 2, 3, 4, ....]
Then finally insert the saved number into our current location.
[-1, <-2>, 1, 2, 3, 4, ...]
Then we move onto examining the next index.
<strike>This is O(n) in the worst case, because in [3,2,1,-3,-2,-1], we perform n/2 shuffles, where each shuffle swaps at most n/2 elements. n/2 * n/2 = O(n).</strike>
It's actually O(n^2), thanks for the correction lxduan.
def find_next_negative(i, arr):
while i < len(arr):
if arr[i] < 0:
return i
i = i + 1
return None
def sort_relative(arr):
next_negative_index = None
for current_index in xrange(0, len(arr)):
if arr[current_index] < 0:
pass
else:
# find next negative
next_negative_index = find_next_negative(current_index+1, arr)
if next_negative_index:
# copy it to this location, and bump everything up
value_to_copy = arr[next_negative_index]
copy_index = next_negative_index - 1
while copy_index >= current_index:
arr[copy_index+1] = arr[copy_index]
copy_index -= 1
arr[current_index] = value_to_copy
else:
break
return arr
print sort_relative([3,2,1,-1]) == [-1, 3, 2, 1]
print sort_relative([11, 1, 3, -2, -5, 2]) == [-2, -5, 11, 1, 3, 2]
print sort_relative([3,2,1,-3,-2,-1]) == [-3,-2,-1,3,2,1]
Yep you're right. It's O(n) if you store an extra array with all the indices of negative numbers, but then that's O(n) space. My bad.
Same as I thought, actually it can be optimized,
the current_index can jump directly to the next_negative_index previously found.
For example:
[ -1, <1>, 2, 3, 4, -2, -3, ..]
suppose after first iteration, we get:
[ -1, -2 , 1, 2, 3, 4, -3 ..]
then we can let current_index jump to <4> (the position of -2 before swap) directly instead of starting from <1> , and then repeat the iteration.
This is O(n) regardless of the swapping part...
1.arrange the first half as negative and second half as negative
2.then call quick sort for first half of the array check for abs(i) pos with abs(j)
3.then call quick sort for the second half of the array
the complexity is O(n) for arranging positive and negative numbers and O(nlogn)+O(nlogn) for sorting... still can we have better solution :)
public class google {
public static void main(String[] args) {
int[] a={-1,1,3,-2,2};
int neg=0;
int pos=0;
for(int i=0;i<a.length;i++){
if(a[i]<0)
neg++;
else
pos++;
}
int countneg=0;
int i=0;
int j=1;
int k=0;
int temp=0;
while(countneg<neg){
if(a[i]<0){
countneg++;
i++;
}
else{
j=i;
k=i;
while(a[k]>0){
k++;
}
temp=a[j];
a[j]=a[k];
for(int z=k;z>j;z--){
a[z]=a[z-1];
}
a[j+1]=temp;
countneg++;
i++;
}
}
for(i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
}
// anshumandvyas@gmail.com
public class google {
public static void main(String[] args) {
int[] a={-1,1,3,-2,2};
int neg=0;
int pos=0;
for(int i=0;i<a.length;i++){
if(a[i]<0)
neg++;
else
pos++;
}
int countneg=0;
int i=0;
int j=1;
int k=0;
int temp=0;
while(countneg<neg){
if(a[i]<0){
countneg++;
i++;
}
else{
j=i;
k=i;
while(a[k]>0){
k++;
}
temp=a[j];
a[j]=a[k];
for(int z=k;z>j;z--){
a[z]=a[z-1];
}
a[j+1]=temp;
countneg++;
i++;
}
}
for(i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
}
#include <stdio.h>
void swapT(int* a,int* b, int *c){
int temp=*c;
*c=*b;
*b=*a;
*a=temp;
}
#define N 5
int main(){
int i, pos, mid, neg = 0;
int a[] = {-1,1,3,-2,2};
for (i = 0; i < N; i++) printf (" %d ", a[i]);
printf ("\n");
int totNeg = 0;
for (i = 0; i < N; i++){
if (a[i] < 0) totNeg++;
}
mid = totNeg;
pos = totNeg;
while (totNeg > 0){
if (a[neg] < 0){
neg++;
totNeg--;
}
else {
while (a[pos] >= 0) pos++;
swapT(&a[neg], &a[mid], &a[pos]);
neg++;
pos++;
mid++;
totNeg--;
}
}
for (i = 0; i < N; i++) printf (" %d ", a[i]);
printf ("\n");
return 0;
}
#include <stdio.h>
void swap(int *, int *);
main()
{
int array[6] = {
1,2,3,4,-2,-3
};
int a = 0, b = 5;
while (a <= b) {
while (array[a] < 0)
a++;
while (array[b] > 0)
b--;
if (b -a > 1) {
swap(&array[a], &array[b]);
a++;
b--;
}
}
int i = 0;
for (; i < 6; i++)
printf("%d ", array[i]);
printf("\n");
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
};
My apology, previous code is not work for some special test data, so i edit and add the second one.
#include <stdio.h>
void swap(int *, int *);
main()
{
int array[6] = {
-1,1,3,-2,2,4
};
int a = 0, b = 5;
while (b -a > 1) {
while (array[a] < 0)
a++;
while (array[b] > 0)
b--;
swap(&array[a], &array[b]);
a++;
b--;
}
int i = 0;
for (; i < 6; i++)
printf("%d ", array[i]);
printf("\n");
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
};
void rearrange(vector <int> &nums)
{
vector<int> temp;
int start_pos = 0;
for(int i=0;i<nums.size();++i)
{
if(nums[i] <0 )
nums[start_pos++] = nums[i];
else
temp.push_back(nums[i]);
}
for(int i=0;i<temp.size();++i)
nums[start_pos++] = temp[i];
}
It's O(N) time and (N) memory , i can't find solution with less memory.
public void sortIntegers(int[] intarray)
{
for(int h=0;h<intarray.length;h++)
System.out.print(intarray[h]+ " ");
int lastnegative = 0;
for(int i=0; i< intarray.length;i++)
{
if(intarray[i]<0)
{
swap(intarray,lastnegative,i);
lastnegative = lastnegative+1;
}
}
System.out.println();
for(int m=0;m<intarray.length;m++)
System.out.print(intarray[m]+ " ");
}
void swap(int[] intarray, int lnegative, int j)
{
int temp = intarray[j];
for(int k = j-1;k>=lnegative;k--)
{
intarray[k+1] = intarray[k];
}
intarray[lnegative] = temp;
}
we can also use queue data structure like this in Java
public class Sort {
public static void sortArray(int[] a)
{
int N = a.length;
Queue<Integer> q1 = new Queue<Integer>();
Queue<Integer> q2 = new Queue<Integer>();
for (int i = 0; i<N; i++)
{
if(a[i] < 0 ) q1.enqueue(a[i]);
else q2.enqueue(a[i]);
}
int i = 0;
while (!q1.isEmpty())
a[i++] = q1.dequeue();
while(!q2.isEmpty())
a[i++] = q2.dequeue();
}
public static void main(String[] args)
{
int[] a = {-1,1,3,-2,2};
sortArray(a);
for (int i =0; i<a.length;i++)
System.out.println(a[i]);
}
}
If this wasn't an array it would be doable!
if you had a linked list you could easily do this in one pass!
Just link the negative list together then link the last item with the first positive.
LinkedListNode current = list.root;
LinkedListNode prevPos = null;
LinkedListNode firstPos = null;
LinkedListNode prevNeg = null;
while (current != null && current.next != null)
{
if (current.val >= 0)
{
if (prevPos == null)
{
firstPos = current;
}
else
{
prevPos.next = current;
}
prevPos = current;
}
else
{
if (prevNeg == null)
{
list.root = current;
}
else
{
prevNeg.next = current;
}
prevNeg = current;
}
current = current.next;
}
if (prevNeg == null)
list.root = firstPos;
else
prevNeg.next = firstPos;
if (prevPos != null)
prevPos.next = null;
Otherwise, I do not believe this problem is solvable.
[ o(1) space, by time complexity is not o(n) :( ]
private void start( int[] a ) {
int n = -1, p = -1; // set positive and negative count
for ( int i = 0; i < a.length; i++ ) {
if ( a[i] < 0 ) {
n = i;
if ( n > p && p >= 0 ) {
move( a, p, n );
p++; // increment positive index which will be used for next negative value set.
}
} else if ( p <= 0 ) { // get first positive number index
p = i;
}
}
System.out.println( Arrays.toString( a ) );
}
/**
* replace first positive number with negative number. and then move remaining positive numbers by 1 towards right.
* For { -1, 1, 3, -2, 2 }, s=1, and e=3, replace a[s] with a[e], and set a[s+1] with a[s], increment s by 1. do it
* until u reach end 'e'
*
* @param s start index
* @param e end index
*/
private static void move( int[] a, int s, int e ) {
int temp = a[s];
a[s] = a[e];
for ( int i = s + 1; i <= e; i++ ) {
int t2 = a[i];
a[i] = temp;
temp = t2;
}
}
#include<stdio.h>
void swap(int*,int*);
void insert(int*, int*);
int main()
{
int arr[5] = {-1,1,3,-2,-4};
int negcount = 0, i, p;
/*Counting negetive numbers*/
for(i=0;i<5;i++)
if(arr[i]<0)
negcount++;
/*p points to the next location to insert positive number */
p = neg;
/*Main algo part*/
for(i=0;i<neg;i++)
{
if(arr[i] >0)
{
printf("swapping\n");
swap(&arr[i], &arr[p]);
p++;
if(arr[i] <= 0)
insert(&arr[i], &arr[neg-1]);
i--;
}
}
/*Print The Result*/
for(i=0;i<5;i++)
printf("%d\t", arr[i]);
printf("\n");
}
This is like merge sort with a twist. The best solution I can think of for an O(1) space complexity is O(nlogn) time complexity. The trick is to think in terms of merge sort and perform matrix rotation through reverse
public static int order(int[] x, int startidx, int endidx){
if(startidx==endidx) return x[startidx] >= 0 ? 1 : 0;
else{
int p1 = order(x, startidx, (startidx+endidx)/2);
int p2 = order(x, (startidx+endidx)/2 + 1, endidx);
//order (only if the first half has positive items And second half has negative items)
if(p1 != 0 && p2!= (endidx - (startidx + endidx)/2)){
int fst_pidx_1;
fst_pidx_1 = (startidx+endidx)/2 - p1 +1;
int lst_nidx_2 = endidx - p2;
//We basically want to perform a rotation operation for part of the array
//This can be done in O(n) if we use the reverse function
int shftVal = endidx - (startidx+endidx)/2 - p2;
reverse(x, fst_pidx_1, lst_nidx_2);
reverse(x, fst_pidx_1, fst_pidx_1 + shftVal - 1);
reverse(x, fst_pidx_1 + shftVal, lst_nidx_2);
}
//return p1 + p2
return (p1 + p2);
}
}
//This function reverses part of the array
public static void reverse(int[] x, int begin, int end)
{
int lst = end;
for(int i = begin; i <= (begin+end)/2; i++){
int tmp =x[i];
x[i] = x[lst];
x[lst] = tmp;
lst--;
}
}
T(n) = 2T(n/2)+o(n). o(n) being the rotation function. Then time complexity is O(nlogn). I dont really think any type of sorting can occur in O(n) but if someone come up with a solution, thatd be good.
def swap(list,idx1,idx2)
t = list[idx1]
list[idx1] = list[idx2]
list[idx2] = t
list
end
def separate(list)
idx = list.length
idx -= 1
while(idx > 0) do
iidx = idx
if list[idx] < 0
pidx = idx - 1
while(pidx >= 0) do
if list[pidx] > 0
list = swap(list,idx,pidx)
if idx < iidx
iidx += 1
end
break
else
idx = pidx
end
pidx -= 1
end
end
idx = iidx - 1
end
list
end
list = [1,2,-3,4,6,-9,10]
puts separate(list).join(',')
public class GoogleSort {
public static void main(String args[]) {
int[] in = {-1,2,3,-2,4,-5}; //input array
int temp;//space1
for (int i = 0; i < in.length; ) {
if(in[i]<0) i++;
else{
temp=i;
while(temp < in.length && in[temp]>0 )
temp++;
if(temp >= in.length)
break;
while(i < temp ){
//XOR swap
in[temp] ^= in[temp -1];
in[temp-1] ^= in[temp];
in[temp] ^= in[temp -1];
temp --;
}
i = temp;
}
}
for (int i = 0; i < in.length; i++) {
System.out.println(in[i]);
}
}
}
I haven't figured out the O(N) solution given an array, but it'd be easy to do with a linked list. Then you could just keep track of pointers for the end of the positive and negative lists, and then connect them in the end, with O(1) space (all you'd need is three pointers, one for the current position, one for the start of the positive list and one for the start of the negative).
This is the best I got keeping the space on O(1) and O(n) without zeros
Wasn't sure by the description if the array has zeros in it so added code to handle but not without extra time
<script>
var arr = [100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2];
function sortNegative(arr) {
var negPos=-1;
var hasZero = false;
i=0;
while (i<arr.length) {
if (arr[i] < 0) {
tmp = arr[i];
negPos++;
//move all positives forward
for (j=i; j>negPos; j--) {
arr[j] = arr[j-1];
}
arr[negPos] = tmp;
}
if (arr[i] == 0)
hasZero = true;
i++;
}
if (hasZero) {
i=negPos;
while (i<arr.length) {
if (arr[i] == 0) {
tmp = arr[i];
negPos++;
//move all positives forward
for (j=i; j>negPos; j--) {
arr[j] = arr[j-1];
}
arr[negPos] = tmp;
}
i++;
}
}
return arr;
}
document.write(arr + '<br>');
document.write(sortNegative(arr));
</script>
function for the solution is given below,it solves the problem in O(n) time:
int arrange_numbers(int *ARRAY,int no_of_elements)
{
int NEW_ARRAY[no_of_elements];
int i,j=0;
for(i=0;i<no_of_elements;i++)
{
if(*ARRAY <0 )
{
NEW_ARRAY[j] = *ARRAY;
j++;
}
ARRAY++;
}
// loop 1 ends,arrangin all negative numbers correctly;
}
for(i=0;i<number_of_elements;i++)
{
if(*ARRAY > 0)
{
NEWARRAY[j]=*A;
j++;
}
ARRAY++;
}
//loop 2 ends arranging all positive numbers correctly
return NEW_ARRAY;
}
/*
Question ID: 5201559730257920
Give you an array which has n integers,it has both positive and negative integers.
Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.
Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
O(n)time complexity and O(1) space complexity is perfect.
*/
public class sol5201559730257920{
static int length;
static int[] a;
static int start;
static int end;
static int total_n;
public static void sort(){
while(start < total_n){
if(a[start] < 0)
start ++;
else{
a[end] = a[start] + (a[start] = a[end]) - a[end]; // swap;
end ++;
}
}
}
public static void display(){
for(int i = 0; i < length; i ++){
System.out.print(a[i] + " ");
}
}
public static void main(String[] args){
length = args.length;
a = new int[length];
for(int i = 0; i < length; i ++){
a[i] = Integer.parseInt(args[i]);
if(a[i] < 0) // count total negative numbers
total_n ++;
}
end = total_n; // index where positive num starts
sort();
display();
}
}
public static void sort(int[] array){
int cout_pos = 0; int count_neg = 0;
int sum_pos = 0; int sum_neg = 0;
int neg_co = 1; int pos_co = 1;
for(int i=0; i!=array.length; ++i){
if(array[i] < 0){
neg_co *= 10;
count_neg++;
sum_neg += -1 * array[i] * neg_co;
}
else{
pos_co *= 10;
cout_pos++;
sum_pos += array[i] * pos_co;
}
}
//put them back in the array
for(int i = count_neg -1; i!=0; --i){
array[i] = -1*(sum_neg / neg_co);
sum_neg -= array[i] * neg_co;
neg_co /= 10;
}
for(int i = array.length-1; i!=count_neg-1; --i){
array[i] = sum_pos / pos_co;
sum_pos -= array[i] * pos_co;
pos_co /= 10;
}
}
public static void sort(int[] array){
int cout_pos = 0; int count_neg = 0;
int sum_pos = 0; int sum_neg = 0;
int neg_co = 1; int pos_co = 1;
for(int i=0; i!=array.length; ++i){
if(array[i] < 0){
neg_co *= 10;
count_neg++;
sum_neg += -1 * array[i] * neg_co;
}
else{
pos_co *= 10;
cout_pos++;
sum_pos += array[i] * pos_co;
}
}
//put them back in the array
for(int i = count_neg -1; i!=0; --i){
array[i] = -1*(sum_neg / neg_co);
sum_neg -= array[i] * neg_co;
neg_co /= 10;
}
for(int i = array.length-1; i!=count_neg-1; --i){
array[i] = sum_pos / pos_co;
sum_pos -= array[i] * pos_co;
pos_co /= 10;
}
}
public static void sort(int[] array){
int cout_pos = 0; int count_neg = 0;
int sum_pos = 0; int sum_neg = 0;
int neg_co = 1; int pos_co = 1;
for(int i=0; i!=array.length; ++i){
if(array[i] < 0){
neg_co *= 10;
count_neg++;
sum_neg += -1 * array[i] * neg_co;
}
else{
pos_co *= 10;
cout_pos++;
sum_pos += array[i] * pos_co;
}
}
//put them back in the array
for(int i = count_neg -1; i!=0; --i){
array[i] = -1*(sum_neg / neg_co);
sum_neg -= array[i] * neg_co;
neg_co /= 10;
}
for(int i = array.length-1; i!=count_neg-1; --i){
array[i] = sum_pos / pos_co;
sum_pos -= array[i] * pos_co;
pos_co /= 10;
}
}
public static void main(String[] args){
int []A={1,-2,-3,4,5,6,7,8,-9,-10,11,12,13,-14,-15,-16,-17,-18, 19};
int l=A.length;
int j=l-1;
int i=0;
int [] b=sortArr(A, i, j);
for(i=0; i<l; i++){
System.out.print(b[i]+" ");
}
}
static int [] sortArr(int []A, int i, int j){
while(A[j]>=0 & j>-1){
j--;
}
int k=j;
while(A[k]<0 && k>-1){
k--;
}
for(int p=k; p<j; p++){
int temp=A[p];
A[p]=A[p+1];
A[p+1]=temp;
}
if(k==0){
return A;
}
j--;
k=j;
return sortArr(A, i, j);
}
}
1. Multiply all negative numbers by 10 and odd numbers by 10 and add 1
2. sort the array using stable sorting algorithm considering only the last digit of the number
-10 -20 11 31 21
3. divide all elements by 10
-1 -2 1 3 2
This is O(N) and O(1)
OR
2. O(NlogN) soln - sort using any standard algo considering only the last digit
def rearrange(src, tgt):
src_pos = {}
for i, s in enumerate(src): # O(n)
src_pos[s] = i
zero = src.index(0) # O(n)
for i, t in enumerate(tgt): # n times O(1)
if t == 0 or t == src[i]:
continue
swap(src, zero, i)
swap(src, src_pos[t], i)
zero = src_pos[t]
print src
I know time complexity is O(n^2).
#include<iostream>
using namespace std;
int main()
{
int a[7]={2,-3,3,5,-6,2,-9},j,n=0;
for (int i = 0; i < 7; ++i)
{
if (a[i]<0)
{ int temp=a[i];
for (j=i;j>n;j--)
a[j]=a[j-1];
a[n++]=temp;
}
}
for (int i = 0; i < 7; ++i)
{
cout<<a[i]<<endl;
}
system("pause");
}
public static void specialSort(int[] arr){
if (arr == null) throw new NullPointerException();
if(arr.length == 1) return;
int temp = arr[0];
int pos, neg;
int n = arr.length;
pos = neg = 0;
while(neg < n){
for(int k = neg;pos < n && neg < n;k++){
if(arr[neg] >= 0){
//check if the last element in the array is
// a positive number. If so we are done
if (neg < n-1){
// move the positive numbers to the right
// if you haven't reached the end of
// the array
int exch = arr[neg];
arr[neg] = temp;
temp = exch;
}
neg++;
}
if(arr[pos] < 0) pos++;
if(neg >= n) break; //no more negative numbers
if(arr[pos] >= 0 && arr[neg] < 0) break;
}
if(neg < n){//if neg > n then the last element of
// the array is a positive number and we are done
if(neg > pos ){
if(arr[neg] < 0){
arr[pos] = arr[neg];
arr[neg] = temp;
pos = neg;
}
}
else neg = pos; // make sure we continue at
// the higher index
neg++;
temp = arr[pos];
}
}
}
I believe I have achieved O(n) time and O(1) extra space complexity:-
Let us maintain such an invariant at all times:
The first n numbers of the array are negative.
The next p numbers of the array are positive.
So let the array look like this:
-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve ....
n times p times remaining
Now let us find n1 and p1 such that
-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve -ve -ve ... -ve; +ve +ve +ve .... +ve; -ve ....
n times p times n1 times p1 times remaining
Now let us try to 'consume' the n1 and p1 elements in the n and p elements. We can do this by swapping the 2nd and 3rd blocks(p and n1 elements). If we can do this in O(p+n1) time, then increment n to be n+n1 and p to be p+p1 and keep doing this, we should be able to do this for the whole array in O(n) time.
So the challenge is this:
x1 x2 x3 ... xp; y1 y2 y3 ... yq
has to be rearranged to form
y1 y2 y3 ... yq; x1 x2 x3 ... xp
in O(p+q) time.
If p==q, then it's easy. Just keep on swapping x1, y1; x2, y2 and so on.
If p!=q, suppose p>q without loss of generality. Then swap the elements y1..yq and x1..xq to get
y1 y2 y3 ... yq xq+1 xq+2 ... xp x1 x2 x3 ... xq
and repeat the procedure for the subarray xq+1 xq+2 ... xp; x1 x2 x3 ... xq
This way, it is possible to swap an unequal number of elements in place in O(n) time and O(1) extra space.
Code:
#include<stdio.h>
#include<stdlib.h>
void swap(int* arr, int pos1, int pos2) {
arr[pos1] ^= arr[pos2];
arr[pos2] ^= arr[pos1];
arr[pos1] ^= arr[pos2];
}
void swap_in_place(int* arr, int ff, int fl, int sf, int sl) {
if(ff==fl+1 || sf==sl+1) {
return;
}
if(fl-ff>sl-sf) {
int lesser = sl-sf+1;
int i;
for(i=0; i<lesser; i++) {
swap(arr, ff+i, sf+i);
}
swap_in_place(arr, ff+lesser, fl, sf, sl);
}
else{
int lesser = fl-ff+1;
int i;
for(i=0; i<lesser; i++) {
swap(arr, fl-i, sl-i);
}
swap_in_place(arr, ff, fl, sf, sl-lesser);
}
}
void print_array(int* arr, int size) {
int i;
for(i=0; i<size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void swap_pos_neg(int* arr, int size) {
int neg=0;
int pos=0;
while(neg<size && arr[neg]<0) {
neg++;
}
pos=neg;
while(pos<size && arr[pos]>0) {
pos++;
}
if(pos>=size) return;
while(pos<size) {
int new_neg=pos;
while(new_neg<size && arr[new_neg]<0) {
new_neg++;
}
int new_pos = new_neg;
while(new_pos<size && arr[new_pos]>0) {
new_pos++;
}
swap_in_place(arr, neg, pos-1, pos, new_neg-1);
neg += new_neg-pos;
pos = new_pos;
}
}
void main() {
int size = 5;
int arr[] = {-1, 1, 3, -2, 2};
print_array(arr, size);
swap_pos_neg(arr, size);
print_array(arr, size);
}
This code takes .325 seconds for 10,000 elements.
#include<stdio.h>
int main()
{
char arr[]=
{0,-1,1,-5,3,-2,6};
int i,j=0;
int k=0;
int size=sizeof(arr)/sizeof(arr[0]);
printf("before\n");
for(i=0;i<size;i++)
printf("%3d",arr[i]);
printf("\n");
i=0;
int cnt=0;
int loop=0;
while(cnt<=size-j)
{
loop++;
cnt++;
if(arr[i]>=0&&!k)
{
j=i;
k=1;
}
if((arr[i]>=0)&&(arr[i+1]<0))
{
int t=arr[i];
arr[i]=arr[i+1];
arr[i+1]=t;
if(i==j)
j=i+1;
cnt=0;
}
if(i==size-2)
{
i=0;
k=0;
}
else
i++;
}
printf("after\n");
for(i=0;i<size;i++)
printf("%3d",arr[i]);
printf("\n");
printf("loop=%d\n",loop);
return 0;
}
public static void reArrageArray(int []data) {
int loopCount = 0;
int nPos = -1;
for (int i = 0; i < data.length; i++) {
int nValue = data[i];
if (nValue < 0) { //2
if (nPos != i-1) {
for (int j = i ; j > 0; j--) {
if (data[j-1] >= 0) {
data[j] = data[j-1];
data[j-1] = nValue;
} else {
nPos = j;
}
loopCount++;
}
} else {
nPos = i;
loopCount++;
}
} else {
loopCount++;
}
}
System.out.println("Total loop count : " + loopCount);
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
public class Test{
public static void main(String[] args){
int[] a = {-1, 1, 3, -2, 2, -6, -7, 8,9,12};
int i = 0, j = a.length - 1, tmp;
while (i < j){
if (a[i] < 0){
i++;
}
if (a[j] > 0){
j--;
}
if(i < j){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
for(int k = 0; k < a.length; k++){
System.out.print(a[k] + " | ");
}
}
}
It seems not that difficult, someone did mention 'mergesort' but no one mentioned how to make it O(N): So, how about using a special version of mergesort recursively, where "merge" involves inserting +ve and -ve parts of the 'right' sub-list into the 'left' sub-list, this "merge" will take O(1), leading to O(N) for the whole mergesort?
This is not possible in O(1) space, O(n) time is fine. I guess interviewer wanted to see if interviewee is confident enough to say this.
for O(1) space, can we not allocate max integer space and then fill it sequentially with occurred positive integers in given array, and then fill them back in original array from end of the array, here we will ensure that all -ve integers are pulled ahead. (filling up in original array should be easy). Help expand this logic if makes sense.
#include<iostream>
using namespace std;
void swapp(int* a,int* b)
{
int t= *a;
*a=*b;
*b=t;
}
int main()
{
int n;
cin>>n;
int* a=new int[n];
for(int i=0;i<n;i++)
cin>>a[i];
int countneg=0,countpos=0;
for(int i=0;i<n;i++)
{
if(a[i]<0)countneg++;
else countpos++;
}
cout<<countneg<<" "<<countpos<<endl;
int j=0,tempcount=countneg;
for(int i=0;i<n;i++)
{
if(a[i]>0 && i<countneg)
{
swapp(&a[i],&a[tempcount]);
tempcount++;
}
else if(a[i]<=0)
{
swapp(&a[i],&a[j]);
j++;if(i>0) i--;
}
else continue;
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
delete []a;
}
Do an in-place partition (i.e. from the quick sort algorithm) on the pivot value 0. However, the partition algorithm is not stable, but we can fix that without too much extra work and constant overhead.
Example:
Given: -1 1 3 -2 2
Correct Answer: -1 -2 1 3 2
Let's run through the quicksort partition algorithm:
-1 1 3 -2 2
^--- -1 <= 0, keep it there, adding it to the left paritition.
increment the pointer.
-1 1 3 -2 2
^--- 1 > 0. This is the first value inserted to the right partition.
Call this position first_right_val.
-1 1 3 -2 2
^ ^ 3 > 0. do nothing when first_right_val is the first element of the right
partition.
-1 -2 3 1 2
^ ^ swap to grow the left partition.
note that this operation loses the "stable" property.
however, we can regain that. for now, lets track that the value
was swapped, i.e. update first_right_val to point to its new
position.
-1 -2 2 1 3
^ ^--- 2 > 0. If first_right_val is not the first element of the
right parition, we should do a swap. first_right_val
remains pointing to the "1"
Parition is finished. But the partition is not stable. However we know where
the first encountered element of the right partition _is_, i.e. its the "1".
And by adding extra swapping logic when examining the elements greater than
the pivot we have essentially kept a "rotated" copy of the right partition.
To recover a stable partition, simply do a rotate on the right paritition,
to get:
-1 -2 1 3 2
By the way, a stable_partition is already implemented in STL if using C++ that
does exactly what this question is asking.
bool IsLessThanZero(int val) { return val < 0; }
std::stable_partition(data_array.begin(), data_array.end(), IsLessThanZero);
If you have to implement the stable_partition manutally, you can always use the
STL rotate for the last step!
// After partitioning as above, keeping track of the first_right_val.
std::rotate(data_array.begin() + right_partition_start_index,
data_array.begin() + first_right_val, // the new first element
data_array.end());
LOL. "Easy"? Have you even tried doing it yourself, rather than fanning yourself while waving your hands?
Do an in-place partition (i.e. from the quick sort algorithm) on the pivot value 0. However, the partition algorithm is not stable, but we can fix that without too much extra work and constant overhead.
Example:
Given: -1 1 3 -2 2
Correct Answer: -1 -2 1 3 2
Let's run through the quicksort partition algorithm:
-1 1 3 -2 2
^--- -1 <= 0, keep it there, adding it to the left paritition.
increment the pointer.
-1 1 3 -2 2
^--- 1 > 0. This is the first value inserted to the right partition.
Call this position first_right_val.
-1 1 3 -2 2
^ ^ 3 > 0. do nothing when first_right_val is the first element of the right
partition.
-1 -2 3 1 2
^ ^ swap to grow the left partition.
note that this operation loses the "stable" property.
however, we can regain that. for now, lets track that the value
was swapped, i.e. update first_right_val to point to its new
position.
-1 -2 2 1 3
^ ^--- 2 > 0. If first_right_val is not the first element of the
right parition, we should do a swap. first_right_val
remains pointing to the "1"
Parition is finished. But the partition is not stable. However we know where
the first encountered element of the right partition _is_, i.e. its the "1".
And by adding extra swapping logic when examining the elements greater than
the pivot we have essentially kept a "rotated" copy of the right partition.
To recover a stable partition, simply do a rotate on the right paritition,
to get:
-1 -2 1 3 2
By the way, a stable_partition is already implemented in STL if using C++ that
does exactly what this question is asking.
bool IsLessThanZero(int val) { return val < 0; }
std::stable_partition(data_array.begin(), data_array.end(), IsLessThanZero);
If you have to implement the stable_partition manutally, you can always use the
STL rotate for the last step!
// After partitioning as above, keeping track of the first_right_val.
std::rotate(data_array.begin() + right_partition_start_index,
data_array.begin() + first_right_val, // the new first element
data_array.end());
With a singly linked list (instead of an array) you can obtain O(n) time complexity and O(1) space complexity:
public void sort() {
Node crtPos = list.head;
Node crtNeg = list.head;
while ((crtPos != null) && (crtPos.x < 0)) {
crtPos = crtPos.next;
}
while ((crtNeg != null) && (crtNeg.x >= 0)) {
crtNeg = crtNeg.next;
}
if ((crtNeg == null) || (crtPos == null)) {
return;
}
// we've found the head of the list
list.head = crtNeg;
// keep a reference to the first positive item
Node firstPos = crtPos;
Node lastNeg = null;
Node latestNeg = crtNeg;
Node latestPos = crtPos;
while ((latestNeg != null) && (latestPos != null)) {
while ((crtNeg != null) && (crtNeg.x < 0)) {
latestNeg = crtNeg;
crtNeg = crtNeg.next;
}
lastNeg = latestNeg;
while ((crtPos.x >= 0) && (crtPos != null)) {
latestPos = crtPos;
crtPos = crtPos.next;
}
while ((crtPos != null) && (crtPos.x < 0)) {
crtPos = crtPos.next;
}
latestPos.next = crtPos;
latestPos = crtPos;
while ((crtNeg != null) && (crtNeg.x >= 0)) {
crtNeg = crtNeg.next;
}
latestNeg.next = crtNeg;
latestNeg = crtNeg;
}
lastNeg.next = firstPos;
}
O(n) O(1)!
void sort(int arr[], int n) {
int nextNonNeg = 0;
int i = 0;
for (i, nextNonNeg; i < n; i++, nextNonNeg++)
if (arr[i] > 0)
break;
for (i; i < n; i++) {
if (arr[i] < 0) {
int t = arr[i];
memmove(&(arr[nextNonNeg + 1]),
&(arr[nextNonNeg]),
sizeof(int) * (i - nextNonNeg));
// swap(arr, i, nextNonNeg);
arr[nextNonNeg] = t;
nextNonNeg++;
}
}
}
O(n) time O(1) space solution:
def sort(A):
while ( j < len(A) ):
while ( i < len(A) and A[i] < 0 ):
i += 1
while ( j < len(A) and A[j] >= 0 ):
j += 1
if ( i < j and i < len(A) and j < len(A)):
temp = A[i]
A[i] = A[j]
A[j] = temp
j+=1
return A
complexity is little more than (n)...
public class Googlearray {
public static void main(String[] args) {
int a[]={-1,1,-3,3,-2,-4,5,-3,2};
int l=a.length;
int i = 0,j=0; //j for positive... i for negative numbers
int count=0;
int temp;
while(i<l && j<l){
if(a[j]<0)
j++;
if(a[i]<0 && count>0){
temp = a[i]; //swap -ive no with previous one until it
a[i]=a[i-1]; //is not replaced by positive.
a[i-1]=temp;
count--;
i--;
}
if(a[i]<0 && count==0){
i++;
}
if(a[i]>0)
{
count++; //keep counts for swaping the -ne no.
i++;
}
}
for(i=0;i<=l-1;i++){
System.out.println(a[i]);
}
}
}
<?php
$arr = array(1, 1, 3, -2, 2);
$arr = customSort($arr);
var_dump(implode(",",$arr));
function customSort($arr)
{
$negCount = 0;
foreach($arr as $value){
if($value < 0){
$negCount++;
}
}
$sIndex = 0;
/*if(count($arr) % 2 == 0){
$eIndex = count($arr) - $negCount ;
}else{
$eIndex = count($arr) - $negCount -1;
}*/
$eIndex = $negCount ;
$i = 0;
while($sIndex < $negCount){
if($arr[$i] < 0){
$temp = $arr[$i];
$arr[$i]=$arr[$sIndex];
$arr[$sIndex] = $temp;
$sIndex++;
$i++;
}else{
$temp = $arr[$i];
$arr[$i]=$arr[$eIndex];
$arr[$eIndex] = $temp;
$eIndex++;
}
}
return $arr;
}
?>
I have a completly different approach.
What I would suggest is to use Godel numbering to hold the array. we will have 2 Godel numbering. one for the positive numbers, and one for the negative ones.
The godel numbers will be created based on the position of the numbers in the array.
there are some issues in the solution, such as Godel number might grow exponentially with n, and also that if the numbers are not in N, this method won't work.
but still this is a cool approach, maybe someone can develop it a bit more.
Using double pointers. The first pointer is to head and the other one to tail.
If the first pointer value is less than zero, first pointer move one step forward. Otherwise, if first pointer greater than zero, waiting second pointer scan from tail till find the first one which is negative.
The complex is O(1) (the constant is 1) and space is O(1) .
static List<int> DoSearch(List<int> n) {
if ((n.Count == 1) || (n.Count == 0))
return n;
int x = 0;
int y = n.Count - 1;
while (x <= y) {
if (n[x] > 0) {
while (n[y] >= 0)
{
y--;
}
if (y <= x)
break;
int m = n[x];
n[x] = n[y];
n[y] = m;
x++;
y--;
}
x++;
}
return n;
}
int negatifindex=0;
int prevnegatifindex=-1;
int pozitifindex=4; // array.length-1
int nextpozitifindex=-1;
while (negatifindex<=pozitifindex)
{
if(array[negatifindex]<0)
{
if (prevnegatifindex!=-1)
swap(array[prevnegatifindex],array[negatifindex])
prevnegatifindex=-1;
negatifindex++;
}
if(array[pozitifindex]>0)
{
if (nextpozitifindex!=-1)
swap(array[nextpozitifindex],array[pozitifindex])
nextpozitifindex=-1;
pozitifindex--;
}
if (array[pozitifindex]<0 & array[negatifindex]>0)
{
swap(array[pozitifindex],array[negatifindex])
prevnegatifindex=negatifindex;,
pozitifindex--;
nextpozitifindex=pozitifindex;
negatifindex++;
}
}
Time complexity is O(n) and space is O(1)
Let's solve this problem by diving it into two much simpler problems:
A) We want negative numbers to be at the right positions; we don't care about the positive one
B) We move the positive numbers at the right positions, not caring about the negative one
C) We apply A B on copies of the array and then combine the result to get the final solution
A and B can be easily solve linearly.
Solution for A:
{{
void solveA(int* a, int n)
{
int p = 0;
for (int i = 0; i < n; i++)
if (a[i] < 0)
{
a[p] = a[i];
p++
}
}
}}
For B the solution is similar.
C) is also quite easy. We just need to count how many negative and positive number we have in order to know how many values to copies from the two partial solution.
Complexity: O(n) both time and space
O(n) and O(n)
void positionSort(int x[])
{
int tempArr[count];
memcpy(tempArr,x,count*sizeof(int));
int neg_index = 0,
pos_index=count-1,temp=0;
for(int i=0;i<count;i++)
{
if(tempArr[i] < 0)
{
x[neg_index++] = tempArr[i];
}
if(tempArr[count-i] >= 0)
{
x[pos_index--] = tempArr[count-i];
}
}
}
Here's the simple code, where you shift right everything when you encounter negative number.
public static void specialOrderedSort(int[] array){
if ( array == null){
return;
}
int negNumIndex = -1;
int firstPosNumIndex = -1;
for ( int index = 0; index < array.length; index++){
if(array[index] < 0){
negNumIndex = index;
}else{
if ( firstPosNumIndex == -1){
firstPosNumIndex = index;
}
}
if ( negNumIndex >= firstPosNumIndex){
int negNum = array[negNumIndex];
for ( int i = negNumIndex-1; i >= firstPosNumIndex;i--){
array[i+1]=array[i];
}
array[firstPosNumIndex] = negNum;
firstPosNumIndex++;
negNumIndex = -1; //reset to get next -ve number position.
}
}
}
Here is my solution O(n) time and constant space complexity
1) count number of negative numbers in the array
2) set the index where positive number is supposed to start as pivot
3) count number of positive numbers before pivot and after pivot
4) iterate each number in the array until pivot
a) if number is negative proceed
b) if number if positive initiate rearrangment to place each number in its correct position until we come back to current position.
c++ code
#include <iostream>
using namespace std;
int countNegatives(int a[], int n){
int negNums = 0;
for(int i = 0 ; i < n ; ++i){
if(a[i] < 0)
negNums++;
}
return negNums;
}
int countPositivesBeforePivot(int a[], int pivot){
int numPos = 0;
for(int i = 0 ; i < pivot ; ++i){
if(a[i] > 0)
numPos++;
}
return numPos;
}
void rearrange(int a[], int posCount, int i, int numNegs, int posBeforePivots, int posAfterPivots){
int nexti = posCount + numNegs - 1;
int curval = a[i];
while(nexti != i){
int temp = a[nexti];
a[nexti] = curval;
curval = temp;
cout << nexti << " " << temp << endl;
if(temp > 0){
cout << "positive" << endl;
nexti = nexti + posBeforePivots;
}
if(temp < 0){
cout << "negative" << endl;
nexti = nexti - (posBeforePivots + posAfterPivots);
}
}
a[i] = curval;
}
void sepNegnPos(int a[], int n){
int negNums = countNegatives(a, n);
std::cout << " num negs " << negNums << std::endl;
int posBeforePivots = countPositivesBeforePivot(a, negNums);
std::cout << " num pos before pivot " << posBeforePivots << std::endl;
int posAfterPivots = n - negNums - posBeforePivots;
int numPosSofar = 0;
for(int i = 0 ; i < negNums ; ++i){
std::cout << a[i] << std::endl;
if(a[i] == 0){
std::cout << "zero not allowed" << std::endl;
return;
}
if(i < negNums && a[i] < 0)
continue;
else if(i < negNums && a[i] > 0){
numPosSofar++;
rearrange(a, numPosSofar, i, negNums, posBeforePivots, posAfterPivots);
}
}
}
int main(void){
int a[] = {-1, 1, 4, 3, 5, -2, -3};
sepNegnPos(a, 7);
for(int i = 0 ; i < 7 ; ++i){
std::cout << a[i] << " ";
}
std::cout << std::endl;
}
Instead of numbers we should work with segments of positive or negative numbers. Lets say the numbers are [1 2 -1 -2 -3 4 5 6 -7 -8 -9].
initial segments: [1 2], [-1 -2 -3]*, [4 5 6], [-7 -8 -9]
step 1. [-1 -2], [1 2]*, [-3], [4 5 6], [-7 -8 -9] ... pushed right seg to left, 2 swaps
step 2. [-1 -2 -3], [1 2 4 5 6]*, [-7 -8 -9] ... pushed left seg to right, 2 swaps
step 3. [-1 -2 -3], [1 2], [-7 -8 -9]*, [4 5 6] ... pushed left seg to right, 3 swaps
step 4. [-1 -2 -3 -7 -8], [1 2]*, [-9], [4 5 6] ... pushed right seg to left, 2 swaps
step 5. [-1 -2 -3 -7 -8 -9], [1 2 4 5 6] ... pushed left seg to right, 2 swaps
Total 11 swaps.
Lets say the negative segment is N and the positive segment is P. Now, given a situation like "[all negative], P, N, [unknown]", we need to do the following.
1. If |N| >= |P|, send right segment to left, total swap needed |N|+|P|
2. If |N| < |P|, send left segment to right, total swap needed |N|+|P|
Amortized O(n).
Please let me know if it has any problem? it is in O(N) time complexity and O(1) space.
/*
============================================================================
Author : Shashi Shekhar
Email : shashishekhar32@gmail.com
Description : Given an array which has n integers. It has both positive and negative integers.Now you need to sort this array in such a way that,the negative integers should be in the front,and the positive integers should at the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.Required running time complexity is O(N) and the space complexity is O(1)
Created Date : 26-JAN-2014
===========================================================================
*/
#include<stdio.h>
void sort_array(int arr[],int n)
{
int count =0;
int temp1=0;
int pos_to_fill_with_positive_num=0;
int pos1=0;
int pos2=0;
int just_moved =0;
int num_remaining=0;
for(int i=0;i<n;i++)
{
if(arr[i]<0)
{
count++;
}
}
pos1 = count;
num_remaining=count;
for(int i=0;i<n;i++)
{
if(arr[i]<0)
{
temp1=arr[pos2];
arr[pos2]=arr[i];
arr[i]=temp1;
pos2++;
if(pos1>=i && i>count)
{pos1++;
just_moved=1;
}
num_remaining--;
}
else
{
if(pos2==count)
break;
else if((i>=count) && (i<pos1) &&(!just_moved))
continue;
else if(just_moved)
{
just_moved=0;
temp1=arr[i];
arr[i]=arr[pos2];
arr[pos2]=temp1;
}
else
{
if(i<count)
{
temp1=arr[pos1];
arr[pos1]=arr[i];
if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
arr[pos_to_fill_with_positive_num]=temp1;
else if(pos_to_fill_with_positive_num<count)
arr[++pos_to_fill_with_positive_num]=temp1;
else
{
pos_to_fill_with_positive_num=pos2;
arr[pos_to_fill_with_positive_num]=temp1;
}
pos_to_fill_with_positive_num++;
pos1++;
}
else
{
temp1=arr[pos1];
arr[pos1]=arr[pos_to_fill_with_positive_num];
arr[pos_to_fill_with_positive_num]=temp1;
pos_to_fill_with_positive_num++;
pos1++;
}
}
}
if(num_remaining==0)
break;
}
}
void main()
{
int n = 9;
int arr[9]={-1,1,3,4,6,-3,1,-2,2};
//int arr[7]={-1,3,-2,4,5,-5,9};
//int arr[5]={-1,1,3,-2,2};
printf("\input array:");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
sort_array(arr,n);
printf("\noutput array");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
}
#include<stdio.h>
void sort_array(int arr[],int n)
{
int count =0;
int temp1=0;
int pos_to_fill_with_positive_num=0;
int pos1=0;
int pos2=0;
int just_moved =0;
int num_remaining=0;
for(int i=0;i<n;i++)
{
if(arr[i]<0)
{
count++;
}
}
pos1 = count;
num_remaining=count;
for(int i=0;i<n;i++)
{
if(arr[i]<0)
{
temp1=arr[pos2];
arr[pos2]=arr[i];
arr[i]=temp1;
pos2++;
if(pos1>=i && i>count)
{pos1++;
just_moved=1;
}
num_remaining--;
}
else
{
if(pos2==count)
break;
else if((i>=count) && (i<pos1) &&(!just_moved))
continue;
else if(just_moved)
{
just_moved=0;
temp1=arr[i];
arr[i]=arr[pos2];
arr[pos2]=temp1;
}
else
{
if(i<count)
{
temp1=arr[pos1];
arr[pos1]=arr[i];
if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
arr[pos_to_fill_with_positive_num]=temp1;
else if(pos_to_fill_with_positive_num<count)
arr[++pos_to_fill_with_positive_num]=temp1;
else
{
pos_to_fill_with_positive_num=pos2;
arr[pos_to_fill_with_positive_num]=temp1;
}
pos_to_fill_with_positive_num++;
pos1++;
}
else
{
temp1=arr[pos1];
arr[pos1]=arr[pos_to_fill_with_positive_num];
arr[pos_to_fill_with_positive_num]=temp1;
pos_to_fill_with_positive_num++;
pos1++;
}
}
}
if(num_remaining==0)
break;
printf("\nin step %d",i+1);
for(int j=0;j<n;j++)
printf(" %d ",arr[j]);
}
}
void main()
{
int n = 9;
int arr[9]={-1,1,3,4,6,-3,1,-2,2};
//int arr[7]={-1,3,-2,4,5,-5,9};
//int arr[5]={-1,1,3,-2,2};
printf("\input array:");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
sort_array(arr,n);
printf("\noutput array");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
}
public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
{ public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}
public class TestLogic {
public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}
public class TestLogic {
public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}
The problem can indeed be solved in O(n) time and with O(1) complexity.
Below is my solution:
#include <vector>
#include <iostream>
#include <stdio.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define repv(i, v) for(int i = 0; i < v.size(); i++)
void printArray(const vector<int> &A)
{
repv(i, A) cout << A[i] << " ";
cout << endl;
}
void reverse(vector<int> &A, int start, int end)
{
while(start < end) swap(A[start++], A[end--]);
}
void sortPosNeg(vector<int> &A)
{
// find and sort each segment of positive-streak followed by negative-streak
// time complexity -- O( A.size() ) , space complexity -- O(1)
int pstart, pend;
int nstart, nend;
int i = 0;
while(i < A.size())
{
// ignore leading streak of negatives
if( i == 0 )
{
while(i < A.size() && A[i] < 0) i++;
if(i == A.size()) break;
printf( "leading neg-streak: (%d,%d)\n", 0, i-1);
pstart = i;
pend = pstart;
}
// find start and end of postive-streak -- O( length(pos-streak) )
while(pend < A.size() && A[pend] > 0) pend++;
if(pend-- == A.size()) break;
printf( "pos-streak: (%d,%d)\n", pstart, pend);
// find start and end of negative-streak -- O( length(neg-streak) )
nstart = pend+1;
nend = nstart;
while(nend < A.size() && A[nend] < 0) nend++;
nend--;
printf( "neg-streak: (%d,%d)\n", nstart, nend);
// now swap positions pos-streak with neg-streak
// Note: this is just like reversing words in a sentence
reverse(A, pstart, pend); // O( length(pos-streak) )
reverse(A, nstart, nend); // O( length(neg-streak) )
reverse(A, pstart, nend); // O( length(pos-streak) + O( length(neg-streak) )
// update the position of the positive-streak which we just moved
pstart = nend - (pend - pstart);
pend = nend;
// A[0] to A[nend] has been sorted now move on to the rest of the array
i = nend + 1;
}
}
int main()
{
// read data
int N;
cin >> N;
vector<int> A(N);
rep(i, N) cin >> A[i];
cout << "Before sorting: " << endl;
printArray(A);
// sort the array
sortPosNeg(A);
cout << "After sorting: " << endl;
printArray(A);
return 0;
}
Approach:
Think of the array as continguous streaks of positive and negative integers: [n0 p1, n1, p2, n2, p3, n3, ...]
Each streak can have any number of integers in it.
We can ignore the leading streak of negative integers (if any) because they are already in the sorted position.
Now we need to find a solution to sort each [pi, ni] pair or a positive streak followed by a negative streak.
After sorting [pi, ni] we get [ni, pi] -- essentially swap/switch the locations of the streaks.
To do this, do the following steps
-- Reverse pi to get rev(pi)
-- Reverse ni to get rev(ni)
-- Reverse [ rev(pi), rev(ni) ] to get [ rev(rev(ni)), rev(rev(pi)) ] which is equal to [ni, pi]
This is very similar to reversing all the words within a sentence (not the whole sentence).
I would appreciate it if you could correct me if i am wrong anywhere.
My solution in C++ below. Running time is O(n) (two passes) and it's done in place (O(1) extra-space) :
#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;
}
Time O(N) and space O(1)
#include <stdio.h>
/*
we will take positive number block and negative number block.
And will move negative number block in front of positive number block.
*/
int main()
{
int num[] = {-1, 1, 3, -2, -3, 4, 5, -7, 2, 8, -8};
int len = sizeof(num)/sizeof(int);
int i,l_t,var_t;
int ps,pe,ns,ne,nc,pc;
ps = pe = ns = ne = 0;
while (1){
for (;num[ps] < 0; ps++); /* Find start of positive number block */
for (pe = ps; num[pe+1] >= 0 && pe+1 < len; pe++); /* Find end of positive number block */
if (pe+1 == len) {
break;
}
ns = pe + 1; /* Assign start of negative number block */
for (ne = ns; num[ne+1] < 0 && ne+1 < len; ne++); /* Find end of negative number block */
nc = ne - ns + 1; /* Count negative numbers in block */
pc = pe - ps + 1; /* Count positive numbers in block */
i = ns;
var_t = num[ns];
while (1) {
if (i-pc >= ps && num[i-pc] >= 0) { /* Move negative number to new position */
i -= pc;
l_t = num[i];
num[i] = var_t;
var_t = l_t;
} else if (i+nc <= ne) { /* Move positive number to new position */
i += nc;
l_t = num[i];
num[i] = var_t;
var_t = l_t;
} else { /* Pick next -ve number */
for (;num[ns] >= 0 && ns <= ne; ++ns);
if (ns > ne) break;
i = ns;
var_t = num[ns];
}
}
}
for (i=0; i < len; ++i) {
printf("%d ", num[i]);
}
printf("\n");
return 0;
}
void sortNegPos(int arr[], size n)
{
int i = 0, j = n-1, index = -1, key = 0;
while (arr[i] < 0)
i++;
while (arr[j] >= 0)
j--;
// At this point i points to the first positive integer and j to the last negative integer
index = i;
key = arr[i];
while (i < j)
{
if (key >= 0)
{
key = arr[i + 1];
arr[i+1] = arr[i];
}
else
{
arr[index] = key;
++index;
}
i++;
}
}
The following solution seems like O(n) time and O(1) to me. Comments?
/* Align negative numbers on one side and positive on the other, with relative positions unperturbed. */
uint64_t i;
uint64_t j;
for (i = 0; i < n; ++ i) {
if (a[i] < 0) {
++negativeCount;
}
}
for (i = 0, j = negativeCount; i < negativeCount && j < n;) {
if (a[i] > 0 && a[j] > 0) {
swap(a[i], a[j]);
++j;
} else if (a[i] < 0) {
++i;
} else {
// a[j] < 0
swap(a[i], a[j]);
++i;
}
}
public void NegPostSort(int[] a, int low)
{
int neg = -1;
int pos = -1;
int current = low;
while ((current < a.Length) && ((neg < 0) || (pos < 0)))
{
if (a[current] > 0 && pos < 0)
pos = current;
if (a[current] < 0 && neg < 0)
neg = current;
current++;
}
while (neg > pos)
{
swap(ref a[neg], ref a[--neg]);
}
if (++neg < a.Length && current < a.Length)
NegPostSort(a, neg);
}
private void swap(ref int a, ref int b)
{
int t = a;
a = b;
b = t;
}
public void NegPostSort(int[] a, int low)
{
int neg = -1;
int pos = -1;
int current = low;
while ((current < a.Length) && ((neg < 0) || (pos < 0)))
{
if (a[current] > 0 && pos < 0)
pos = current;
if (a[current] < 0 && neg < 0)
neg = current;
current++;
}
while (neg > pos)
{
swap(ref a[neg], ref a[--neg]);
}
if (++neg < a.Length && current < a.Length)
NegPostSort(a, neg);
}
private void swap(ref int a, ref int b)
{
int t = a;
a = b;
b = t;
}
Here is the java implementation for O(n) time complexity, O(1) space complexity solution. Pretty sure others would have answered it already on this forum...I just did not take time to go through all the solutions.
import java.util.Arrays;
import java.util.List;
public class Sort {
public static void main(String[] args) {
System.out.println(sortPositiveNegative(Arrays.asList(-1, 1, 2, -4, 6, 8, -8, 10)));
}
public static List<Integer> sortPositiveNegative(List<Integer> numbers) {
int numbersCount = numbers.size();
// select pivot as 0 because we want to keep all negative numbers before
// any positive numbers
int pivot = 0;
int i = 0;
// Lets take i to the first positive number. Before that everything is
// sorted anyways.
while (numbers.get(i) < pivot) {
i++;
}
// Rearrange rest of the numbers properly.
for (int j = i + 1; j < numbersCount; j++) {
if (numbers.get(j) < pivot) {
swap(i, j, numbers);
i++;
}
}
return numbers;
}
private static void swap(int i, int j, List<Integer> numbers) {
// keep it simple as below or try some bit manipulation.
int temp = numbers.get(i);
numbers.set(i, numbers.get(j));
numbers.set(j, temp);
}
}
Can anyone find something wrong with this? It should be O(n)/O(1).
void weird_sort(int a[], int n)
{
.
.
/* Find first positive number */
for (i=0; i<n; i++)
{
if (a[i]>=0) break;
}
pivot=i;
/* Swap negative numbers and advance pivot */
for (i=pivot+1; i<n; i++)
{
if (a[i]<0)
{
swap(a,i,pivot);
pivot++;
}
}
Below is basically a merge-sort implementation. I did this in Python but easy to port to C. It is O(N logN) I think (log N calls to sort, merge is O(n)), and could be farmed out to multiple machines too for each independent part for scale. Not sure how to evaluate space usage -- do you count the stack? Also, the Python tuple concatenation and list division is not ideal in memory usage of course but could easily be improved and done in-place in C.
#!/usr/bin/env python
import sys
def sort(l):
if len(l) == 1:
return l
elif len(l) == 2:
if l[0] > 0 and l[1] < 0:
return (l[1], l[0])
else:
return (l[0], l[1])
else:
return merge(sort(l[0:len(l)/2]), sort(l[len(l)/2:]))
def merge(l1, l2):
result = ()
for val in l1 + l2:
if val < 0:
result += (val,)
for val in l1 + l2:
if val >= 0:
result += (val,)
return result
if __name__ == '__main__':
print sort(tuple([int(v) for v in sys.argv[1].split(',')]))
example: -1 , 1 , 3 , -2 , 2, -4 , 4 , 5 , -5
O(n) time O(1) space solution
Count the number of negative elements (k = 4 here) , as a first step try to get first 4 elements in correct order, every time you swap an element out record its index, let f be the encoding function for negatives and g for positives.
Step1.1 : -1 , 1 , -4 , -5 , 2 , g(3,3), 4 , 5 , f(-2,4)
Step1.2 ( f(x,y) will be in the order f(x1, y1), f(x2, y2), f(x3, y3) , ..., where y1 < y2 < y3 < .. , same property holds for g). But you have the rest of the negative elements in their final destinations, freeze these elements. Treat f(x,y) as your new negatives on an array, perform swaps similar to step1, let h be the encoding function for positives dislocated in this step:
-1 , f(-2,4) , -4 , -5 , 2 , g(3,3) , 4 , 5 , h(1,2)
Step2: Stable sort the unfrozen negative elements
Step3: Now you are done with all the negatives. You have the property max(y / h(x,y)) < max(y / g(x,y)), again h(x,y) will appear in increasing order of y. Stable sort h union g relative to the other positives:
<all negatives> , h(1,2) , g(3,3), 2 , 4 , 5
You can always pick to work on the positives first / negatives first based on the sizes of arrays appearing in the recursive step. So you would have
T(n) = O(n) + T(a) + T(b) ( where a+b < 3n/4)
so T(n) = O(n)
It is unreasonable to expect someone to solve this within 1 hour
public static int[] PosNegSort(int[] dataArray)
{
int[] result = new int[dataArray.Length];
int index = 0;
// 1 - Collect the negative numbers first.
foreach (int data in dataArray)
{
if (data < 0)
{
result[index++] = data;
}
}
// 2 - Collect the zero(s) second.
foreach (int data in dataArray)
{
if (data == 0)
{
result[index++] = data;
}
}
// 3 - And finally collect the positive numbers.
foreach (int data in dataArray)
{
if (data > 0)
{
result[index++] = data;
}
}
return result;
}
public class SpecialSort {
public static void main(String[] args) {
int[] data = {-1, 1, 3, -2, 2};
int length = data.length - 1;
int[] specialSort = specialSort(data, length);
for(int i=0; i<specialSort.length; i++){
System.out.printf("%d ", specialSort[i]);
}
}
private static int[] specialSort(int[] data, int length) {
for(int i=0; i<length-1; i++){
for(int k=0; k<length-i; k++){
if(data[k] > 0 && data[k+1] < 0){
int temp = data[k];
data[k] = data[k+1];
data[k+1] = temp;
}
}
}
return data;
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:
public class HelloWorld{
public static void main(String []args){
int a[]={-1,3,5,-7,2,4,-6,8};
int len=a.length;
for(int i=0;i<len;i++)//bubble sort times
{
for(int j=0;j<len-1-i;j++)// times of comparison in each loop
{
if(a[j]>0&&a[j+1]<0)
{a[j]=a[j]-a[j+1];
a[j+1]=a[j]+a[j+1];
a[j]=a[j+1]-a[j];
}
}
}
for (int i=0;i<len;i++)
{
System.out.println(a[i]);
}
}
}
private static void sortArray() {
int changeIndex = -1;
int[] a = {-34, -3, 41, 2, -3, -4, 4, 54, -56, 43, -34, 34, 345, -55, 55, -5, 6, 8, 9, -8};
displayArrayElements(a);
for (int i = 0; i < a.length - 1; i++) {
if (a[i] * a[i + 1] < 0) {
if (changeIndex == -1) {
changeIndex = i + 1;
} else {
moveElements(a, changeIndex, i + 1);
changeIndex += 1;
}
} else {
}
}
displayArrayElements(a);
}
private static void displayArrayElements(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
private static void moveElements(int[] a, int changeIndex, int i) {
int element = a[i];
for (int j = i; j > changeIndex; j--) {
a[j] = a[j - 1];
}
a[changeIndex] = element;
}
private static int[] reorderArray(int[] input) {
if (input==null || input.length==0)
return input;
int fistPositiveNumber = -1;
int temp = 0;
for (int position = 0;position<input.length; position++) {
if (input[position]>0 && fistPositiveNumber<0)
fistPositiveNumber = position;
if (input[position]<0 && fistPositiveNumber>=0) {
temp = input[position];
System.out.println(fistPositiveNumber +" "+ temp);
System.arraycopy(input,fistPositiveNumber,input,fistPositiveNumber+1,position-fistPositiveNumber);
input[fistPositiveNumber] = temp;
fistPositiveNumber++;
}
printArrays(input);
}
return input;
}
private static int[] reorderArray(int[] input) {
if (input==null || input.length==0)
return input;
int fistPositiveNumber = -1;
int temp = 0;
for (int position = 0;position<input.length; position++) {
if (input[position]>0 && fistPositiveNumber<0)
fistPositiveNumber = position;
if (input[position]<0 && fistPositiveNumber>=0) {
temp = input[position];
System.out.println(fistPositiveNumber +" "+ temp);
System.arraycopy(input,fistPositiveNumber,input,fistPositiveNumber+1,position-fistPositiveNumber);
input[fistPositiveNumber] = temp;
fistPositiveNumber++;
}
printArrays(input);
}
return input;
}
n 0 1 2 3 4
value -1 1 3 -2 2
1. define boolean inProcess = false;
2. From 0 to n, if value(n) = negative, continue
else
inProcess = true;
tempA = n;
while(inProcess) {
if(value[n] = negative)
inProcess = false;
tempB = value(n+1)
shift value(n) from n to n+1
increase n until find a negative value (m).
}
value[tempA] = tempB;
{{
int[] array = {-1, 1, 3, 4, -2, 2};
boolean inProcess = false;
while(i<array.length) {
if(array[i] < 0) {
i++;
} else {
inProcess = true;
tempNo = i;
while(inProcess) {
if(tempB == null)
tempA = array[i];
else
tampA = tempB;
tempB = array[i+1];
if(array[i+1] < 0)
inProcess = false;
array[i+1] = tempA;
i++;
}
array[tempNo] = tempB;
}
}
}}
n 0 1 2 3 4
value -1 1 3 -2 2
1. define boolean inProcess = false;
2. From 0 to n, if value(n) = negative, continue
else
inProcess = true;
tempA = n;
while(inProcess) {
if(value[n] = negative)
inProcess = false;
tempB = value(n+1)
shift value(n) from n to n+1
increase n until find a negative value (m).
}
value[tempA] = tempB;
int[] array = {-1, 1, 3, 4, -2, 2};
boolean inProcess = false;
while(i<array.length) {
if(array[i] < 0) {
i++;
} else {
inProcess = true;
tempNo = i;
while(inProcess) {
if(tempB == null)
tempA = array[i];
else
tampA = tempB;
tempB = array[i+1];
if(array[i+1] < 0)
inProcess = false;
array[i+1] = tempA;
i++;
}
array[tempNo] = tempB;
}
}
public static int[] relSort3(int[] arr){
int[] res=new int[arr.length];
int lastExch=0;
//sort negatives
for(int i=0; i<res.length; i++){
for(int j=lastExch; j<arr.length; j++ )
if(arr[j]<0){
res[i]=arr[j];
lastExch=j+1;
break;
}
}
int lastExch2=arr.length-1;
//sort positives
for(int i=res.length-1; i>0; i--){
for(int j=lastExch2; j>-1; j-- )
if(arr[j]>0){
res[i]=arr[j];
lastExch2=j-1;
break;
}
}
return res;
}
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
class ReOrder:
'''Give you an array which has n integers,it has both positive and
negative integers.Now you need sort this array in a special way.
After that,the negative integers should in the front,and the
positive integers should in the back.Also the relative position
should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect. '''
def __init__(self, items):
self.items = items
def prt(self):
swap = True
iLen = len(self.items)
x = self.items #just make it easier for typing, one can directly use self.items for x
if iLen < 2:
print self.items
return
cnt = 0
while swap:
swap = False
for i in range(iLen-1):
if x[i] > 0 and x[i+1] < 0:
x[i], x[i+1] = x[i+1], x[i]
swap = True
cnt += 1
print (cnt, x)
public int[] getMagicSort(int[] a){
int firstNeg=0;
for(int start=0; start < a.length; start++){
while(firstNeg < a.lenght){
if(a[firstNeg] < 0){
break;
}
firstNeg++;
}
percolate(a, start, firstNeg);
}
}
private void percolate(int[] a, int sI, int eI){
if(eI <= sT)
return;
int temp = a[eI-1];
a[eI-1] = a[eI];
a[eI] = temp;
percolate(int a, sI, eI-1);
}
space complexity O(1), time complexity O(N)
It seems quite easy, I don't understand why it should be done in O(Nlog(N)).
#include <stdio.h>
#include <stdlib.h>
int main(){
int* arr;
int pn, pp;
int nn = 0, np = 0;
int i, N;
scanf("%d", &N);
if(N < 0)
return 0;
arr = (int*)malloc(sizeof(int)*N);
for(i=0; i<N; i++){
scanf("%d", &arr[i]);
}
for(i=0; i<N; i++){
if(arr[i] < 0)
nn++;
}
pn = 0;
pp = nn;
int ppp = pp;
while(1){
while(arr[pn] < 0 && pn < ppp)
pn++;
while(arr[pp] >= 0 && pp < N)
pp++;
if(pn < ppp && pp < N){
int p = arr[pn];
arr[pn] = arr[pp];
arr[pp] = p;
}else
break;
pn++;
pp++;
}
for(i=0; i<N; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
public static void inplaceReplacePosNeg(int [] a , int start , int end){
int count = 0;
if(end-start<2){
return;
}
for(int i=start;i<end;i++){
if(a[i]<0)
count++;
}
if(start+count<end)
inplaceReplacePosNeg(a, start, start+count);
if(count>0)
inplaceReplacePosNeg(a, start+count, end);
int i=start;int j=start+count;
while(i<start+count){
if(a[i]<0){
i++;
continue;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
}
public static void inplaceReplacePosNeg(int [] a , int start , int end){
int count = 0;
if(end-start<2){
return;
}
for(int i=start;i<end;i++){
if(a[i]<0)
count++;
}
if(start+count<end)
inplaceReplacePosNeg(a, start, start+count);
if(count>0)
inplaceReplacePosNeg(a, start+count, end);
int i=start;int j=start+count;
while(i<start+count){
if(a[i]<0){
i++;
continue;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
}
public static void main(String args[]) {
int a[] = {-1, 2, 3, -2, 4, -5};
int temp[] = new int[a.length];
int j = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] < 0) {
temp[j++] = a[i];
a[i] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] >= 0 && a[i] != Integer.MAX_VALUE) {
temp[j++] = a[i];
}
}
for(int i = 0; i<a.length; i++){
System.out.println(temp[i]);
}
}
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence
This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and The code in c#
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);
if((j==-1) || (j==a.Length-1) )
return;
int i = 0;
if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}
// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1
while(j<a.Length-1 && (j>=0))
{
int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");
MovePositivestoEndOfBlock(a, i, j, k);
i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);
if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}
}
//Starting from startIndex returns the index till which the sign of integers has not changed , sets out isPositive to true is numbers >=0 and false
// if numbers are < 0
private static int getContigousBlock(int[] a, int startIndex, out bool isPositive)
{
isPositive = false;
comparisons = comparisons + 4;
if (a==null || a.Length==0 || startIndex < 0 || startIndex > a.Length - 1)
return -1;
isPositive = (a[startIndex] >= 0);
comparisons++; // complexity analysis variable
int i = startIndex;
comparisons++;
if (isPositive)
{
comparisons++;
while (i < a.Length && a[i] >= 0 )
{
i++;
comparisons= comparisons +2;
}
return i - 1;
}
else
{
comparisons++;
while (i < a.Length && a[i] < 0)
{
i++;
comparisons = comparisons + 2;
}
return i - 1;
}
}
//Input is an array of non negative integers followed by -ve integers
// Out put is array of -ve integers followed by positive integers. relative position of the -ve and non negative integers
//amongst them remains the same
// Algo Array A= PN where P is positive N is -ve
//Reverse A we get N-reversed + P-Reversed
// Now reverse N-Reversed and P-Reversed , so essentially O (n)
public static void MovePositivestoEndOfBlock(int[] a, int pFirst, int pEnd, int nEnd )
{
Reverse(a, pFirst, nEnd);
Reverse (a, pFirst, pFirst + nEnd-pEnd-1);
Reverse (a, pFirst+ nEnd-pEnd , nEnd);
}
public static void Reverse(int[]a, int startIndex, int endIndex)
{
comparisons = comparisons + 3;
if((a==null) || (a.Length==0) || (a.Length==1))
return;
comparisons++;
for(int i=startIndex,j=endIndex; i<j; i++, j--)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
assignments = assignments + 3;
comparisons++;
}
}
O(n) time, O(1) space
import java.util.*;
class NegativePositiveSort {
private static void sort(int[] data) {
int i = 0;
while(i < data.length) {
if(data[i] > 0) {
int j = i;
while(j < data.length && data[j] > 0) {
j++;
}
if(j < data.length) {
int neg = data[j];
for(; j > i; j--) {
data[j] = data[j - 1];
}
data[i] = neg;
}
i = j;
} else {
i++;
}
}
}
public static void main(String... args) {
//int[] data = new int[] {-1, 1, 3, -2, 2};
//int[] data = new int[]{1, 2, 3, 4, 5, -5, -4, -3, -2, -1};
int[] data = new int[] {1, -1, 2, -2};
sort(data);
System.out.println(Arrays.toString(data));
}
}
import java.util.Arrays;
public class sort {
public static void main(String[] args){
sort instance = new sort();
int[] m = {-2, 6, 4, 5,-6, 9, -1};
System.out.println(Arrays.toString(instance.sortArray(m)));
}
public int[] sortArray(int[] array){
int n = array.length;
int[] result = new int[n];
int count = 0;
for(int i = 0; i < n; i++){
if(array[i] < 0){
result[count] = array[i];
count = count + 1;
}
}
for(int j = 0; j < n; j++){
if(array[j] > 0){
result[count] = array[j];
count = count + 1;
}
}
return result;
}
}
Find min in vector which will be O(n) and the using min as pivot do stable_sort?
int minPositive(vector<int> v) {
int minP = std::numeric_limits<int>::max();
for(int i: v) {
if(i > 0) {
if(i < minP)
minP = i;
}
}
return minP;
}
// O(1) space
void sort_1(vector<int> &v) {
vector<int>::iterator _min = min_element(v.begin(), v.end());
int min_value = 0;
min_value = minPositive(v);
stable_sort(v.begin(), v.end(), [min_value](int i, int j) {return i < min_value;});
print_vector(v);
}
int minPositive(vector<int> v) {
int minP = std::numeric_limits<int>::max();
for(int i: v) {
if(i > 0) {
if(i < minP)
minP = i;
}
}
return minP;
}
void sort_1(vector<int> &v) {
vector<int>::iterator _min = min_element(v.begin(), v.end());
int min_value = 0;
min_value = minPositive(v);
stable_sort(v.begin(), v.end(), [min_value](int i, int j) {return i < min_value;});
print_vector(v);
}
This can be solved with a variation on pivot of 0 (from quicksort).
Some solutions here tried to go that way but they do not keep relative position. In order to do that, we need a little bit more info.
1. Scan the array and count positive numbers (O(n))
2. Start with two pointers- one at the start and one in position (arrayLength - numOfPositives).
3. As long as the first pointer points to a positive number, swap elements and increment second pointer.
4. If first points to negative number, increment first pointer.
This works because instead of going backwards you swap the positive integers in order.
This allows us to pivot without losing order. Unless I am missing something, this is O(n) time and O(1) space.
public void pivotWithOrder(int[] arr) {
int posIndex = arr.length - getNumOfPositives();
if (posIndex == 0 || posIndex == arr.length)
return;
int origPosIndex = posIndex;
int negIndex = 0;
while (negIndex < origPosIndex) {
if (arr[negIndex] < 0) {
swap(arr, negIndex, posIndex);
posIndex++;
}
else negIndex++;
}
}
O(n) time O(1) space Ruby solution
def strangesort(array)
array.each.with_index do |num, pos|
if num > 0
any = swap_next_negative(array, pos)
return array unless any
end
end
end
def swap_next_negative(array, pos)
array[pos+1 .. -1].each.with_index do |num, i|
index = i + pos + 1
if num < 0
while index > pos
array[index] = array[index -= 1]
end
array[pos] = num
return true
end
end
false
end
in python
input = [ -1, 1, 3, -2, 2]
output = [0] * len(input)
negatives = 0
for t in input:
if t < 0:
negatives += 1
negativeIndex = 0
positiveIndex = negatives
for t in input:
if t < 0:
output[negativeIndex] = t
negativeIndex += 1
else:
output[positiveIndex] = t
positiveIndex += 1
print(output)
Python code
input = [ -1, 1, 3, -2, 2]
n = len(input)
output = [0] * n
negativeIndex = 0
positiveIndex = n - 1
for i, t in enumerate(input):
if input[i] < 0:
output[negativeIndex] = input[i]
negativeIndex += 1
if input[n - 1 - i] > 0:
output[positiveIndex] = input[n - 1 - i]
positiveIndex -= 1
print(output)
time: o(n)
memory: o(1)
//
// LinkedList.m
// AlgorythmsPlayground
//
// Created by Kirill Kirikov on 29.09.15.
// Copyright © 2015 Seductive. All rights reserved.
//
#import "SortingLinkedList.h"
@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end
@implementation Node
- (instancetype) initWithValue:(int)value {
self = [super init];
if (self) {
self.value = value;
}
return self;
}
@end
@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end
@implementation SortingLinkedList
- (void) insert:(int) elem {
Node *node = [[Node alloc] initWithValue:elem];
if (elem <= 0) {
[self insertNegative:node];
} else {
[self insertPositive:node];
}
}
- (void) insertNegative:(Node *)node {
if (!self.negative) {
if (self.head) {
node.next = self.head;
}
self.head = node;
} else {
node.next = self.negative.next;
self.negative.next = node;
}
self.negative = node;
}
- (void) insertPositive:(Node *)node {
if (!self.head) {
self.head = node;
} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}
self.positive = node;
}
- (void) print {
Node *iterator = self.head;
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}
@end
Time: o(n)
Memory: o(1);
//
// LinkedList.m
// AlgorythmsPlayground
//
// Created by Kirill Kirikov on 29.09.15.
// Copyright © 2015 Seductive. All rights reserved.
//
#import "SortingLinkedList.h"
@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end
@implementation Node
- (instancetype) initWithValue:(int)value {
self = [super init];
if (self) {
self.value = value;
}
return self;
}
@end
@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end
@implementation SortingLinkedList
- (void) insert:(int) elem {
Node *node = [[Node alloc] initWithValue:elem];
if (elem <= 0) {
[self insertNegative:node];
} else {
[self insertPositive:node];
}
}
- (void) insertNegative:(Node *)node {
if (!self.negative) {
if (self.head) {
node.next = self.head;
}
self.head = node;
} else {
node.next = self.negative.next;
self.negative.next = node;
}
self.negative = node;
}
- (void) insertPositive:(Node *)node {
if (!self.head) {
self.head = node;
} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}
self.positive = node;
}
- (void) print {
Node *iterator = self.head;
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}
@end
Time: o(n)
Memory: o(1);
//
// LinkedList.m
// AlgorythmsPlayground
//
// Created by Kirill Kirikov on 29.09.15.
// Copyright © 2015 Seductive. All rights reserved.
//
#import "SortingLinkedList.h"
@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end
@implementation Node
- (instancetype) initWithValue:(int)value {
self = [super init];
if (self) {
self.value = value;
}
return self;
}
@end
@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end
@implementation SortingLinkedList
- (void) insert:(int) elem {
Node *node = [[Node alloc] initWithValue:elem];
if (elem <= 0) {
[self insertNegative:node];
} else {
[self insertPositive:node];
}
}
- (void) insertNegative:(Node *)node {
if (!self.negative) {
if (self.head) {
node.next = self.head;
}
self.head = node;
} else {
node.next = self.negative.next;
self.negative.next = node;
}
self.negative = node;
}
- (void) insertPositive:(Node *)node {
if (!self.head) {
self.head = node;
} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}
self.positive = node;
}
- (void) print {
Node *iterator = self.head;
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}
@end
/*
We can use some data structure which protects the order like LinkedList.
Here I am marking all negatives with 1 and positives with 2 and corresponding to that I am maintaining a linkedlist which we can print at end.
Basically Map one linkedlist to 1 i.e. the mark for negatives and
one with 2 i.e. the mark for positives now print them separately preventing their relative order
*/
import java.util.*;
public class test{
public static void main(String[] args){
LinkedHashMap<Integer,LinkedList<Integer>> m = new LinkedHashMap<Integer,LinkedList<Integer>>();
int a[] = {-1,1,2,-3,2};
for(int i = 0; i< a.length; i++){
if(a[i] < 0){
if(!m.containsKey(1)){
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(a[i]);
m.put(1,temp);
}else{
m.get(1).add(a[i]);
}
}else{
if(!m.containsKey(2)){
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(a[i]);
m.put(2,temp);
}else{
m.get(2).add(a[i]);
}
}
}
LinkedList<Integer> l = m.get(1);
Iterator i = l.iterator();
while(i.hasNext()){
System.out.print(i.next()+" ");
}
l = m.get(2);
i = l.iterator();
while(i.hasNext()){
System.out.print(i.next()+" ");
}
}
}
I think this is just about the most readable solution (in Java):
public static int[] signSort(int[] input) {
int[] ans = new int[input.length];
int index = 0;
for(int i = 0; i < input.length; i++) {
if(input[i] < 0) {
ans[index++] = input[i];
}
}
for(int i = 0; i < input.length; i++) {
if(input[i] > 0) {
ans[index++] = input[i];
}
}
return ans;
}
It's O(n) runtime, O(n) space, so not ideal.
O(n), O(n) solution:
public static void reorder(int[] array){
int totalNegativ=0;
for(int i=0; i < array.length; i++){
if(array[i] < 0)
totalNegativ++;
}
int[] positions = new int[array.length];
int negativLeft = totalNegativ;
int positivMeet = 0;
for(int i=0; i < array.length; i++){
if(array[i] < 0){
positions[i] = i - positivMeet;
negativLeft--;
}else{
positions[i] = i + negativLeft;
positivMeet++;
}
}
for(int i=0; i<array.length; i++){
while(positions[i]!=i){
swap(array, positions, i, positions[i]);
}
}
}
private static void swap(int[] array, int[] positions, int i, int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
tmp = positions[i];
positions[i] = positions[j];
positions[j] = tmp;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vc;
vector<int> vc1;
vector<int> vc2;
int n,i,x;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
vc.push_back(x);
}
for(i=0;i<vc.size();i++)
{
if(vc[i]<0)
{
vc1.push_back(vc[i]);
}
else
{
vc2.push_back(vc[i]);
}
}
vc.clear();
for(i=0;i<vc1.size();i++)
{
vc.push_back(vc1[i]);
}
for(i=0;i<vc2.size();i++)
{
vc.push_back(vc2[i]);
}
for(i=0;i<vc.size();i++)
{
cout<<vc[i]<<" ";
}
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vc;
vector<int> vc1;
vector<int> vc2;
int n,i,x;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
vc.push_back(x);
}
for(i=0;i<vc.size();i++)
{
if(vc[i]<0)
{
vc1.push_back(vc[i]);
}
else
{
vc2.push_back(vc[i]);
}
}
vc.clear();
for(i=0;i<vc1.size();i++)
{
vc.push_back(vc1[i]);
}
for(i=0;i<vc2.size();i++)
{
vc.push_back(vc2[i]);
}
for(i=0;i<vc.size();i++)
{
cout<<vc[i]<<" ";
}
}
Time O(n), space O(1)
C code:
void sort(int *a, int size)
{
int pivot = 0, runner = 0;
while (runner < size)
{
if (a[runner] < 0)
{
swap (a[runner], a[pivot]);
pivot++;
}
runner++;
}
}
**It can be done in O(n) and space O(1).**
we need to scan 3 times through the array and change some values carefully.
Assumption: the max value in the array with size N is should be smaller than (N+1) * Interger.MAX_VALUE.
We need this assumption since we well change some positive values in the array.
- in the first scan, find # of negative and positive values, and the max.
- in the second scan we create the negative section of array as follows:
we start from the beginging of the array and we "**swap**" the first found positive number (e.g. at index i) with the first found negative number (e.g. j). since negative number are being considered with respect to their location, the swap will be okay. the problem is the positive numbers because there might be some other positive numbers between i and j. To handle this issue, we have to somehow encode the index of the positive number in that value before swaping. so then we can realize where it was at the first point. we can do this by a[i]=(i+1)*(max)+a[i].
- in the third scan, we create the positive section of array. by end of the second scan, the negative array is constructed, and the positive numbers are shifted to the right side, but their location may not be correct. So we go though it and correct their position since this info was encoded 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;
}
}
Seriously, this is super simple for O(n) time and constant space
public List<Integer> signSort(List<Integer> input) {
List<Integer> negatives = new ArrayList<>();
List<Integer> zeros = new ArrayList<>();
List<Integer> positives = new ArrayList<>();
for(Integer n : input) {
if(n<0)
negatives.add(n);
else if(n==0)
zeros.add(n);
else
positives.add(n);
}
List<Integer> sorted = new ArrayList<>();
sorted.addAll(negatives);
sorted.addAll(zeros);
sorted.addAll(positives);
return sorted;
}
easy to make a sort using code similar to quick sorts but no need to recursively partition. O(n) time O(1) space:
#include <stdio.h>
#define SIZEOF_ARRAY( arr ) sizeof( arr ) / sizeof( arr[0] )
void sort(int nums[], int n) {
int i = 0, j = n - 1;
while (i < j) {
while (nums[i] < 0) {
i++;
}
while (nums[j] > 0) {
j--;
}
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
}
void printArr (int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main (void) {
int arr[] = {4,8,2,1,3,-6,-4,7,-8,-9,-10};
printArr(arr,SIZEOF_ARRAY(arr));
sort(arr,SIZEOF_ARRAY(arr));
printArr(arr,SIZEOF_ARRAY(arr));
return 0;
}
My solution is to iterate over the list once. First make a temp copy of the list and then iterate over the list. While iterating, if the number is negative then pop it out of the temp list and then add it back to the end of temp list. For the positive numbers, do the opposite which is to pop the number out from the temp list and then add it to the front of the temp list, which also a reverse order for the positive numbers. Keep track of count for positive numbers, so you can slice the final temp list into positive and negative lists. Now, you just need to reverse the positive list and append the two lists into a single list as a return value.
[-1,1,3,-2,2]
After iterating over the original list
[2,3,1,-1,-2]
After slicing by positive-integer count
[2,3,1] [-1,-2]
After reversing positive list
[1,3,2] [-1,-2]
Return
[-1,-2,1,3,2]
#!bash/bin/python
def reorderList(num_ary):
temp = num_ary[:]
count = 0
for i in num_ary:
temp.pop(i)
if i < 0:
temp.append(i)
else:
temp.insert(0,i)
count += 1
return temp[count:len(temp)] + temp[0:count][::-1]
print reorderList([-1,1,3,-2,2])
[-1, -2, 1, 3, 2]
def sort(l):
'''Question doesn't specify how to deal with zeros (positive values or should they be
in the middle?). This implementation puts them in the middle.
Algorithm is O(n) time, O(1) space.
'''
index = 0
zeros = 0
for _ in range(len(l)):
## since we want negatives on the left,
## leave an entry alone if it's negative
if l[index] < 0:
index += 1
continue
## if the entry is positive,
## move it to the end but keep
## index the same.
if l[index] > 0:
l += [l.pop(index)]
continue
## Finally, if l[index] is zero
## increase the number of zeros to be
## added after and pop zero
if l[index] == 0:
l.pop(index)
zeros += 1
continue
return l[:index]+[0]*zeros+l[index:]
could you teach me what is the time complexity and space complexity below code?
import unittest
def rearrange(array):
# max = len(array)
p = 0
for i in range(0, len(array)):
cur = array[p]
if cur >= 0:
array.append(cur)
del array[p]
else:
p += 1
return array
class Test(unittest.TestCase):
def test(self):
self.assertEqual(rearrange([-1, 1, 3, -2, 2]), [-1, -2, 1, 3, 2])
self.assertEqual(rearrange([1, -3, 4, 2, -4, 5]), [-3, -4, 1, 4, 2, 5])
self.assertEqual(rearrange([1, -3, 4, 2, -4, 0]), [-3, -4, 1, 4, 2, 0])
self.assertEqual(rearrange([1, -3, 4, 0, 2, -4]), [-3, -4, 1, 4, 0, 2])
if __name__ == "__main__":
unittest.main()
#include <iostream>
#include<algorithm>
using namespace std;
bool compare(int i,int j)
{
if(i<0 && j<0)
return false;
else if(i>=0 && j>=0)
return false;
else
return i<j;
}
int main() {
// your code goes here
int a[5]={-1,1,3,-2,2};
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<"\n";
sort(a,a+5,compare);
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
return 0;
}
I have an O(n^2) solution, but I think it's easy to understand.
public void rearrangeArray2(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int firstNegative = 0;
int q = 0;
while (firstNegative < nums.length && nums[firstNegative] > 0) {
firstNegative++;
}
q = firstNegative;
while (q < nums.length) {
while (nums[q] < 0) {
q++;
}
if (q == nums.length) {
break;
}
for (int i = q; i > firstNegative; i--) {
int tmp = nums[i - 1];
nums[i - 1] = nums[i];
nums[i] = tmp;
}
firstNegative++;
q++;
}
}
import java.util.*;
public class check {
private static final int[] arr = { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };
public static void main(String[] args){
int c = 0;
int[] pos = new int[arr.length];
for(int i=0;i<arr.length;i++) {
if(arr[i]<0) {
pos[c] = i;
c++;
}
}
for(int j=0;j<arr.length;j++) {
if(arr[j]>=0) {
pos[c] = j;
c++;
}
}
for(int k=0;k<arr.length;k++) {
System.out.println(arr[pos[k]]);
}
}
}
array = [-1, 1, 3, -2, 2]
if __name__ == '__main__':
first_positive_number_index = -1
last_number_was_positive = False
for i in range(len(array)):
if (array[i] < 0):
if (first_positive_number_index >= 0):
temp = array[i]
for j in range(i, first_positive_number_index - 1, -1):
array[j] = array[j - 1]
array[first_positive_number_index] = temp
elif (array[i] == 0):
raise Exception("Unexpected input")
elif (not last_number_was_positive):
first_positive_number_index = i
last_number_was_positive = True
print(array)
I believe this to be O(n) runtime (scans the entire array 2 times) while also being O(1) memory (swaps in-place with only a few 'placeholder' variables and counters).
function arrSpecialSort2() {
let arr1 = [-1,1,3,-2,2,10,-9,-4,4,5];
let negCount = 0;
arr1.forEach(x => {
if(x < 0)
negCount++;
});
// Escape early if no negatives
if(negCount === 0)
return;
let i = 0;
let j = i+1;
console.log(`Arr NegCount - ${negCount} || i - ${i}`, arr1);
while(i < negCount) {
// If negative - continue to next element
if(arr1[i] < 0) {
i++;
}
// If positive - handle finding next positive above 'negCount' barrier then swap
else {
// console.log(`Arr - ${arr1.length} NegCount - ${negCount} || i - ${i}`, arr1);
while(arr1[j] > 0) {
j++;
}
let tmp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = tmp;
j++;
i++;
}
}
console.log(arr1);
}
#include<stdio.h>
main()
{
int n;
scanf("%d",&n);
int a[n],b[n];
int i=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}
for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}
for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}
public int[] sortInOrder(int[] data){
int pos=0;
int negPos=0;
for (pos=0;pos<data.length;) {
if(data[pos]>=0){
while(negPos<data.length && data[negPos]>=0 ){
negPos++;
}
if(negPos==data.length)
break;
while(negPos>pos){
int temp=data[negPos];
data[negPos]=data[negPos-1];
data[negPos-1] = temp;
negPos--;
}
}
negPos++;
pos++;
}
return data;
}
It cannot be done in O(n) . If it can done in O(n), then lower bound for comparision based sorting is O(n) which is false. So, the order is O(nlogn) and space is O(1)
void sort(vector<int>& a)
{
int n = a.size();
int i = 0 ;
while (i < n && a[i] < 0) i++;
while (i < n)
{
int j = i;
while (j < n && a[j] > 0) j++;
int k = j;
while (k < n && a[k] < 0) k++;
if (k < n) {
rev(a, i, j-1);
rev(a, j, k-1);
rev(a, i, k-1);
}
i = i + (k-j);
}
}
#include <iostream>
#include <iostream>
using namespace std;
int arr[] = {1,2,-1,1,3,-2,2};
void reverse(int i, int j){
while(i<j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++; j--;
}
}
void rotatelist(int i, int j, int k){
reverse(i,j-1);
reverse(j, k);
reverse(i,k);
}
int transform(int N){
/****
arr 1 2 -1 1 3 -2 2
index 0 1 2 3 4 5 6
k = 5
j = 5
i = 3
such that j<= x <=k , arr[x] is negative number
such that i<= x <j , arr[x] is positive number
***/
int k = N-1, j, i;
while(k>=0 && arr[k]>=0)
k--;
j = k;
do {
while(j>=0 && arr[j]<0)
j--;
j++;
i = j-1;
while(i>=0 && arr[i]>=0) i--;
i++;
rotatelist(i, j, k);
k = i + (k-j);
j = i-1;
}while(j>0);
}
int main(){
int N = sizeof(arr) / sizeof(arr[0]);
for(int i=0;i<N;i++)
cout << arr[i] << ' ' ;
cout << endl;
transform(N);
for(int i=0;i<N;i++)
cout << arr[i] << ' ' ;
cout << endl;
}
The inplace quicksort doesn't remain the order.
-1 1 3 -2 2 and pivot 0 it would give -1 -2 3 1 2 instead of -1 -2 1 3 2
Here is an O(n) solution without extra space.
void sort(int array[]){
int pos_p = -1;
int num_n = 0;
for(int a:array)
if(a<0) num_n++;
for(int i=0;i<array.length;i++){
if(array[i]>0){
if(pos_p == -1)
pos_p = i;
else
if(num_n > 0)
swap(array, i, pos_p);
}else{
num_n--;
if(pos_p >= 0){
swap(array, i, pos_p);
if(num_n>0)
pos_p = i;
else
pos_p = -1;
}
}
}
}
void swap(int array[], int i, int j){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
1.Start counters i at 0th index and j at nth index of the array.
2.Increase i until arr[i]>=0
3.Decrease j until arr[j]<0
4.swap arr[i] ,arr[j]
5.repeat steps 2, 3,4 till i<j
time-O(n),space-O(1)
Man I 'm so sorry , here is the algo :
e.g {-1,2,8,1,-2,4} is the array
1)start i as 0, j as 0
2)while j<n
inc j by one
if arr[j] is negative ,
make arr[i] as this neg number arr[j]
inc i by 1
and shift all the elements from arr[i to j-1] by one position
but again i 'm afraid it is O(n^2) WC and O(1) space :| ,sorry for not having read the memory constraints above,,actually this shifting procedure is O(N) itself :/
This problem has a O(n) time and O(1) space complexity solution if relative ordering is not a factor. To keep space constant you have to use n^2 operations (swaps and compares) to rearrange the array. To keep operations constant you would need to allocate additional memory to keep track of where each positive/negative entry will need to land.
Also note that I am making the assumption that 0 is treated like a positive number, although I would clarify this point with the interviewer to ensure correctness.
O(n) time, O(1) space without ordering solution:
1. Start with two pointers, one at the front and one at the end ( i=0, j = array.length -1). While i is less than j repeat steps 2-4.
2. Evaluate i - if it is less than 0 increment it by 1
3. Evaluate j - if it is greater than or equal to 0 decrement it by 1
4. Evaluate i && j - if i is greater than or equal to zero AND j is less than 0 then swap the elements. Increment i and decrement j.
Here is a working sample:
public static void sort(int[] a){
int i = 0;
int j = a.length - 1;
int tmp;
while(i < j){
if(a[i] >= 0 && a[j] < 0){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
continue;
}
if(a[i] < 0){i++;}
if(a[j] >= 0){j--;}
}
}
@masterjaso
I don't think your algorithm will ensure the relative positions of both +ve and -ve numbers. Will you algorithm work for [-1 1 -2 2 -3 3]?
This paper:
"Stable minimum space partitioning in linear time"
by
Jyrki Katajainen,
Tomi Pasanen
does it in O(n) time and O(1) space, and maintains the relative order (which is what makes the problem difficult), and hence the usage of the word "stable" as the very first word in the title of the paper.
@ Erasmus
You are correct, my shown algorithm does not maintain the relative order (as disclosed in my comments). I do want to thank you for the sample, it helped me identify a bug and I have amended my post with updated and correct code.
This can be done in O(nlogn) using divide and conquer scheme. Before starting the algorithm, please see the following observation:
- Jason Ding August 30, 2013Observation: given an array A, say [1, -2, ..., 4], with n elements, we can get the inverse of A, denoted as A’ (4, …, -2, 1), in \theta(n) time with O(1) space complexity.
The basic idea of the algorithm is as follows:
1. We recursively ‘sort’ two smaller arrays of size n/2 (here ‘sort’ is defined in the question)
2. Then we spend \theta(n) time merging the two sorted smaller arrays with O(1) space complexity.
How to merge?
Suppose the two sorted smaller array is A and B. A1 denotes the negative part of A, and A2 denotes positive part of A. Similarly, B1 denotes the negative part of B, and B2 denotes positive part of B.
2.1. Compute the inverse of A2 (i.e., A2’) in \theta(|A2|) time; compute the inverse of B1 (i.e., B1’) in \theta(|B1|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array AB (i.e., A1A2B1B2) becomes A1A2’B1’B2.
2.2. Compute the inverse of A2’B1’ (i.e., B1A2) in \theta(|A2|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array A1A2’B1’B2 becomes A1B1A2B2. We are done.
Time complexity analysis:
T(n) = 2T(n/2) + \theta(n) = O(nlogn)