How to avoid StackOverflowError caused by the number of recursion calls in Java?
July 14, 2014  Posted by forumadmin under TechQns 
Comments off

I want to solve this problem: https://www.hackerrank.com/challenges/findmedian ,i.e. find the median element in unsorted array. To do this I perform quickselect algorithm. My program works correctly on my computer. However when I submitted in the system it gave me StackOverflowError. I think this is because of the depth of the recursion calls. I guess I make too many racursion calls than Java allowes (the error is caused by a test case with 10 001 numbers). Can someone suggest me how to avoid this? This is my code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class FindMedian {
static int res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line1 = br.readLine();
int N = Integer.parseInt(line1);
String[] line2 = br.readLine().split(" ");
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(line2[i]);
}
selectKth(arr, 0, N1);
System.out.println(res);
}
public static void selectKth(int[] arr, int start, int end) { //it is written seclect Kth element but actually it selects the median element
if(start >= end){
res = arr[start];
return;
}
int pivot = arr[start];
int n = arr.length1;
int i = start + 1;
int j = end;
while(i <= j){
while(arr[i] <= pivot){
i++;
}
while(pivot < arr[j]){
j;
}
if(i < j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j;
}
}
int tmp = arr[j];
arr[j] = pivot; //j is the index of the last element which is bigger or equal to pivot
arr[start] = tmp;
if(n/2 <= j){
selectKth(arr, start, j);
}
else{
selectKth(arr, i, end);
}
}
}
Asked By – user3371223  Read Answers 