Skip to content

Instantly share code, notes, and snippets.

@rajeshp
Created January 16, 2013 19:52
Show Gist options
  • Save rajeshp/4550249 to your computer and use it in GitHub Desktop.
Save rajeshp/4550249 to your computer and use it in GitHub Desktop.
Code to find the Kth Smallest element from 2 Independently Sorted Arrays
//take 2 pointers p1 and p2 which points to arrays A and B respectively and compare a[p1] to b[p2], if smaller increment p1 else increment p2
static int getKthSmallest(int[] a, int[] b, int k)
{
if(a==null || b==null || k> (a.length+b.length))
throw new IllegalArgumentException();
int p1=0,p2=0,i=0;
while(true)
{
while(a[p1]<b[p2])
{
p1++;
i++;
if(i==k)
return a[p1-1];
}
while(a[p1]>b[p2])
{
p2++;
i++;
if(i==k)
return b[p2-1];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment