Improving performance hacker rank Median

Question

I'm trying to compete on HackerRank and my answer got accepted, but the times are not so good. I have a friend who sent the answer in C# too but somehow made it a lot faster. I'm wondering what can I do to improve it.

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {

   static void Main(String[] args) {
      int N;
      StringBuilder st= new StringBuilder();

      N = Convert.ToInt32(Console.ReadLine());
      int[] x = new int[N];
       List<double> a= new List<double>();
      string[] s = new string[N];

      for(int i=0; i<N ;i++){

         string tmp = Console.ReadLine(); 
         string[] split = tmp.Split(new Char[] {' ', '\t', '\n'});

         s[i] = split[0].Trim();
         x[i] = Convert.ToInt32(split[1].Trim());
          bool r=true;

          if(s[i]=="r"){
              int index= a.BinarySearch(x[i]);
              if(index>=0){
                  a.RemoveAt(a.LastIndexOf(x[i]));    
              }
              else{
              r=false;
              }

          }else{
              var index = a.BinarySearch(x[i]);
                if (index < 0) index = ~index;
                  a.Insert(index,x[i]);
          }
          if(!r || a.Count==0){
              st.AppendLine("Wrong!");

          }
          else{
          st.AppendLine(calcularModa(a).ToString());
          }
      }      
       Console.WriteLine(st.ToString());

   }
   static double calcularModa(List<double> a){

   int i= a.Count/2;
       if(a.Count % 2 !=0){
           return a[i];
       }else{
           return ((a[i - 1] + a[i]))/2;
       }

    }
}

Answer 1

Besides of the pointed by Jesse, I'd like to comment on a couple of things that might improve your code. First, since all that you are parsing is a string, you don't need to call Convert.ToInt32(str), just int.Parse(str). This is what's really going on, you're just taking a few more extra method calls. But where I see you're losing most of your time is in the following:

int index= a.BinarySearch(x[i]);
if(index>=0){
    a.RemoveAt(a.LastIndexOf(x[i]));
    //...
}

Notice that you are looking for the index with Binary Search O(log n) and then you are again looking for the index, but not only once more, but this time in O(n). Instead, you should:

int index= a.BinarySearch(x[i]);
if(index>=0){
    a.RemoveAt(index));
//...
}

Answer 2

There are a lot of stylistic changes I'd normally suggest, but I'm going to forgo that to mention three very simple optimizations:

• remove new Char[] { ' ', '\t', '\n' } from within the loop. No need to recreate this object every time as it's an invariant.
• you know the maximum size of the a list, so create it with that capacity in mind to prevent resizing as it's being accessed: List<double> a= new List<double>(N);
• Repeated code in both the if and else branches pulled out (no performance optimization, but basic tenet of DRY (Don't Repeat Yourself)): int index= a.BinarySearch(x[i]);

Resulting code looks like this:

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {

   static void Main(String[] args) {
      int N;
      StringBuilder st= new StringBuilder();

      N = Convert.ToInt32(Console.ReadLine());
      int[] x = new int[N];
       List<double> a= new List<double>(N);
      string[] s = new string[N];

      Char[] splitChars = new Char[] { ' ', '\t', '\n' };

      for(int i=0; i<N ;i++){

         string tmp = Console.ReadLine(); 
         string[] split = tmp.Split(splitChars);

         s[i] = split[0].Trim();
         x[i] = Convert.ToInt32(split[1].Trim());
          bool r=true;

          int index= a.BinarySearch(x[i]);
          if(s[i]=="r"){
              if(index>=0){
                  a.RemoveAt(a.LastIndexOf(x[i]));    
              }
              else{
              r=false;
              }

          }else{
                if (index < 0) index = ~index;
                  a.Insert(index,x[i]);
          }
          if(!r || a.Count==0){
              st.AppendLine("Wrong!");

          }
          else{
          st.AppendLine(calcularModa(a).ToString());
          }
      }      
       Console.WriteLine(st.ToString());

   }
   static double calcularModa(List<double> a){

   int i= a.Count/2;
       if(a.Count % 2 !=0){
           return a[i];
       }else{
           return ((a[i - 1] + a[i]))/2;
       }

    }
}

Answer 3

     s[i] = split[0].Trim();
     x[i] = Convert.ToInt32(split[1].Trim());

There's no point in storing these values in the array. You use them right away, just store them in locals.

The problem for speed is here:

              a.RemoveAt(a.LastIndexOf(x[i]));    

and here:

              a.Insert(index,x[i]);

But of those will have to shift over elements in memory. It will be O(n) where n is the number of elements in the list. So that's rather expensive. Basically, you can't use a list do this. What you need to think about is what datastructure gives you:

1. Fast insertion
2. Fast deletion by value
3. Determination of the middle

The list gives you 3, but not 1 and 2.

Answer 4

Maybe you can use a HashSet instead of a List since HashSet has a O(1) time complexity for lookups; this way you won't need a binary search O(log2N).

See for example this stackoverflow answer

Hope this is useful.