LeetCode 195 - Tenth Line

This problem asks us to print exactly the 10th line from a text file named file.txt. The file contains multiple lines of plain text, and each line is separated by a newline character. The input is not provided as function arguments like many algorithm problems.

leetcodeeasyshell

LeetCode Problem 195

Difficulty: 🟢 Easy
Topics: Shell

Solution

Problem Understanding

This problem asks us to print exactly the 10th line from a text file named file.txt. The file contains multiple lines of plain text, and each line is separated by a newline character.

The input is not provided as function arguments like many algorithm problems. Instead, the solution must work directly with a file in a shell scripting environment. The expected output is the content of the 10th line, printed exactly as it appears in the file.

The problem statement also raises an important question: what happens if the file contains fewer than 10 lines? In that case, the correct behavior is to print nothing. Most shell utilities naturally behave this way when the requested line does not exist.

Even though this is labeled as an Easy problem, it is designed to test familiarity with standard Unix text processing tools. The problem hints that there are at least three different approaches, which means understanding multiple shell utilities is valuable.

The key constraints are small from a computational perspective, but the challenge lies in using shell commands effectively and concisely. Since the file can theoretically be large, an efficient solution should avoid unnecessary storage or processing.

Several edge cases are important:

  • The file may contain fewer than 10 lines.
  • The file may contain empty lines.
  • The 10th line may contain spaces or special characters.
  • The file may be extremely large, making full-file storage inefficient.

A correct implementation must handle all of these cases cleanly.

Approaches

Brute Force Approach

The brute force idea is to read the entire file into memory, store every line, and then print the element at index 9, since line numbering starts from 1 while array indexing starts from 0.

For example, a script could iterate through the file line by line, append each line into an array, and finally print the 10th entry if it exists.

This approach works because every line is preserved, so accessing the 10th line afterward is straightforward. However, it is inefficient for large files because it stores the entire contents unnecessarily when only one line is needed.

The time complexity is linear because every line must still be read. The space complexity is also linear because all lines are stored.

Optimal Approach

The better solution is to process the file as a stream and stop once the 10th line is reached. Unix tools such as sed, awk, and head combined with tail are ideal for this.

The key insight is that we do not need to remember all previous lines. We only care about one specific line number. Since shell utilities are designed for stream processing, they can read the file sequentially and print the desired line immediately.

For example:

  • sed -n '10p' file.txt prints only the 10th line.
  • awk 'NR==10' file.txt prints the line when the record number reaches 10.
  • head -n 10 file.txt | tail -n 1 first extracts the first 10 lines, then prints the last among them.

These solutions are memory efficient because they process the file incrementally instead of storing everything.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Reads and stores the entire file
Optimal O(n) O(1) Streams through the file and prints only the 10th line

Algorithm Walkthrough

Using sed

  1. Open the file and begin reading it line by line.
  2. Suppress the default automatic printing behavior using the -n flag.
  3. Continue scanning until line 10 is reached.
  4. Use the p command to print the 10th line.
  5. If the file ends before line 10, nothing is printed.

Using awk

  1. Read the file sequentially, one line at a time.
  2. Maintain the current line number using the built-in variable NR.
  3. Check whether NR == 10.
  4. When the condition becomes true, print the current line.
  5. If line 10 never exists, no output is produced.

Using head and tail

  1. Use head -n 10 to extract only the first 10 lines.
  2. Pipe the result into tail -n 1.
  3. tail prints the last line from those 10 lines.
  4. If fewer than 10 lines exist, the final output becomes the last available line, which is why this approach is slightly less precise unless additional checks are added.

Python Solution

Although the original problem expects a shell script, below is a Python equivalent that demonstrates the same logic.

from typing import Optional

class Solution:
    def tenthLine(self, file_path: str) -> Optional[str]:
        with open(file_path, "r") as file:
            for line_number, line in enumerate(file, start=1):
                if line_number == 10:
                    return line.rstrip("\n")

        return None

This implementation opens the file and processes it line by line using iteration. The enumerate function tracks the current line number starting from 1.

As soon as the loop reaches line 10, the method returns that line after removing the trailing newline character. This avoids storing unnecessary data and mirrors the efficient streaming behavior of shell utilities.

If the file ends before reaching line 10, the function returns None, indicating that the requested line does not exist.

Go Solution

package main

import (
	"bufio"
	"os"
)

func tenthLine(filePath string) string {
	file, err := os.Open(filePath)
	if err != nil {
		return ""
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)
	lineNumber := 0

	for scanner.Scan() {
		lineNumber++

		if lineNumber == 10 {
			return scanner.Text()
		}
	}

	return ""
}

The Go solution uses a bufio.Scanner to read the file incrementally. This is memory efficient because it processes one line at a time instead of loading the entire file.

Unlike Python, Go requires explicit error handling when opening files. If the file cannot be opened, the function returns an empty string.

The scanner automatically removes newline characters, so no extra trimming is necessary.

Worked Examples

Example 1

Suppose file.txt contains:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

Step by Step Using awk

Command:

awk 'NR==10' file.txt
Current Line NR Value Condition NR==10 Output
Line 1 1 False None
Line 2 2 False None
Line 3 3 False None
Line 4 4 False None
Line 5 5 False None
Line 6 6 False None
Line 7 7 False None
Line 8 8 False None
Line 9 9 False None
Line 10 10 True Line 10

Final output:

Line 10

Example 2, File With Fewer Than 10 Lines

Input:

A
B
C

Processing stops after line 3 because the file ends.

Current Line NR Value Condition NR==10
A 1 False
B 2 False
C 3 False

Since line 10 never exists, nothing is printed.

Complexity Analysis

Measure Complexity Explanation
Time O(n) The file may need to be scanned until the 10th line or end of file
Space O(1) Only a constant amount of extra memory is used

The algorithm is linear because reading a text file requires scanning lines sequentially. In the worst case, the file contains fewer than 10 lines, so the entire file must be processed.

The space complexity remains constant because only the current line and line counter are stored at any moment.

Edge Cases

File Contains Fewer Than 10 Lines

This is the most important edge case. A naive implementation might attempt to access a nonexistent line and produce an error.

The provided implementations handle this safely. sed and awk naturally print nothing when line 10 does not exist. The Python solution returns None, while the Go version returns an empty string.

Empty Lines in the File

The file may contain blank lines, and they still count as lines.

For example:

Line 1

Line 3

The empty second line still increments the line counter. The implementations correctly count every newline-separated record, regardless of content.

Very Large Files

A solution that stores the entire file in memory could become inefficient for large inputs.

The optimal solutions avoid this issue by processing the file incrementally. Only one line is kept in memory at a time, making the approach scalable even for extremely large files.

Special Characters or Spaces

Lines may contain spaces, tabs, or special characters.

Commands like awk and sed, along with the Python and Go implementations, preserve the line content exactly as written, ensuring correct output without unintended formatting changes.