# Find K biggest numbers in the array

Method 2 (Use temporary array) K largest elements from arr[0..n-1]

1. Store the first k elements in a temporary array temp[0..k-1].
2. Find the smallest element in temp[], let the smallest element be min.
3. For each element x in arr[k] to arr[n-1] If x is greater than the min then remove min from temp[] and insert x.
4. Print final k elements of temp[]

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Please comment on the complexity and runtime speed. Can I improve my implementation in that sense? I was trying to get O((n-k)*k).

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{

//Design an algorithm to find K biggest numbers in the array.
[TestClass]
public class KBiggestNumbers
{
[TestMethod]
public void FindKBiggestNumbersTest()
{
int[] testArray = new[] { 7, 2, 4, 4, 3, 6, 1, 8, 9, 10, 11 };
int k = 5;
int[] result = FindKBiggestNumbers(testArray, k);
int[] expectedResult = new[] { 7,8,9,10,11 };
CollectionAssert.AreEqual(expectedResult, result);
}

private int[] FindKBiggestNumbers(int[] testArray, int k)
{
int[] result = new int[k];
for (int i = 0; i < testArray.Length; i++)
{
//if bigger than the smallest node
if (testArray[i] <= result)
{
continue;
}
else
{
//if bigger than all?
if (testArray[i] > result[k - 1])
{
for (int l = 0; l < k - 1; l++)
{
result[l] = result[l + 1];
}
result[k - 1] = testArray[i];
}
else
{

//Naive way
//for (int j = 0; j < k-1; j++)
//{
//    if (testArray[i] > result[j] && testArray[i] <= result[j + 1])
//    {
//        for (int l = 0; l < j; l++)
//        {
//            result[l] = result[l + 1];
//        }
//        result[j] = testArray[i];
//        break;
//    }
//}

//binary search
int indexLeft = 0;
int indexRight = k-1;

int currIndex = 0;
//10 20 30 40 50 - > place 33
while (indexRight- indexLeft >1)
{
currIndex = (indexRight + indexLeft)/2;
if (testArray[i] >= result[currIndex])
{
indexLeft = currIndex;
}
else
{
indexRight = currIndex;
}

}

for (int l = 0; l < currIndex; l++)
{
result[l] = result[l + 1];
}
result[currIndex] = testArray[i];
}
}
}
return result;
}
}
}

• Please if you give -1, explain why you do so, I wish to learn, not just to get whipped...thanks Jan 21, 2017 at 20:55
• You cannot really ask at SE Code Review for algorithm correctness. Be sure your algorithm works as intended in 1st place. Jan 21, 2017 at 20:55
• /OT @πάνταῥεῖ I'd refuse to answer any math question as an interview question, this doesn't say anything about how good you are at programming Jan 21, 2017 at 21:11
• Questions posted here should include the problem statement, not hide it behind a link. Please include all relevant parts of the problem statement. Links can rot.
– Mast
Jan 21, 2017 at 21:15
• Sure not how I read the instructions. Jan 22, 2017 at 1:54

Store the first k elements in a temporary array temp[0..k-1]

You are not doing that

Find the smallest element in temp[], let the smallest element be min

You are not doing that

For each element x in arr[k] to arr[n-1]...

You are starting on 0 because you skipped step 1

Nothing in there about a binary search
Not less operations the with the shifts

This

if (testArray[i] <= result)
{
continue;
}
else
{


Can be

if (testArray[i] > result)
{


Other than that looks good

Just following what I think are the instructions
It is $\mathcal{O}(n \times k)$ as the first k elements are not free

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
int[] result = new int[k];
int indexMin = 0;
result[indexMin] = testArray;
int min = result[indexMin];

for (int i = 1; i < testArray.Length; i++)
{
if(i < k)
{
result[i] = testArray[i];
if (result[i] < min)
{
min = result[i];
indexMin = i;
}
}
else if (testArray[i] > min)
{
min = testArray[i];
result[indexMin] = min;
for (int r = 0; r < k; r++)
{
if (result[r] < min)
{
min = result[r];
indexMin = r;
}
}
}
}
return result;
}


A bug

On the array of 10 elements

19 8 5 9 15 10 8 2 6 1


when computing 8 largest numbers, your version returns

2 5 8 8 9 10 15 19
^
wrong, should be 6


5 6 8 8 9 10 15 19.


Performance

My idea was to build a maximum heap of the entire input array (which runs, according to Introduction to Algorithms, in $\Theta(n)$), after which to peak $k$ maximum elments; this algorithm runs in $\Theta(n + k \log n)$. That is how:

using System;
using System.Linq;

namespace CRKBiggestNums
{
public class KBiggestNumbers
{
public static int[] FindKBiggestNumbers(int[] testArray, int k)
{
int[] result = new int[k];
for (int i = 0; i < testArray.Length; i++)
{
//if bigger than the smallest node
if (testArray[i] <= result)
{
continue;
}
else
{
//if bigger than all?
if (testArray[i] > result[k - 1])
{
for (int l = 0; l < k - 1; l++)
{
result[l] = result[l + 1];
}
result[k - 1] = testArray[i];
}
else
{
//binary search
int indexLeft = 0;
int indexRight = k - 1;

int currIndex = 0;
//10 20 30 40 50 - > place 33
while (indexRight - indexLeft > 1)
{
currIndex = (indexRight + indexLeft) / 2;
if (testArray[i] >= result[currIndex])
{
indexLeft = currIndex;
}
else
{
indexRight = currIndex;
}

}

for (int l = 0; l < currIndex; l++)
{
result[l] = result[l + 1];
}
result[currIndex] = testArray[i];
}
}
}

return result;
}

public static int[] FindKBiggestNumbers2(int[] array, int k)
{
BuildMaxHeap(array);
int[] result = new int[k];
int heapSize = array.Length;

for (int i = 0; i < k - 1; ++i)
{
result[i] = array;
array = array[--heapSize];
MaxHeapify(array, 0, heapSize);
}

result[result.Length - 1] = array;
return result;
}

private static void BuildMaxHeap(int[] array)
{
for (int i = array.Length / 2; i >= 0; --i)
{
MaxHeapify(array, i, array.Length);
}
}

private static void MaxHeapify(int[] array, int index, int heapSize)
{
int leftChildIndex = GetLeftIndex(index);
int rightChildIndex = leftChildIndex + 1;
int maxChildIndex = index;
int target = array[index];

while (true)
{
if (leftChildIndex < heapSize)
{
if (array[leftChildIndex] > target)
{
maxChildIndex = leftChildIndex;
}
}

if (maxChildIndex == index)
{
if (rightChildIndex < heapSize)
{
if (array[rightChildIndex] > target)
{
maxChildIndex = rightChildIndex;
}
}
}
else
{
if (rightChildIndex < heapSize)
{
if (array[rightChildIndex] > array[maxChildIndex])
{
maxChildIndex = rightChildIndex;
}
}
}

if (maxChildIndex == index)
{
array[maxChildIndex] = target;
return;
}

array[index] = array[maxChildIndex];
index = maxChildIndex;
leftChildIndex = GetLeftIndex(index);
rightChildIndex = leftChildIndex + 1;
}
}

private static int GetLeftIndex(int index)
{
return (index << 1) + 1;
}

private static long GetMilliseconds()
{
return DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
}

public static void Main(string[] args)
{
Random random = new Random();
int[] array1 = new int[1000 * 1000];
int[] array2 = new int[array1.Length];

for (int i = 0; i != array1.Length; ++i)
{
int element = random.Next(20);
array1[i] = element;
array2[i] = element;
}

int k = 10 * 1000;
var start = GetMilliseconds();
int[] result1 = FindKBiggestNumbers(array1, k);
var end = GetMilliseconds();

Console.WriteLine("OP method in {0} milliseconds.", end - start);

start = GetMilliseconds();
int[] result2 = FindKBiggestNumbers2(array2, k);
end = GetMilliseconds();

Console.WriteLine("coderodde method in {0} milliseconds.", end - start);

Array.Sort(result1);
Array.Sort(result2);

Console.WriteLine("The algorithms agree: {0}.", result1.SequenceEqual(result2));
}
}
}


Finally, the performance figures for $n = 1000000, k = 10000$ speak for themselves:

OP method in 1692 milliseconds.
coderodde method in 69 milliseconds.


Hope that helps.

• Hey thanks. Great answer.I'm trying to solve this as I am practicing for job interviews. Your solution is better but think, i will be afraid to write it under the pressure of an interview. I would certainly describe it. Jan 22, 2017 at 11:00

There is a bug in the above code because of which FindKBiggestNumbers and FindKBiggestNumbers2 give different results. Actually bug is there in FindKBiggestNumbers function. Here is the modified code for FindKBiggestNumbers

public static int[] FindKBiggestNumbers(int[] testArray, int k)
{
int[] result = new int[k];
for (int i = 0; i < testArray.Length; i++)
{
//if bigger than the smallest node
if (testArray[i] <= result)
{
continue;
}
else
{
//if bigger than all?
if (testArray[i] > result[k - 1])
{
for (int l = 0; l < k - 1; l++)
{
result[l] = result[l + 1];
}
result[k - 1] = testArray[i];
}
else
{
//binary search
int indexLeft = 0;
int indexRight = k - 1;

int currIndex = (indexRight + indexLeft) / 2; ;
//10 20 30 40 50 - > place 33
while (indexRight - indexLeft > 1)
{

if (testArray[i] >= result[currIndex])
{
indexLeft = currIndex;
}
else
{
indexRight = currIndex;
}
currIndex = (indexRight + indexLeft) / 2;
}

for (int l = 0; l < currIndex; l++)
{
result[l] = result[l + 1];
}
result[currIndex] = testArray[i];
}
}
}

return result;
}