Discriminated union state machines in Typescript - Time & Space Complexity

Time Complexity: Discriminated union state machines

O(1)

Understanding Time Complexity

When using discriminated union state machines, it's important to know how the program's steps grow as the input changes.

We want to see how the number of operations changes when the machine processes different inputs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    type State =
      | { type: 'idle' }
      | { type: 'loading' }
      | { type: 'success'; data: string[] }
      | { type: 'error'; message: string };

    function processState(state: State): number {
      switch (state.type) {
        case 'idle':
          return 0;
        case 'loading':
          return 1;
        case 'success':
          return state.data.length;
        case 'error':
          return -1;
      }
    }
    

This code checks the state type and returns a number based on the state, counting items if successful.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing state.data.length when state is 'success'.
• How many times: Exactly once per function call, no loops or recursion inside.

How Execution Grows With Input

The function does a simple check and returns a value. The only input-dependent step is reading the length of an array.

Input Size (n)	Approx. Operations
10	1 (length check)
100	1 (length check)
1000	1 (length check)

Pattern observation: The number of operations stays the same no matter how big the data array is.

Final Time Complexity

Time Complexity: O(1)

This means the function runs in constant time, doing the same amount of work regardless of input size.

Common Mistake

[X] Wrong: "Because the data array can be large, the function takes longer to run."

[OK] Correct: The function only reads the length property, which is stored and accessed instantly, so size doesn't affect time.

Interview Connect

Understanding how state machines handle inputs efficiently shows you can write clear and fast code, a skill valued in many coding challenges.

Self-Check

"What if the function had to sum all numbers in the data array instead of just reading its length? How would the time complexity change?"

Practice

1.

What is the main purpose of using a discriminated union in TypeScript state machines?

easy

A. To enable dynamic addition of states at runtime without type errors.

B. To clearly define different states with a common type property for safe type checking.

C. To allow any property names in the state objects without restrictions.

D. To automatically generate UI components based on state names.

Solution

1. Step 1: Understand discriminated unions

   Discriminated unions use a common type property to distinguish between different object shapes.

2. Step 2: Identify the purpose in state machines

   This common property allows TypeScript to safely narrow the state type and catch errors.

3. Final Answer:

   To clearly define different states with a common type property for safe type checking. -> Option B

4. Quick Check:

   Discriminated union = safe state typing [OK]

Hint: Look for the common type property in states [OK]

Common Mistakes:

• Thinking discriminated unions allow any property names freely
• Assuming states can be added dynamically without type errors
• Confusing discriminated unions with UI generation

2.

Which of the following is the correct syntax to define a discriminated union type for a state machine with states loading and success?

type State = ?

easy

A. { status: 'loading' } | { status: 'success'; data: string }

B. { type: 'loading'; data: string } | { type: 'success' }

C. { type: 'loading' } | { type: 'success'; data: string }

D. { state: 'loading' } | { state: 'success'; data: string }

Solution

1. Step 1: Identify the discriminant property

   The discriminated union requires a common property named type to distinguish states.

2. Step 2: Match the correct state shapes

   Loading state has only type: 'loading', success state has type: 'success' and extra data.

3. Final Answer:

   { type: 'loading' } | { type: 'success'; data: string } -> Option C

4. Quick Check:

   Common type property with correct fields = B [OK]

Hint: Discriminant property must be named exactly 'type' [OK]

Common Mistakes:

• Using different property names like 'status' or 'state'
• Mixing properties between states incorrectly
• Adding data to loading state incorrectly

3.

Given the following TypeScript code, what will be the output?

type State =
  | { type: 'idle' }
  | { type: 'loading' }
  | { type: 'success'; data: string };

function getMessage(state: State): string {
  switch (state.type) {
    case 'idle':
      return 'Waiting...';
    case 'loading':
      return 'Loading...';
    case 'success':
      return `Data: ${state.data}`;
  }
}

console.log(getMessage({ type: 'success', data: 'Hello' }));

medium

A. Error: Property 'data' does not exist

B. Loading...

C. Waiting...

D. Data: Hello

Solution

1. Step 1: Analyze the input state

   The input state is { type: 'success', data: 'Hello' }, matching the 'success' case.

2. Step 2: Follow the switch case logic

   For 'success', the function returns `Data: ${state.data}`, which becomes 'Data: Hello'.

3. Final Answer:

   Data: Hello -> Option D

4. Quick Check:

   State 'success' returns data string [OK]

Hint: Match type in switch to get correct output [OK]

Common Mistakes:

• Confusing 'success' with 'loading' or 'idle'
• Expecting an error accessing 'data' without checking type
• Ignoring template string interpolation

4.

Identify the error in this discriminated union state machine code:

type State =
  | { type: 'start' }
  | { type: 'end'; result: number };

function process(state: State) {
  if (state.type === 'start') {
    console.log('Starting');
  } else {
    console.log('Result is ' + state.result);
  }
}

process({ type: 'start' });

medium

A. No error; code runs and prints 'Starting'.

B. Error: Accessing 'result' on 'start' state causes runtime error.

C. Error: Missing return type annotation on function.

D. Error: 'type' property should be optional.

Solution

1. Step 1: Check the state type conditions

   The function checks if state.type === 'start' and logs 'Starting'.

2. Step 2: Confirm safe access to 'result'

   In the else branch, state.result is accessed only if state.type !== 'start', so it must be 'end' with result.

3. Final Answer:

   No error; code runs and prints 'Starting'. -> Option A

4. Quick Check:

   Type narrowing prevents invalid property access [OK]

Hint: Check type guards before accessing state-specific properties [OK]

Common Mistakes:

• Assuming accessing 'result' on 'start' state causes error
• Expecting return type annotation is mandatory
• Thinking 'type' property should be optional

5.

You want to extend a discriminated union state machine to handle an error state with an optional message. Which is the best way to define this state to keep type safety and allow missing message?

type State =
  | { type: 'idle' }
  | { type: 'loading' }
  | { type: 'success'; data: string }
  | ???

hard

A. { type: 'error'; message?: string }

B. { type: 'error'; message: string | undefined }

C. { type: 'error'; message: string }

D. { type: 'error'; message: string | null }

Solution

1. Step 1: Understand optional properties in discriminated unions

   Using message?: string means the property can be missing or a string, which fits optional message.

2. Step 2: Compare other options

   { type: 'error'; message: string | undefined } requires the property but allows undefined explicitly, less idiomatic. { type: 'error'; message: string } requires message always. { type: 'error'; message: string | null } requires message but allows null, which is less type safe.

3. Final Answer:

   { type: 'error'; message?: string } -> Option A

4. Quick Check:

   Optional property syntax keeps type safety and flexibility [OK]

Hint: Use '?' to mark optional properties in state types [OK]

Common Mistakes:

• Making message required when it should be optional
• Using union with undefined instead of optional property
• Allowing null which can cause runtime issues