Find the minimum element in a sorted and rotated array

/*
-- Base Conditions of array
-- Divide and Conquer Algorithm
-- Find middle element
-- Condition for return result
-- Condition for return left sub array
-- Condition for return right sub array
-- return result if except all test cases
*/

static int minimumElement(int[] a, int l, int r){
if (a == null || r == -1) return -1;
if(l == r) return a[l];

int m = l + (r-l)/2;

if((m-1)>=0 && a[m-1] > a[m]) return a[m];

if(a[l] > a[m]) return minimumElement(a, l, m-1);

else if(a[m] > a[r]) return  minimumElement(a, m+1, r);

return a[0];
}

References:
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Merge k sorted arrays

// define max value for min heap when array doesn't have any more element
public static final int MAX_VALUE = 10000;

static int[] mergeKArray(int a[][], int row, int col){
int count = 0;
if(row == 0 || row == 1) return a[0];
// declare final merged sorted array
int mergeArr[] = new int[row*col];

// allocation of heapNode array which has size no of row times.
heapNode[] hn = new heapNode[row];

for (int i = 0; i<row; i++)
{
hn[i] = new heapNode(a[i][0], 1, i);
//hn[i].key = a[i][0];
//hn[i].index = 1;
//hn[i].n = i;
}

// convert heapNode array to minheap
minHeap(hn);

heapNode minKeyNode;

for(int i = 0; i< row*col; i++)
{
minKeyNode = minValueHeap(hn);

mergeArr[count++] = minKeyNode.key;

if(minKeyNode.index < a[minKeyNode.n].length)
{
minKeyNode.key = a[minKeyNode.n][minKeyNode.index];
minKeyNode.index++;
}else minKeyNode.key = MAX_VALUE;

hn[0] = minKeyNode;

minHeapify(hn, 0, row);
}
return mergeArr;
}

private static void minHeap(heapNode[] hn) {
int n = hn.length;
if(n == 0 || n == 1) return;
for(int i=n/2; i>=0; i--)
{
minHeapify(hn,i,n);
}
}

private static void minHeapify(heapNode[] hn, int i, int n){
int minIndex = i;
int l = left(i);
int r = right(i);
if(l < n && (hn[l].key < hn[i].key))
{
minIndex = l;
}
if(r < n && (hn[minIndex].key > hn[r].key))
{
minIndex = r;
}

if(minIndex != i)
{
swap(hn, minIndex, i);
minHeapify(hn, minIndex, n);
}
}

private static void swap(heapNode hn[], int minIndex, int i){
heapNode tmp = hn[i];
hn[i] = hn[minIndex];
hn[minIndex] = tmp;
}


private static heapNode minValueHeap(heapNode hn[]){
return hn[0];
}

private static int right(int i) {
return 2*i+2;
}

private static int left(int i) {
return 2*i+1;
}


References:
http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Count all distinct pairs with difference equal to k

-- If difference of curr and prev index value is equal to k, increment count by 1
-- curr greater than prev and difference of values less than k, increment curr.
-- curr greater than prev and difference of values legreater than k, increment prev.


static int countPairsWithDiffK(int a[], int k){
int n = a.length;
if(n == 0 || n == 1) return 0;
int count = 0, rem_curr = 0;
Arrays.sort(a);
for(int curr = 1, prev = 0; curr < n; )
{
if(a[curr] - a[prev] == k)
{
if(a[curr] != a[rem_curr])
{
System.out.println(a[curr]+", "+a[prev]);
count ++;
}
rem_curr = curr;
curr ++;
}
else if(curr > prev && a[curr] - a[prev] < k)
{
curr ++;
}else if(curr > prev && a[curr] - a[prev] > k)
{
prev ++;
}else curr ++;


}
return count;
}


References:
http://www.geeksforgeeks.org/count-pairs-difference-equal-k/

Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

Idea is to multiply each array element  with n(no of elements) and get remainder of final array

static void rearrangeArr(int a[]){

int n = a.length;
if(n == 0 || n == 1) return;

for(int i = 0 ; i < n; i++)
{
a[i] = a[i]*n;
}

for(int i = 0; i < n; i++)
{
a[i] = a[i] + a[a[i]/n] /n;
}
for(int i = 0; i < n; i++)
{
a[i] = a[i]%n;
System.out.print(a[i] +" ");
}
}


References:
http://www.geeksforgeeks.org/rearrange-given-array-place/