Transpose File - Solution & Explanation
Problem Statement
Given a text file file.txt, transpose its content.
You may assume that each row has the same number of columns, and each field is separated by the ' ' character.
Example:
If file.txt has the following content:
name age alice 21 ryan 30
Output the following:
name alice ryan age 21 30
Approach Overview
Problem Overview: The file file.txt contains rows of space-separated words. The task is to transpose the file so that the first column becomes the first row, the second column becomes the second row, and so on. Essentially, treat the input as a matrix of words and output its transpose.
Approach 1: Using Arrays for Transpose (Time: O(m*n), Space: O(m*n))
This approach reads the entire file and stores words using a 2D structure. Split each line into tokens and place them in an array using row and column indices. After loading the data, iterate column by column and print elements across all rows. The key idea is treating the input as a matrix where arr[row][col] holds each word. This method is straightforward and mirrors classic matrix transpose logic often used in arrays problems.
Approach 2: Using Stream Processing (Time: O(m*n), Space: O(n))
Instead of storing the entire matrix, process the file line by line and build column strings dynamically. Tools like awk allow referencing fields ($1, $2, etc.) while reading each line. Maintain an array where index i accumulates the i-th column. Each time a new row is read, append the field to its column string. After processing all lines, print the accumulated column strings. This streaming pattern avoids storing every cell individually and is idiomatic for shell scripting.
Recommended for interviews: The array-based approach demonstrates the core idea clearly: load the grid and print columns as rows. It mirrors standard matrix transpose logic, so it’s easy to reason about. The stream-processing approach is more practical for shell environments and large files because it processes input incrementally. Showing both demonstrates that you understand both algorithmic thinking and real-world shell scripting.
Approach 1: Using Arrays for Transpose
This approach involves reading each line from the file, splitting it into words, and storing these words in a 2D array where we can easily access and rearrange the data to perform the transpose operation.
The C solution uses an array to store words found in each line of the input file. It then reads each line and splits it using the strtok() function. The number of columns and rows is tracked and, once all lines have been processed, it prints out the transposed array by swapping access indices in the loop.
Complexity
Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line.
Space Complexity: O(m * n) for storing words in memory.
Approach 2: Using Stream Processing
This approach makes use of common stream processing libraries and methods available in different programming languages to handle the file reading and transposing simultaneously, thereby optimizing certain operations such as memory management and I/O handling.
This C implementation handles memory more efficiently by dynamically allocating memory for strings when tokens are identified. A buffer retains the mapping of positions to facilitate transposing. The memory is explicitly managed, freeing strings after printing.
Complexity
Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line.
Space Complexity: O(m * n) for dynamically allocated memory.
Approach 3: awk
Code
Shell
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Arrays for Transpose | Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line. |
| Using Stream Processing | Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line. |
| awk | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array-Based Transpose | O(m*n) | O(m*n) | When you want a straightforward matrix-style implementation and memory is not a constraint |
| Stream Processing (awk/field accumulation) | O(m*n) | O(n) | When processing large files or writing idiomatic shell scripts that avoid storing the full matrix |
Video Solution
194. Transpose File, Bash, Leetcode Questions • H William Polenz • 284 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Transpose File easy or hard?
Transpose File Python/Java solution
How to solve Transpose File in O(n)?
What is the best approach for Transpose File?
Is Transpose File asked at Google/Amazon/Meta?
What data structure is used in Transpose File?
What is the time complexity of Transpose File?
Ready to solve this problem?
Practice Transpose File with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor