# Improving performance hacker rank Median

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;
}

}
}

• What's this supposed to do? I can't make any sense of it. You should use descriptive variable names. Commented May 2, 2013 at 18:51
• it calculates the median for this challenge hackerrank.com/challenges/median Commented May 2, 2013 at 19:01
• which is your goal time? Commented May 2, 2013 at 23:25

## 4 Answers

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));
//...
}

• Hey thanks, that looks like could help, i will test it later. Commented May 2, 2013 at 20:45
• Also, make sure your array is sorted. BinarySearch() isn't efficient on unsorted arrays. Commented May 2, 2013 at 21:40
• Yes its sorted, and it improved a lot my time, at hardest test cases it went from 3.5 seconds to 0.6 Commented May 3, 2013 at 14:41
• I'm confused by this. Isn't RemoveAt O(N)? Commented May 3, 2013 at 15:19
• @EnriqueMedina, I get that. I'm just surprised it made as much of a difference as Luis is reporting. Commented May 3, 2013 at 16:45

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;
}

}
}

• It improved a little but still somehow a lot slower that the other implementation, i will try to get the other code to see why it could be faster, thanks for reviewing :) Commented May 2, 2013 at 18:48
     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.

• Not storing the values in the array did not provide any improvement, and what data structure would you recommend? Commented May 3, 2013 at 14:53
• @LuisTellez, the point of the exercise is for you to think about and figure it out yourself. I've solved this problem, all I'm willing to give you is hints about it. Commented May 3, 2013 at 14:59
• I solved it before coming here, i just wanted tips to improve times, but its already accepted and with Enrique Medina improvement it did improve a lot my times. Commented May 3, 2013 at 15:30

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.

• The HashSet contains no duplicate elements, and whose elements are in no particular order, so it does not work for this problem. Commented May 3, 2013 at 14:45