Sort Array

Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).

Solution:
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)

Matrix Sorted Search Problem

Given a Matrix of size n*n and an element E to search in the Matrix. Each row and each column of the Matrix is sorted. We need to find an efficient algorithm to search this matrix.

Solution:

Take the last element of the first row and go either down or left using the following logic:

1. If the search element E is greater than the current element go down one step. i.e change the row to the next row.

2. If the search element E is less than the current element then go one step to the left. i.e change the col = col - 1.

Do the above operation till u find the element E or you have reached the end of the Matrix. End of the Matrix means we cannot move either to left or down.

Runtime of the algorithm would be around O(n).

Original array

/*
You are given an array of n numbers and each element is equal to the value of numbers less than that number in right hand side of the original array we have to find the original array
for ex. if the original array is 4,1,3,2
then we would we given the array 3,0,1,0
and we have to find the original array ,it is given that the numbers in the original array is from 1 to n.
ex no 2. original array 2,3,1,4
given array 1,1,0,0
ex no. 3 original array 5,2,1,3,4
given array 4,1,0,0,0
*/
Solution1:
main()
{
int *array;
int *value;
int *input;
int *orig;
unsigned int origIndex = 0;
unsigned int size = 0;
unsigned int sizeValue = 0;
unsigned int sizeArray = 0;
int i,j,k;
printf("Enter the size of input Array: ");
scanf(" %d",&size);
input = (int *)malloc(sizeof(int)*size);
array = (int *)malloc(sizeof(int)*size);
value = (int *)malloc(sizeof(int)*size);
orig = (int *)malloc(sizeof(int)*size);
for(i=0;i lessThan size;i++)
{
printf("Enter arr[%d]=",i);
scanf(" %d",&input[i]);
array[i] = i+1;
value[i] = i;
orig[i] = 0;
}
sizeValue = size;
for(i=0;i lessThan size;i++)
{
for(j=0;j lessThan sizeValue;j++)
{
if(input[i] == value[j])
{
orig[origIndex] = array[j];
origIndex++;
/*Shift the array and its value*/
for(k=j+1;k lessThan sizeValue;k++)
{
value[k] = (value[k] == 0)? 0: (value[k]-1);
}
for(k=j;k lessThan sizeValue-1;k++)
{
array[k] = array[k+1];
value[k] = value[k+1];
}
sizeValue--;
break;
}
}
}
printf("\n");
for(i=0;i lessThan size;i++)
printf("%2d",orig[i]);
printf("\n");
}



Solution2:
Let us assume that output has n elements.
We init an array say helperArray[i] = i; for i from 1 till n
Also have an outputArr[] which is init to 0.

Now take the input array inputArr[].
Step1. Check what is inputArr[i] let it be k.
Step2. Then we ask this qn what is the number which has exactly k lesser elements than itself. For this we check the helperArray[] and find the element from there. Let that element be helperArray[j]. Now strike of this element and do the above step again. But we dont take the striked off elements into considerations.

We take a simple example
let input 4 1 0 0 0
output 0 0 0 0 0
helper 1 2 3 4 5

Iteration1: k = 4 then output[0] = 5 as number which has 4 less numbers is 5
strike of 5 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 0 0 0 0
helper 1 2 3 4

Iteration2: k = 1 then output[1] = 2 as number which has 1 less numbers is 2
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 0 0 0
helper 1 3 4

Iteration3: k = 0 then output[2] = 1 as number which has 0 less numbers is 1
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 0 0
helper 3 4

Iteration4: k = 0 then output[3] = 3 as number which has 0 less numbers is 3
strike of 3 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 0
helper 3 4

Iteration5: k = 0 then output[4] = 4 as number which has 0 less numbers is 4
strike of 4 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 4
helper

Median

/*********************************************
X[1...n] and Y[1....n] are 2 sorted arrays....
give O(log n) algo to find median of the array
formed by merging the 2 arrays
*********************************************/

/***
Take the middle of Arr X call it midX and middle element of
Arr Y call it midY..
***/
int findMedian(Array arrX[])
{
lowX=0
lowY=0
highX=arrX.size - 1
highY=arrY.size - 1

midX = (highX - lowX)/2
midY = (highY - lowY)/2
while(lowX != highX || lowY !=highY)
{
if(midX < midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowX=midX
highY=midY
midX = midX + (highX - lowX)/2;
midY = (highY - lowY)/2;
**/
}
else if (midX > midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowY =midY
highX=midX
midY = midY + (highY - lowY)/2;
midX = (highX - lowX)/2;
**/
}
else
{
printf("median %d",arrX[midX]);
return arrX[midX];
}
}
return arrX[midX];/*or return arrY[midY]*/
}