I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like it is the correct answer or maybe there is more nuance. Given that nothing was said about extra space, is this the simplest(and correct) way to do it ?
1
- $\begingroup$ This doesn't really take up much extra space anyway, just a few numbers to track size, min, max, and mean $\endgroup$HackerBoss– HackerBoss2020-12-15 19:25:39 +00:00Commented Dec 15, 2020 at 19:25
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
3 If you are just given an array and asked to find these statistic there there is no way to do that (unless the size of the array is upper bounded by a constant). An easy way to convince yourself that this is true is noticing that in $O(1)$ time you can only access $O(1)$ entries of the array. Then the maximum, minimum, or median could be in the unread entries (notice that you can safely assume that any $O(1)$-time algorithm always accesses the returned entry).
You talk about "insert operations" which makes me thing that you were actually asked to design a data structure that supports some set of operations, among which there are insertions and reporting the above statistics. If this is the case then the answer depends on how what the other operations are and how much time do you want to spend on those.
If the only updates to the array are insertion then it suffices to keep track of the number of elements, their sum, and the maximum and minimum element after each insertion. This will require $O(1)$ time per insertion and $O(1)$ time to report the statistics.
- $\begingroup$ I forgot to mention that the array is empty at the start. $\endgroup$Harsha Limaye– Harsha Limaye2020-12-12 01:25:18 +00:00Commented Dec 12, 2020 at 1:25
- $\begingroup$ Yeah I did something similar like keeping track of count(number of elements), min, max and total(sum). $\endgroup$Harsha Limaye– Harsha Limaye2020-12-12 01:27:56 +00:00Commented Dec 12, 2020 at 1:27
- $\begingroup$ Yes I only need to insert new elements and report on these statistics instantly. $\endgroup$Harsha Limaye– Harsha Limaye2020-12-12 01:29:51 +00:00Commented Dec 12, 2020 at 1:29