Merge two sorted arrays - One having big enough buffer to hold another

Problem

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Another way to ask same question

Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example

array1 = {1, 3, 6}
array2 = {2, 4, 5, _, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

Solution

Method 1 - Merge sort
This is part of the merge-sort. Let the position of the last element located in the 2 arrays is called tail. Also, for array B, end is same as tail of the array. We start with tails of the 2 arrays, and compare the 2 elements and put them at the end of the array A, whichever is maximum.

Code in java

public static void bufferMerge(int[] A, int[] B, int sizeAdata) {
    // Assume sizeAdata + sizeB = A.length
    // i.e., B exactly fits into the buffer at the end of A
    int aEnd = A.length - 1; // Index of last location of array A
    int aTail = sizeAdata - 1;// Index of last element in array A
    int bTail = B.length - 1;// Index of last element as well as 
       //last location in array B

    // Start comparing from the last element and merge A and B
    while (aTail >= 0 && bTail >= 0) {
        if (A[aTail] > B[bTail]) {
            A[aEnd--] = A[aTail--];
        } else {
            A[aEnd--] = B[bTail--];
        }
    }
    while (bTail >= 0) {
        A[aEnd--] = B[bTail--];
    }
}

Time Complexity - O (m+n) where size of A as m and size of B as n. So , a linear time algorithm.

Similar Problem:

Question : Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2) which are scattered throughout the array, merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example:
array1 = {1, 3, 6}
array2 = {2, _,4 , 5, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

Again solution is same as above, but first make array 2 to skip all the whitespaces and make it like this:
array2 = {2, ,4 , 5, _, _,_}

Read More

Number of unique elements in sorted array with repeated elements

Problem

Find the number of unique elements in sorted array with repeated elements.
Follow up - How can you do it without using extra space

Example
Input = [1,1,1, 2]
Output = 2 i.e. 1 and 2.

Example for follow up
Input = [1,1,2]
Output = 2



Solution
It's not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. If you do restrict the collection to only having unique items, then the answer is trivial; it's the number of items in the collection since they all have to be distinct.

But now lets take the case, where we can't use any space - we have to simply compare the adjacent space.
Method 1 - Iterate through the array and compare adjacent elements

Here is the code (java) which returns the number of unique elements and changes the array structure inplace to contain only unique elements :

public int removeDuplicates(int[] A) {
    if(A.length < 2)
        return A.length;

    int j = 0;
    int i = 1;

    while(i < A.length){
        if(A[i] == A[j]){
            i++;
        }else{
            A[++j] = A[i++];
        }    
    }

    return j+1;
}

Time complexity - O(n)

Method 2- Using hashtable
Here we can add the element to hashset if it is not present, otherwise ignore it. This size of hashset will give us the number of unique elements. But this is not very useful as array is already sorted. So method 1 is better approach.

Read More

Finding the biggest difference between sorted array values

Problem

finding the biggest difference between sorted array values

Example 
Consider the array : 
var array = array(1,4,7,8,12,15);
The values in the array will always be integers and is sorted, and elements may repeat.

Now, we want to print out the biggest step in the array. step is difference between adjacent element:
step array - (-,3,3,1,4,3)

The biggest step is 4, between 8 and 12.


Solution

Method 1- Brute force

var max=0;
for (i=1; i<array.length; i++)
    max = Math.max(max,array[i]-array[i-1]);

Reference - stackoverflow

Read More

Sorted Linked List to Balanced BST

Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.

Example : 

Input: Linked List 1->2->3->4->5->6->7
Output: A Balanced BST
        4
      /   \
     2     6
   /  \   / \
  1   3  4   7  

Lets discuss 2 approaches for this problem.

Solution
Method 1 (Simple)
Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

Time complexity: O(nLogn) where n is the number of nodes in Linked List.This is because each level of recursive call requires a total of n/2 traversal steps in the list, and there are total log(n) number of levels.

Method 2 (Tricky)
The method 1 constructs the tree from root to leave, i.e. top down approach.

Now lets follow bottom up approach. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.

public TreeNode sortedListToBST(ListNode head,int start, int end) {
 if(start>end) return NULL;
 int mid = (start+end)/2;
 TreeNode leftChild = sortedListToBST(list, start, mid-1);
 TreeNode parent = new TreeNode();
 if(parent==null)
  System.out.println("Memory error");
 parent.setData(list.getData());
 parent.setLeft(leftChild);
 list = list.getNext();
 parent.sertRight(sortedListToBST(list,mid+1,end));
 return parent;
}
//method caller
sortedListToBST(head,0,n-1);

While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
Time complexity = O(n)

Read More

Convert sorted array to Balanced BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/convert-sorted-array-to-height-balanced-binary-search-tree/.

Problem 

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Examples

Input: 1 2 3 4 5 6 7

Output:

    4
   / \
  3   6
 / \ / \
3  4 6  7

Solutions

 Method 1 - Take the array's middle element and insert it recursively

• Pick up the middle element of the array
• Set it as the root
• Recursively build up left and right subtrees with lower and higher halves of the array

Here is the code in java:

public static BST sortedArrayToBST(int[] arr){
    Node bst = new Node();
    bst = sortedArrayToBST(arr, 0, arr.length-1, bst);
    return bt;
}

private static Node sortedArrayToBST(int[] arr, int start, int end) {

    if( start == end){
        bst.insert(new Node(arr[start]));
        return;
    }
    else if(start > end) {
        return;
    }
    int middle = (start+end)/2;
    Node node = new Node(arr[middle]);
    //bst.insert(new Node(arr[middle]));
    node.left = sortedArrayToBST(arr, start, middle - 1);
    node.right = sortedArrayToBST(arr, middle+1, end);
    return node;
}

Time complexity - O(n)
Space Complexity - O(1) (but if you internally think of recursion, it will be kind of O(n)

Read More

Find the minimum and maximum in the array

Here are few question we find on finding min and max in the array, but array type changes.

Unsorted 1D array

• Find the maximum (OR minimum) in an array
• Find the maximum AND minimum in an array with min number of comparisons
• Find the max and second maximum in an array (likewise for minimum)
• Find the max and nth max in an array

Rotated Sorted array

• Find the minimum element in the rotated sorted array.
• Find Nth largest element in the rotated sorted array

Read More

Merge two arrays efficiently - one sorted, another unsorted

Problem

Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently.

Solution

Method 1 - Insert the elements in sorted array using binary search
Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that.
Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity.

• sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively of the cases.
• merge(part1,part2): O(n+logn) or O(n+sqrt(n)), which is O(n)¹ anyway.

So, the total complexity of both cases is O(n), which is optimal for this problem.




Source

• http://stackoverflow.com/questions/13862701/merge-two-arrays-efficiently-one-sorted-another-unsorted

Read More

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

Read More

k-way merge - Merging k sorted arrays of n elements

 Given k sorted arrays of size n each, merge them and print the sorted output.
Example:

Input:
k = 3, n =  4
arr[][] = { {1, 3, 5, 7},
            {2, 4, 6, 8},
            {0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11 

Method 1 - Merging from 1 array to other
It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.

Time complexity - O(n . k^2)

It doesn't traverse each of the k arrays once. The first array is traversed k-1 times, the first as merge(array-1,array-2), the second as merge(merge(array-1, array-2), array-3) ... and so on.
The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).
The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.

Method 2 - Merge 2 at a time, again and again.
Step 1: Merge arrays (1 and 2), arrays (3 and 4), and so on. (k/2 array merges of 2n, total work kn).
Step 2: Merge array (1,2 and 3,4), arrays (5,6 and 7,8), and so on (k/4 merges of 4n, total work kn).
Step 3: Repeat...
There will be log(k) such "Steps", each with kn work. Hence total work done = O(k.n.log(k)).
Even otherwise, if we were to just sort all the elements of the array we could still merge everything in O(k.n.log(k.n)) time.

 Method 3 - Maintain k min heaps, and get the min element from all the arrays and saving into one
A simple solution is to create an output array of size n*k and one by one copy all arrays to it. Finally, sort the output array using any O(nLogn) sorting algorithm. This approach takes O(nkLognk) time.
We can merge arrays in O(nk*Logk) time using Mean Heap. Following is detailed algorithm.
1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a the heap
3. Repeat following steps n*k times.
     a) Get minimum element from heap (minimum is always at root) and store it in output array.
     b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Source
http://stackoverflow.com/questions/11026219/why-is-k-way-merge-onk2
http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Read More

Find Nth largest element in the rotated sorted array

Question : Find Nth largest element in the rotated sorted array
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don't know. But seeing the above array we cans see that k = 2, which is also the index of minimum element i.e. 2 here. So, 3rd largest element is counting 3rd from 2 i.e. 6. Similarly for Nth largest element, it is k+N-1. But as we can see as the array is rotated, k+N-1 may overflow array, so we need to modulo operator on k+N-1, i.e. Nth largest element lies at = (k+N-1)%arraySize.

So, the problem breaks down in 2 step

1. Find k, i.e. number of rotations. To do so please refer the post - Find the rotation count in rotated sorted array
2. Return the arr[(k+N-1)%arr.size]

Here is the pseudocode:

int findNthHigehest(int[] arr, int size, int n)
{
    int k = findRotationCount(arr, size);
    return arr[(n+k-1)%size];
}

Thanks.

Read More

Find the rotation count in rotated sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array.
So, we need to find the point of inflection where we find a point such that a[i]>a[i+1].

So, finding the minimum element in the rotated sorted array has been implemented here - Find the minimum element in rotated sorted array. Thanks.

Read More

Convert array of positive numbers to sorted array

You are given an array of positive integers. Convert it to a sorted array with minimum cost.
Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of element
For example:
4,3,5,6, -> cost 1 (decrement 4)
10,3,11,12 -> cost 3  (delete 3)

Trying out DP
We can make the DP more efficient You don't need to scan the whole previous column when calculating costs of decrementing. Rather there are only two possibilities.


Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing sequence with the last element being no more than m. And we always draw m from the set V of values in a[].
So here is the new DP:

C(1, m) = max(a[1] - m, 0)  // first row only decrement is possible 
C(n, m) = min ( 
a[n] + C(n - 1, m),   // delete 
(a[n] <= m) ?  C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement 
) 

In case you don't follow, the "//delete" line is saying that we already know the cost of making everything up to element n-1 non-decreasing and no more than m. This, by recursive assumption, is just C(n-1,m). The additional cost of deleting a[n] is a[n].
The "//decrement" line is similar, but there are 2 cases. If a[n] is more than m, we must decrement it. The cost here consists of making everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m). Plus we have the cost of chopping a[n] down to m, which is a[n]-m.

In the other case, a[n] is m or less. So there's no need todecrement, but we must get the elements a[1..n-1] to be no more thana[n]. Again by recursive assumption this cost is C(n-1,a[n]).Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. Theleast cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and "m" means that a decrement was based on the value of m rather than a[n].We take the answer from C(6,5) = 5.Implementing this is a little tricky because m values are drawn from V. You could use a hash table for the m-axis. But it's more efficient to store V in an array and convert all the values of m in the DP into indices of V. Because all the indices lie in [ 1 .. |V| ], we can use  simple arrays rather than hash tables to representthe rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.For C, we also need to convert all the indices to origin 0. So here's the final O(n^2) code. I think this is a correct implementation. If anyone has an example that breaks it, I'd like to see.

Also see - http://www.careercup.com/question?id=3603906

Read More

Find the minimum element in the rotated sorted sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

// always restrict the search to the unsorted 
// sub-array. The min is always there.
public static int findMin(int[] a, int start, int end){
  int mid = (start + end)/2;
  if(start == mid){//only 1 element
    return a[mid+1];
  }else if(a[start] > a[mid]){
    return findMin(a, start, mid);
  }else if(a[mid+1] > a[start]){
    return findMin(a, mid+1, end);
  }
  //else{
  //  return a[mid+1];
  //}
}

To begin with we call findMin(array, 0, array.length-1).
Doing it iteratively:

// index of first element
l = 0

// index of last element.
h = arr.length - 1

// always restrict the search to the unsorted 
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
        // find mid.
        mid = (l + h)/2
        // decide which sub-array to continue with.
        if (arr[mid] > arr[h]) {
                l = mid + 1
        } else {
                h = mid
        }
}
// answer
return arr[l]

Read More

Search an element in the sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer: We can do a binary search with some modified checks.

So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.

Pseudocode: 

1. Find the middle of array
2. Select the sorted array part
   If a [middle]  >  a[start] - That means this part of array is sorted and is without rotation. So, we choose array to search as [start] to a[middle] otherwise we choose a[middle] to a[end].
3. Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key x lies in range of the array, we will search for the element in that range, otherwise other range. 

So, second step helps us get the sorted array on which we can apply binary search. 

Program in java

public int rotatedSearch(int[] arr, int start, int end,
                          int x){
    if(arr[start] == x){
        return start;
    } else if(arr[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }

    int middle = (start + end) / 2;

//we have no rotation between start and middle, i.e. normal sorted array
//if left sub array is sorted
   if(arr[start] <= arr[middle]){
//if x is less than middle - then x may lie in this part of array
        if(x <= arr[middle] && x >= arr[start]){
            return rotatedSearch(arr, start, middle-1, x);
        } else {
            return rotatedSearch(arr, middle+1, end, x);
        }
    }
//if right sub array is sorted
    else if(arr[middle] <= arr[end]){
        if(x >= arr[middle] && x <= arr[end] ){
            return rotatedSearch(arr, middle+1, end, x);
        } else {
            return rotatedSearch(arr, start, middle-1, x);
        }
    } else {
        return -1;
    }
}

Time Complexity - O(log n)
Thanks.

Read More

Median of 2 sorted arrays of equal size n

Question 

There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))

Solution

Before going to solution what is the median.

What is Median?

Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.


For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.
Input Array - {12,11,15,10,20}
Sorted array - { 10, 11, 12, 15, 20 }
Median - 12

There are different conventions to take median of an array with even number of elements, one can take the mean of the two middle values, or first middle value, or second middle value.

Let us see different methods to get the median of two sorted arrays of size n each. Since size of the set for which we are looking for median is even (2n), we are taking average of two middle two numbers in all below solutions.

Method 1 - Simply count while Merging(Brute force)
Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.

int getMedian(int arr1[], int arr2[], int n)
{
 int i = 0;  // Current index of array arr1[] 
 int j = 0;  // Current index of array arr2[] 
 int count;
 int m1 = -1, m2 = -1;

 //Since there are 2n elements, median will be average
 // of elements at index n-1 and n in the array obtained after
 // merging ar1 and ar2 
 for(count = 0; count <= n; count++)
 {
  //Below is to handle case where all elements of arr1[] are
  //  smaller than smallest(or first) element of arr2[]
  if(i == n)
  {
   m1 = m2;
   m2 = arr2[0];
   break;
  }

  //Below is to handle case where all elements of arr2[] are
  //  smaller than smallest(or first) element of arr1[]
  else if(j == n)
  {
   m1 = m2;
   m2 = arr1[0];
   break;
  }

  if(arr1[i] < arr2[j])
  {
   m1 = m2;  //Store the prev median
   m2 = arr1[i];
   i++;
  }
  else
  {
   m1 = m2;  //Store the prev median 
   m2 = arr2[j];
   j++;
  }
 }    

 return (m1 + m2)/2;
}    

// Driver program to test above function 
int main()
{
 int arr1[] = {1, 12, 15, 26, 38};
 int arr2[] = {2, 13, 17, 30, 45};

 printf("%d", getMedian(ar1, ar2, 5)) ;

 getchar();
 return 0;
}

Time Complexity - O(n)

Dry running the algorithm
A1 = { 1,12,15,26,38}
A2 = {2,13,17,30,45}

Initially i=0,j=0,m1=m2=-1

So, we reach arr1[i] < a[j] i.e. arr1[0]<arr2[0] which is true.

Method 2 - By comparing the medians of two arrays(Divide and Conquer)
This method works by first getting medians of the two sorted arrays and then comparing them.

Here is an exemple of how it works. Imagine we have these two sorted lists:

l1 = [1, 4, 5, 7, 7, 8, 9, 9] 
l2 = [0, 1, 3, 6, 6, 6, 7, 8]

We calculate the median of both lists:

l1 median = 7
l2 median = 6

l1 median is greater than l2 median so we can safely remove the numbers on the right side of the median of l1 because the final median is somewhere between the median of both. We also have to remove the same amount of numbers at the left side of l2 to keep the stability of the final list. If one of the list is shorter the amount of removed numbers will the minimum between both median index. So we get:

l1 = [1, 4, 5, 7, 7]
l2 = [6, 6, 6, 7, 8]

We continue the process until have a list with 2 numbers (or less).

l1 median = 5
l2 median = 6

We remove 2 from left side of l1, we remove 2 from right side of l2.

l1 = [5, 7, 7]
l2 = [6, 6, 6]

l1 median = 7
l2 median = 6

We remove 1 from left side of l2, we remove 1 from right side of l1.

l1 = [5, 7]
l2 = [6, 6]

Remember that we have 2 list of the same size. In another case one could be an order of magnitude bigger than the other. Finaly we have to deal with some special case:

1. The 2 remaining numbers have to be inserted on the left side of the median of the other list.
2. The 2 remaining numbers have to be inserted on the right side of the median of the other list.
3. One have to be inserted on the left side of the median and the other on the right side.

For each case we have to check if the number could change the median of the resulting list. If we decide to insert l1 into l2, there will be no implication on the initial median value of l2. But if we decide to insert l2 into l1, the median of l1 will be completly changed. In both case we optain this list [5, 6, 6, 7] and calcuate the median of it : 6.
Inserting the two remaining value into the other list is not the fastest thing possible but it's simple and understandable.

Algorithm (Divide and Conquer):

1) Calculate the medians m1 and m2 of the input arrays ar1[]
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
     return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
   of the below two subarrays.
    a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
   of the below two subarrays.
   a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
   becomes 2.
6) If size of the two arrays is 2 then use below formula to get
  the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

To sum up, actual median M will lie between m1 and m2. If m1 & gt; m2 => M lies between m2 to m1, so all elements less than m1 but more than m2, hence first half of ar1 and 2nd half of ar2. Likewise for m2>m1.

Time Complexity = O(lg n)

Here is the code:

// This function returns median of ar1[] and ar2[].
// This function returns median of ar1[] and ar2[].
//   Assumptions in this function:
//   Both ar1[] and ar2[] are sorted arrays
 //Both have n elements 
int getMedian(int ar1[], int ar2[], int n)
{
  int m1; // For median of ar1 
  int m2; // For median of ar2 
 
  // return -1  for invalid input 
  if(n <= 0)
    return -1;
 
  if(n == 1)
    return (ar1[0] + ar2[0])/2;
 
  if (n == 2)
    return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
 
  m1 = median(ar1, n); // get the median of the first array 
  m2 = median(ar2, n); // get the median of the second array 
 
  // If medians are equal then return either m1 or m2 
  if(m1 == m2)
    return m1;
 
  // if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] 
  if (m1 < m2)
    return getMedian(ar1 + n/2, ar2, n - n/2);
 
  // if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] 
  return getMedian(ar2 + n/2, ar1, n - n/2);
}
 
// Driver program to test above function 
int main()
{
  int ar1[] = {1, 12, 15, 26, 38};
  int ar2[] = {2, 13, 17, 30, 45};
  printf("%d", getMedian(ar1, ar2, 5)) ;
 
  getchar();
  return 0;
}
 
// Utility functions 
int max(int x, int y)
{
    return x > y? x : y;
}
 
int min(int x, int y)
{
    return x > y? y : x;
}
 
// Function to get median of a single array 
int median(int arr[], int n)
{
  if(n%2 == 0)
    return (arr[n/2] + arr[n/2-1])/2;
  else
    return arr[n/2];
}

References 

• http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
• For cases where 2 arrays are not equal - http://leetcode.com/2011/03/median-of-two-sorted-arrays.html 

Read More

Intersection of two sorted lists or 2 sorted arrays

For two sorted lists,
1, 2, 12, 15, 17, 18
1, 12, 14, 15, 16, 18, 20
intersection is bold numbers.

Solution 1 : Brute force
 An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. We have two better solutions.

Solution 2 : Take the benefit of sorting of array
It is noticeable that the two input arrays are sorted. Supposing a number number1 in array1 equals to a number number2 in array2, the numbers after number1 in array1 should be greater than the numbers before number2 in array2. Therefore, it is not necessary to compare the numbers after number1 in array1 with numbers before number2 in array2. It improves efficiency since many comparisons are eliminated.

List getIntersection(int[] a, int[] b){
    int apos = 0, bpos = 0
    List intersection
    while apos < a.length && bpos < b.length:
        if a[apos] == b[bpos]:
            intersection.add(a[apos])
            apos++, bpos++
        else:
            if a[apos] < b[bpos]:
                apos++
            else:
                bpos++
    return intersection 
}

Time Complexity is O(m + n).
Since it only requires to scan two arrays once, its time complexity is O(m+n).


Note: Using an ArrayList wastes space, instead use LinkedList.

Solution 3 - Using binary search in O(n log m) time

As we know, a binary search algorithm requires O(logm) time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n). Therefore, we can implement a new and better solution based on binary search in such a situation. 

For instance, the following same code is suitable when array1 is much longer than array2.

 /* === Supposing array1 is much longer than array2 === */
void getIntersectionUsingBinarySearch(int[] array1,
                     int[] array2,
                     int[] intersection)
{
    intersection.clear();
   
    int iter1 = array1[0];
    while(iter1 != array1[array1.size-1])
    {
        if(binary_search(0, array2.size, iter1))
            intersection.add(iter1);
    }
}

Time complexity : n log (m)

Thanks.

Read More

Remove duplicates from the sorted array

Problem 

 Remove duplicates from the sorted array

Example
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]

Method 1- using 3 pointers

//using 3 pointers
fixDuplicatesInSortedArray(Integer[] a):
    start = 0
    end = 0
    destination = 0

    while(start < a.length):
        while(end < a.length && a[end] == a[start]):
            end++
        end--
       
        //copy the distinct element
        a[destination] = a[start]
        destination++
       
        start = end + 1
        end = start

    //null out the rest
    while destination < a.length:
        a[destination] = null

    return

Method 2 - using 2 pointers

//using 2 pointers
fixDuplicatesInSortedArray(Integer[] a):
    prev = 0
    curr = 1
   
    while curr < a.length():
        while curr < a.length && a[curr] == c[prev]:
            curr++
        if curr == a.length() break
       
        prev++
        a[prev] = a[curr]
        curr++
   
    //null out the rest
    prev++
    while prev < a.length:
        a[prev] = null
   
    return

Time complexity - O(n) in both cases.

Thanks.

Read More