Java Find Median in Stream

Question

I'm trying to find the median in a input stream in Java. After each user input, there should be an output updating the new median. Example: After reading 1st element of stream 5 median is 5 After reading 2nd element of stream 5, 15 median is 10 After reading 3rd element of stream 5, 15, 1 median is 5 After reading 4th element of stream 5, 15, 1, 3 median is 4, so on

Here's my code so far but it does not work for inputs past 4.

public static void main(String[] args){
    Scanner s = new Scanner(System.in); 
    System.out.print("Enter a integer for number of streams: ");
    int n=s.nextInt();
    int[] x=new int[n];
    for(int i=0;i<n;i++) {
        System.out.println("Enter a integer: ");
        x[i]=s.nextInt();
        if(i==0) { //first input number
            System.out.println(x[i]+" goes to stream --> Median is: "+x[i]);
        }
        else if(i==1) {   //when i =1, it is technically second input 
            System.out.println(x[i]+" goes to stream --> Median is: "+(float)(x[i]+x[0])/2);
        }
        else if(i>=2 && i%2==0) {  //3rd input so # of inputs is odd        
            Arrays.sort(x);
            System.out.println(x[i]+" goes to stream --> Median is: "+x[n/2]);
        }
        else if(i>=3 && i%2!=0) {  //when # of input is more than 3 and even
            Arrays.sort(x);
            int j=n/2;
            float med=(x[j]+x[j-1])/2;
            System.out.println(x[i]+" goes to stream --> Median is: "+med);
        }

I have not finished yet but my question is: does this approach work? Basically I'm just using iterator i to see if the # of inputs is odd or even. If odd, sort the input array, and find the middle #. If even, find the middle 2 and add and divide. I have seen other solutions using heaps etc, but I am only strictly using arrays.

Answer 1

Your code looks ok, obviously it can be improved since its a naive approach.

The mistake I see in your solution is that you are using n (length of complete array) instead of i (current length) in 3rd and 4th else-if block

Also, use an ArrayList instead of Array, as array is initialized to its default value (here 0) because of which you are getting wrong output.

Try using below correction:

public static void main(String[] args){
    Scanner s = new Scanner(System.in); 
    System.out.print("Enter a integer for number of streams: ");
    int n=s.nextInt();
    List<Integer> x = new ArrayList<>();
    for(int i=0;i<n;i++) {
        System.out.println("Enter a integer: ");
        x.add(s.nextInt());
        if(i==0) { //first input number
            System.out.println(x.get(i)+" goes to stream --> Median is: "+x[i]);
        }
        else if(i==1) {   //when i =1, it is technically second input 
            System.out.println(x.get(i)+" goes to stream --> Median is: "+(float)(x.get(i)+x.get(0))/2);
        }
        else if(i>=2 && i%2==0) {  //3rd input so # of inputs is odd        
            Collections.sort(x);
            System.out.println(x.get(i)+" goes to stream --> Median is: "+x.get(i/2));
        }
        else if(i>=3 && i%2!=0) {  //when # of input is more than 3 and even
            Collections.sort(x);
            int j=i/2;
            float med=(x.get(j)+x.get(j-1))/2;
            System.out.println(x.get(i)+" goes to stream --> Median is: "+med);
        }
 }
}

Now, lets talk about the time complexity.

As I said above its a naive approach. Next step can be to improve time complexity, which can be done by using data structure to store elements which sorts by itself on each new addition instead of we sorting each time. I mean if we use some kind of SortedList.

But, in java there is no class such as SortedList. But there is a class which is based on similar concept i.e. PriorityQueue. I would recommend you to read about it and try reducing the complexity yourself.