Katkat
Back

Validate a Balanced INDENT and DEDENT Token Stream

FigmaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Determine if a sequence of structural tokens maintains valid scoping rules—never closing an un-opened level and closing all levels by the end. Tests single-pass balance checking, edge-case handling for empty streams, and O(1) space optimization.

Problem Statement

In block-structured languages and document-tree serializations, hierarchical nesting is frequently represented by a flat stream of tokens containing INDENT and DEDENT markers alongside standard statements.

Write a function is_valid_token_stream(tokens: list[str]) -> bool that determines whether a given token stream has valid indentation semantics.

A token stream is valid if and only if:

  1. At any point in the stream, the number of DEDENT tokens does not exceed the number of preceding INDENT tokens (indentation depth cannot drop below 0).
  2. At the end of the stream, all open indentation blocks have been closed (final indentation depth must be exactly 0).
  3. Non-scoping tokens do not affect indentation depth.

Function Signature

def is_valid_token_stream(tokens: list[str]) -> bool:
    pass

Input & Output Format

  • Input: tokens, a list of strings representing the sequence of tokens. Possible values are "INDENT", "DEDENT", or any other arbitrary string representing a statement (e.g., "STATEMENT", "PASS").
  • Output: A boolean (True if the stream is balanced and valid, False otherwise).

Constraints

  • 0 <= len(tokens) <= 2 * 10^5
  • tokens[i] consists of uppercase/lowercase alphanumeric strings.

Examples

Example 1

Input: tokens = ["STATEMENT", "INDENT", "STATEMENT", "DEDENT"]
Output: True
Explanation: The level starts at 0, increases to 1 at index 1, and decreases back to 0 at index 3.

Example 2

Input: tokens = ["INDENT", "INDENT", "DEDENT"]
Output: False
Explanation: The stream ends with an unclosed indentation block (depth = 1).

Example 3

Input: tokens = ["DEDENT", "INDENT"]
Output: False
Explanation: At index 0, a DEDENT occurs when depth is 0, causing the depth to become negative (-1). Even though the total count of INDENT and DEDENT is equal, the ordering is invalid.

Edge Cases

  • An empty list [] should return True (depth starts and ends at 0).
  • Streams with only STATEMENT tokens and no indentation markers should return True.
  • Streams that end with an extra DEDENT must be rejected immediately without waiting for end-of-stream.

Hints

Hint 1

Consider how this problem mirrors the classic balanced parentheses problem, but where all brackets are of the same type.

Hint 2

Because all opening tokens and closing tokens are identical, you do not need a stack data structure; a single integer tracking the current nesting depth is sufficient.

Hint 3

Ensure that you reject the stream as soon as the depth drops below zero, and verify that the depth returns to exactly zero at the end.

Follow-up questions

  • How would your implementation change if each INDENT specified a column offset (e.g., INDENT(4)) and a DEDENT could close multiple levels back to an arbitrary outer column?
  • How would you modify the function to return the 0-indexed position and a descriptive error message explaining why validation failed?
  • If the token stream is several gigabytes long and partitioned across multiple workers, how could you validate it in parallel using a map-reduce strategy?