Finding median from unsorted array with duplicate elements without sorting it
If we never modify the elements of array, then it should be passed as a pointer to const: int const *array.

The frequency counts can be unsigned, and ought to be able to represent any size of input array (that suggests that count should be a size_t).

We absolutely must test that the return value of malloc() (and family) is not null before trying to dereference it (including passing it to memset()).  Additionally, it's not necessary or desirable to cast it to the target type:

size_t *freq = calloc(sizeof *freq, range + 1);
if (!freq) {
    fputs("Memory allocation failed!\n", stderr);
    exit(EXIT_FAILURE);
}


The algorithm has undefined behaviour if any element in the array is less than zero.  We need to find the minimum as well as maximum value, or perhaps change the input to be an unsigned type.

The counting is strange, with the nested loop.  Normally, we'd loop just once, incrementing the index for each element we look at - something like this:

for (int i = 0;  i &lt; count;  ++i) {
     ++freq[array[i]];
}


To avoid excessive temporary memory use for the count array, we could use a multi-pass approach.


Divide the range [min,max] into into (say) 256 buckets.
Count the inputs into those buckets.
Identify the median bucket.  Call that M.
Now divide the range represented by M into buckets.
Make another pass over the inputs, counting values within M into these new buckets (discarding values not in M).
Repeat until the bucket size is 1.