Find K biggest numbers in the array

Question

I was trying to implement method number 2, from this article.

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[0])
 {
 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;
 }
 }
}

• Gilad: Please if you give -1, explain why you do so, I wish to learn, not just to get whipped...thanks
• πάντα ῥεῖ: You cannot really ask at SE Code Review for algorithm correctness. Be sure your algorithm works as intended in 1st place.
• t3chb0t: /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
• Mast: 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.
• paparazzo: Sure not how I read the instructions.

Answer 1

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[0])
{
 continue;
}
else
{

Can be

if (testArray[i] > result[0])
{

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[0];
 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;
}

Answer 2

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

when the correct answer is

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[0])
 {
 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[0];
 array[0] = array[--heapSize];
 MaxHeapify(array, 0, heapSize);
 }
 result[result.Length - 1] = array[0];
 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.

• Gilad: 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.

Answer 3

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[0])
 {
 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;
}