Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly  . I began with $"max"$; but in cannot update quickly; Means that if we consider $max$ then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)*O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How can i do this job? thanks for you help.

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with "max"; but it cannot update quickly; Means that if we consider max then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How do I solve this problem?

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly . I began with $"max"$; but in cannot update quickly; Means that if we consider $max$ then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)*O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently

How can i do this job? thanks for you help.

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly . I began with $"max"$; but in cannot update quickly; Means that if we consider $max$ then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)*O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How can i do this job? thanks for you help.