Finding median of sub arrays taking too much time

Question

I'm trying to solve a programming challenge where I have to find the median of given subarrays of an array. I have used std::vector's n_th element for this. But the evaluator fails some test cases as "time limit exceeded".

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

/*
In
6
2 4 5 3 1 6
3
1 6
2 4
3 3

Out
3
4
5

*/

int get_ceil(int length)
{
    if (length % 2 == 0)
    {
        return length/2;
    }
    else
    {
        return (length+1)/2;
    }

}

int get_median_of_subarray(std::vector<int> & full_array, int lo, int hi)
{

    std::vector<int>::const_iterator begin = full_array.begin() + lo;
    std::vector<int>::const_iterator end = full_array.begin() + hi + 1;
    std::vector<int> sub_array(begin, end);

    int median_pos = get_ceil(hi - lo + 1);
    std::nth_element (sub_array.begin(), sub_array.begin() + median_pos -1, sub_array.end());
    return sub_array[median_pos - 1];
}



int main()
{
    ios_base::sync_with_stdio(false);

    int array_size = 0;
    std::vector<int> input_array;

    cin >> array_size;

    for(int i = 0; i < array_size; i++)
    {
        int x;
        cin >> x;
        input_array.push_back(x);
    }

    int query_size = 0;
    cin >> query_size;

    int lo = 0;
    int hi = 0;

    for(int i = 0; i < query_size; i++)
    {
        cin >> lo >> hi;
        std::cout << get_median_of_subarray(input_array, --lo, --hi) << std::endl;
    }

    return 0;
}

Answer 1

• One performance problem is the overhead of allocating and resizing a vector. Since you read the size up front, why not simply reserve() enough space?

    cin >> array_size;
    input_array.reserve(array_size);

• If you sorted the sequence, computing the median would become dead simple and very fast (O(1)). This may be a better approach. However, you can't sort the sequence once and then run different queries, because the subsequence applies to the unsorted sequence. I haven't thought this through completely, but when removing two elements from the sequence, there are several possible ways it can affect the median:

  • If both elements are larger, the median becomes the previous value in the sorted sequence.
  • If both elements are smaller, the median becomes the next value in the sorted sequence.
  • If one element element is smaller and one is larger, the median remains the same.
  • If one element is equal to the median, it moves opposite to the other value.

  The problem here is that the "new" median can easily be one that's should be removed already, so this simple approach is not yet enough, but it might serve as a start to a better algorithm. In any case, what you need to keep in mind is the complexity and the variables that affect it. For your task, you have the number of values n and the number of queries m. Your algorithm is almost optimal for the case that m = 1. In order to improve the overall performance, you can actually optimize the performance for the case of m > 1, even at the expense of the the m = 1 case! Often, you can improve the performance by first sorting the data and then switching to a different (faster) algorithm for the actual work.

Answer 2

Not related to performance, but never ever do this:

#include <bits/stdc++.h>

using namespace std;

For reference see these Q&A at Stack Overflow:

• Why should I not #include <bits/stdc++.h>?
• Why is “using namespace std;” considered bad practice?