Space

Open

From Fieldwork

Scales

588. Design In-Memory File System

leetcodeharddesigntriehash-tablestringsorting

Open pinned source

v1

Various little things going on here:

The "Unified Traversal" (Get vs. Create):

We can write a single helper function with a create boolean flag (or insert_if_missing mode) instead of writing separate findNode and addNode functions.

The "Sanitized Split" Idiom

Never trust string.split('/') blindly. It produces empty strings for leading/trailing delimiters or duplicates (//).

Time Complexity:

ls, mkdir, addContent, readContent: O(L) where L is the path length.

ls (directory): O(L + K log K) where K is the number of files in that directory (due to sorting).

readContent: O(L + C) where C is the total character length of the file content.

Space Complexity: O(N) where N is the total number of unique path components + content characters stored in the system.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_file = False
        # Use list for O(1) appends, join only on read
        self.content = []

class FileSystem:

    def __init__(self):
        self.root = TrieNode()

    def _traverse(self, path: str, create: bool = False):
        """
        Unified helper for navigation. 
        Returns the node if found/created, else None.
        """
        node = self.root
        # Split by '/' and ignore empty strings (handles "//" or trailing "/")
        parts = [p for p in path.split('/') if p]

        for part in parts:
            if part not in node.children:
                if not create:
                    return None
                node.children[part] = TrieNode()
            node = node.children[part]
        return node

    def ls(self, path: str) -> List[str]:
        node = self._traverse(path)
        
        if not node:
            return []
        
        if node.is_file:
            # We guaranteed root can't be a file, so split works safely
            return [path.split('/')[-1]]

        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self._traverse(path, create=True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        # Guard clause: Prevent corrupting the root directory
        if filePath == "/":
            return 
            
        node = self._traverse(filePath, create=True)
        node.is_file = True
        node.content.append(content)

    def readContentFromFile(self, filePath: str) -> str:
        node = self._traverse(filePath)
        
        if not node or not node.is_file:
            return ""
            
        return "".join(node.content)

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeNov 29, 2025