LeetCode 1166 - Design File System

This problem asks us to design a simplified file system that supports two operations: 1. Creating a new path with an associated integer value. 2. Retrieving the value stored at a path. A path behaves similarly to a directory structure in a real operating system.

leetcodemediumhash-tablestringdesigntrie

LeetCode Problem 1166

Difficulty: 🟡 Medium
Topics: Hash Table, String, Design, Trie

Solution

Problem Understanding

This problem asks us to design a simplified file system that supports two operations:

  1. Creating a new path with an associated integer value.
  2. Retrieving the value stored at a path.

A path behaves similarly to a directory structure in a real operating system. Every path is composed of components separated by /.

For example:

  • /leet
  • /leet/code

are valid paths.

The key rule is that a path can only be created if its parent already exists.

For example:

  • Creating /leet is valid because it is a top-level path.
  • Creating /leet/code is valid only if /leet already exists.
  • Creating /c/d fails if /c does not exist.

The createPath(path, value) operation should:

  • Return true if the path is successfully created.

  • Return false if:

  • the path already exists, or

  • the parent path does not exist.

The get(path) operation should:

  • Return the value associated with the path if it exists.
  • Return -1 if the path does not exist.

The constraints are relatively small:

  • Path length is at most 100.
  • At most 10^4 operations are performed.

These limits mean we do not need extremely advanced optimizations, but we still want efficient lookups and insertions. Since the operations are fundamentally based on exact path matching, hash maps are a natural fit.

Several edge cases are important:

  • Attempting to create an already existing path.
  • Attempting to create a nested path before its parent exists.
  • Handling top-level paths correctly.
  • Returning -1 for nonexistent paths.
  • Ensuring / itself is not treated as a valid path.

The problem guarantees that all provided paths are syntactically valid, so we do not need to perform path-format validation.

Approaches

Brute Force Approach

A brute-force solution could store all created paths in a list of (path, value) pairs. Every time we call createPath, we would:

  1. Scan the entire list to check whether the path already exists.
  2. Compute the parent path.
  3. Scan the list again to determine whether the parent exists.

Similarly, get(path) would scan the list linearly to locate the matching path.

This approach is correct because every operation explicitly checks the required conditions. However, it is inefficient because every lookup requires linear scanning.

If there are n stored paths, each operation becomes O(n).

Since there can be up to 10^4 operations, repeated linear scans are unnecessary and inefficient.

Optimal Approach

The key observation is that every operation requires fast exact-path lookup.

This makes a hash map ideal.

We can store:

path -> value

inside a dictionary or hash map.

Then:

  • Checking whether a path exists becomes O(1) average time.
  • Retrieving a value becomes O(1) average time.
  • Verifying whether the parent exists also becomes O(1) average time.

The only additional work is extracting the parent path from the string.

For example:

/leet/code

has parent:

/leet

We can find this using string operations.

This gives us an efficient and clean solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per operation O(n) Uses linear scans for every lookup
Optimal O(1) average per operation O(n) Uses a hash map for direct path lookup

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a hash map called paths.

This map stores every valid path and its associated value.

Example:

{
    "/leet": 1,
    "/leet/code": 2
}
  1. When createPath(path, value) is called, first check whether the path already exists.

If it does, return false because duplicate creation is not allowed. 3. Compute the parent path.

For example:

path = "/leet/code"
parent = "/leet"

We can find the parent by locating the last /. 4. If the parent is not empty, verify that it exists in the hash map.

This ensures hierarchical correctness.

Examples:

  • /leet/code requires /leet
  • /a/b/c requires /a/b
  1. If the parent does not exist, return false.
  2. Otherwise, insert the new path into the hash map with its value.
  3. Return true to indicate successful creation.
  4. For get(path), simply return:
  • the stored value if the path exists
  • -1 otherwise

Why it works

The algorithm maintains the invariant that every stored path has a valid parent chain.

A path is only inserted if:

  • it does not already exist, and
  • its parent already exists.

Because every insertion preserves this property, the file system structure always remains valid. The hash map guarantees efficient retrieval and existence checking.

Python Solution

class FileSystem:

    def __init__(self):
        self.paths = {}

    def createPath(self, path: str, value: int) -> bool:
        # Path already exists
        if path in self.paths:
            return False

        # Find parent path
        last_slash_index = path.rfind("/")
        parent = path[:last_slash_index]

        # Parent must exist unless this is a top-level path
        if parent and parent not in self.paths:
            return False

        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        return self.paths.get(path, -1)

# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path, value)
# param_2 = obj.get(path)

The implementation uses a dictionary called paths to store every created path and its value.

Inside createPath, the first check prevents duplicate creation. If the path already exists, we immediately return False.

Next, the code computes the parent path using rfind("/"), which finds the final slash in the string. Everything before that slash becomes the parent.

For example:

"/leet/code"

becomes:

parent = "/leet"

If the parent string is nonempty, we verify that it already exists in the dictionary. If it does not, creation fails.

Otherwise, the path is inserted into the dictionary and the method returns True.

The get method uses Python's dictionary .get() method to return either the stored value or -1 if the path is absent.

Go Solution

package main

import "strings"

type FileSystem struct {
	paths map[string]int
}

func Constructor() FileSystem {
	return FileSystem{
		paths: make(map[string]int),
	}
}

func (this *FileSystem) CreatePath(path string, value int) bool {
	// Path already exists
	if _, exists := this.paths[path]; exists {
		return false
	}

	// Find parent path
	lastSlashIndex := strings.LastIndex(path, "/")
	parent := path[:lastSlashIndex]

	// Parent must exist unless top-level path
	if parent != "" {
		if _, exists := this.paths[parent]; !exists {
			return false
		}
	}

	this.paths[path] = value
	return true
}

func (this *FileSystem) Get(path string) int {
	if value, exists := this.paths[path]; exists {
		return value
	}

	return -1
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor()
 * param_1 := obj.CreatePath(path, value)
 * param_2 := obj.Get(path)
 */

The Go implementation follows the same logic as the Python version but uses a map[string]int for storage.

Go requires explicit existence checks when accessing maps. Therefore, the code uses:

value, exists := map[key]

to distinguish between missing entries and stored zero values.

The strings.LastIndex function is used to find the final slash when computing the parent path.

Worked Examples

Example 1

Input:

["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]

Step-by-Step Trace

Operation Internal Hash Map Result
Initialize {} null
createPath("/a", 1) {"\/a": 1} true
get("/a") unchanged 1

Explanation:

  • /a is a top-level path.
  • Its parent is an empty string.
  • Therefore creation succeeds.

Example 2

Input:

["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]

Step-by-Step Trace

Operation Internal Hash Map Result
Initialize {} null
createPath("/leet", 1) {"\/leet": 1} true
createPath("/leet/code", 2) {"\/leet": 1, "\/leet/code": 2} true
get("/leet/code") unchanged 2
createPath("/c/d", 1) unchanged false
get("/c") unchanged -1

Explanation of failure:

  • /c/d requires parent /c
  • /c does not exist
  • Therefore creation fails

Complexity Analysis

Measure Complexity Explanation
Time O(1) average per operation Hash map lookups and insertions are constant time on average
Space O(n) Stores all created paths

The dominant operations are dictionary or hash map lookups. Since hash maps provide average-case constant-time access, both createPath and get are highly efficient.

The space complexity grows linearly with the number of stored paths.

Test Cases

# Example 1
fs = FileSystem()
assert fs.createPath("/a", 1) == True   # Create top-level path
assert fs.get("/a") == 1                # Retrieve existing path

# Example 2
fs = FileSystem()
assert fs.createPath("/leet", 1) == True
assert fs.createPath("/leet/code", 2) == True
assert fs.get("/leet/code") == 2
assert fs.createPath("/c/d", 1) == False  # Missing parent
assert fs.get("/c") == -1                 # Nonexistent path

# Duplicate path creation
fs = FileSystem()
assert fs.createPath("/x", 5) == True
assert fs.createPath("/x", 10) == False   # Duplicate path

# Nested creation without parent
fs = FileSystem()
assert fs.createPath("/a/b", 1) == False  # Parent missing

# Multiple nested levels
fs = FileSystem()
assert fs.createPath("/a", 1) == True
assert fs.createPath("/a/b", 2) == True
assert fs.createPath("/a/b/c", 3) == True
assert fs.get("/a/b/c") == 3

# Get nonexistent path
fs = FileSystem()
assert fs.get("/missing") == -1

# Create sibling paths
fs = FileSystem()
assert fs.createPath("/root", 1) == True
assert fs.createPath("/root/left", 2) == True
assert fs.createPath("/root/right", 3) == True
assert fs.get("/root/left") == 2
assert fs.get("/root/right") == 3

# Long chain creation
fs = FileSystem()
assert fs.createPath("/a", 1) == True
assert fs.createPath("/a/b", 2) == True
assert fs.createPath("/a/b/c", 3) == True
assert fs.createPath("/a/b/c/d", 4) == True
assert fs.get("/a/b/c/d") == 4
Test Why
Create /a Validates top-level creation
Get existing path Ensures retrieval works
Create nested path Verifies parent dependency
Create /c/d without /c Tests missing-parent rejection
Duplicate creation Ensures duplicates are blocked
Deep nesting Confirms recursive hierarchy support
Get missing path Ensures -1 is returned correctly
Sibling paths Verifies independent child creation
Long chain Tests repeated nested insertions

Edge Cases

Creating a Path That Already Exists

A common bug is accidentally overwriting an existing path's value.

For example:

createPath("/a", 1)
createPath("/a", 2)

The second call must fail.

The implementation handles this immediately with:

if path in self.paths:
    return False

This preserves the rule that paths cannot be recreated.

Creating a Nested Path Without Its Parent

Another important edge case occurs when trying to create a deeply nested path before its parent exists.

Example:

createPath("/a/b", 1)

when /a does not exist.

A naive implementation might incorrectly allow this insertion.

The solution explicitly extracts the parent path and checks for its existence before insertion.

Retrieving a Nonexistent Path

The get method must return -1 for missing paths.

For example:

get("/missing")

should not raise an exception or return an arbitrary default value.

The implementation safely handles this with dictionary lookup defaults:

return self.paths.get(path, -1)

This guarantees correct behavior for all nonexistent paths.

Handling Top-Level Paths Correctly

Top-level paths such as:

/a

have no parent.

A buggy implementation might incorrectly require the empty string "" to exist as a parent.

The solution avoids this issue by checking:

if parent and parent not in self.paths:

If parent is empty, the existence check is skipped, allowing valid top-level path creation.