OutOfMemoryError when trying to find the largest kth element in a large array

Question

I am trying to solve a task that asks me to find the largest kth element in an unsorted array of length n (n might be as large as 5,000,000; elements in the array are distinct). Due to the task limits, I cannot use any sorting method, PriorityQueue, etc. Also, I used the user-defined FastReader class instead of the Scanner class to make it faster.

I have implemented the following code, which uses a temporary array of length k to store the first k elements and renew the smallest element through the process of reading.

import java.io.*;
import java.util.StringTokenizer;

public class lazyArray
{
    public static void main(String[] args)
    {
        FastReader in = new FastReader();
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) arr[i] = in.nextInt();
        int min_index = getMinIndex(arr);
        int next_num;
        for (int i = k; i < n; i++)
        {
            next_num = in.nextInt();
            if (arr[min_index] < next_num)
            {
                arr[min_index] = next_num;
                min_index = getMinIndex(arr);
            }
        }
        System.out.println(arr[min_index]);
    }
    static int getMinIndex(int[] arr)
    {
        int minValue = arr[0];
        int index = 0;
        for(int i = 1; i < arr.length; i++)
        {
            if(arr[i] < minValue) {
                minValue = arr[i];
                index = i;
            }
        }
        return index;
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
    }
}

However, the online judge platform returns an OutOfMemoryError.

I guess the error happens when n is near 5,000,000. I have tried to avoid initializing an array with length n which probably causes memory error. But I cannot find any other possible causes for the error.

Please help me. Thanks in advance.

Answer 1

I just tested it locally and the problem with your memory is: the BufferedReader. When the input is a single line, you try to read it into memory all at once - and this takes quite some heap. With just 137MB of heap, your code runs smoothly.

Also your FastReader has a quite high initialization time, but at 5 million input numbers this is not so much important anylonger.

Anyways I developed a FasterReader that is a bit faster (at least when it comes to read in 5 million values from a single line) and uses much less RAM:

static class FasterReader {
  private final InputStream inputStream;

  FasterReader(InputStream inputStream) {
    this.inputStream = inputStream;
  }

  int nextInt() throws IOException {
    int result = Integer.MIN_VALUE;
    int nextValue = inputStream.read();
    while ((nextValue >= 0) && (nextValue != '-') && ((nextValue < '0') || (nextValue > '9') )) {
      // skip non-digits
      nextValue = inputStream.read();
    }
    while ((nextValue >= '0') && (nextValue <= '9') || (nextValue == '-')) {
      if (nextValue == '-') {
        result = -result;
      } else {
        // get the numeric value of the ascii char by subtracting the ascii value for 0
        result = result * 10 + nextValue - '0';
      }
      nextValue = inputStream.read();
    }
    if (result < 0) {
      throw new EOFException();
    }
    return result;
  }
}

Its very very basic, doesn't really care about number formats. I would nearly never use it in production code!

• it just reads in digits and a - sign
• doesn't care about encoding
• numbers are separated by anything that is not a digit or -
• the - sign can appear anywhere: before, inside or after the number, just not separated from it
• multiple - signs will "flip" the sign of the number multiple times
• Integer.MIN_VALUE is used as a marker for an invalid read, so that value cannot be read

I tried to tweak the performance of my FasterReader by wrapping the InputStream with a BufferedInputStream but that didn't work well. Maybe it would help for reading a file, but for STDIN it made things worse.

You can test the memory limitation on your local machine with the commandline parameter -Xmx128M, to measure the time you could insert the following:

public static void main(String[] args) throws IOException {
  long ping = System.currentTimeMillis();

  // here comes your test code

  long pong = System.currentTimeMillis();
  System.out.println(pong - ping);
}  // end of void main(String[])

It prints the number of milliseconds that your code took to run.

Btw: the highest runtime will occur when k = n/2 as then the count of numbers in the array and the count of numbers that are compared with them are both maximized. With this k you probably will not reach the limit of 2000ms for n=5_000_000, no matter how fast your reader is! But of course this absolute timelimit depends on the actual machine the code is running on.