Skip to main content

71. Simplify Path

medium

Canonicalize a Unix-style file path with '.' and '..' segments. A practical, real-world stack problem that's a favorite of platform and infra interviewers.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this absolute path into its simplified canonical path. In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//' or '///') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names. The simplified canonical path should follow these rules: it must start with a single slash '/'; directories within it should be separated by exactly one slash '/'; it should not end with a slash '/', unless it is the root directory; it should exclude any single or double periods used to denote the current or parent directory. Return the simplified canonical path.

Constraints

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.

Examples

Example 1

Input
path = "/home/"
Output
"/home"

Explanation: Note that there is no trailing slash after the last directory name.

Example 2

Input
path = "/home//foo/"
Output
"/home/foo"

Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 3

Input
path = "/a/./b/../../c/"
Output
"/c"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Split the path on '/'. Now you have a list of segments to process left to right.

Hint 2

Three segment cases to skip: empty string (from '//'), '.', and '..' on an empty stack.

Hint 3

'..' pops one directory off the stack. Any other non-empty segment is a directory name — push it.

Hint 4

Join the final stack with '/' and prepend one '/'. Empty stack means root: return '/'.

Solution approach

Reveal approach

Split path on '/' and iterate. Maintain a stack of directory names. For each segment: skip if it's empty or '.'; if it's '..', pop the stack (only if non-empty); otherwise push it. After processing, join the stack with '/' separators and prepend '/'. If the stack is empty, return '/'. O(n) time and O(n) space. Two subtleties: don't treat '...' as a parent directory (only exact '..' is special), and '..' on an empty stack is a no-op (you can't go above root).

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Microsoft
  • Bloomberg

More Stacks practice problems

See all Stacks problems →