I'm looking for a more efficient algorithm for the following problem:
The input of the algorithm is a text file and two non-negative integer numbers - the number of headers and the number of tails.
Execution of the algorithm should provide two output files. Output file 1 should have all the header lines followed by the tail lines. Output file 2 should have all the lines between the headers and the tails - if there is any.
Input file content:
1 2 3
Number of headers: 1 Number of tails: 1
Then after the execution the expected content of the outptut file 1 is
while the content of output file 2 is
One solution reads the input file once, and after finding the header lines (and writing those to output file 1), in a fixed size (size of tails) of queue data structure maintains the possible tail lines. When reading a new line it puts it into the queue. If the queue would be full then it removes the first line from the queue and writes it to output file 2. If it reached the EOF, it writes the content of the queue into the output file 1.
This implementation has an efficient time complexity, but the space complexity is based on the number of tails. If the number of tails is large it can end up reading a large file into the memory.
To avoid this I thought about another algorithm which reads the input file twice. First it counts the number of lines. And in the second iteration based on the number of lines, it can figure out where the tail lines are starting. With this we can avoid reading a large file which perhaps would not fit into the memory.
Is there any algorithm which could be used to iterate through the input file only once, but at the same time avoid filling up the memory with a large file?
(I'm using Java for the implementation with BufferedReader and simple text file)