Ahmed Rakan

Posted on Sep 16

Introduction to State-Driven Programming

#algorithms #datastructures

State-driven programming is a style where the current state of data drives the computation, rather than relying heavily on conditional statements (if/else) scattered throughout the code. This approach is particularly useful when tracking sequences, patterns, or logical transitions in a dataset.

In this post, we’ll use a practical example: counting connected components in a linked list based on a subset of its values.

Problem

You are given:

head of a linked list containing unique integers.
An array nums, a subset of the linked list values.

Return the number of connected components in nums, where two values are connected if they appear consecutively in the linked list.

Examples

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2

Explanation: [0, 1] is one component, [3] is another.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2

Explanation: [0, 1] and [3, 4] are the two connected components.

Initial Solution (Imperative)

The standard approach is to:

Convert nums to a set for O(1) lookups.
Traverse the linked list.
Count a component whenever:

The current node is in nums, and
The next node is not in nums (or is None).

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        while head:
            if head.val in s and not (head.next and head.next.val in s):
                ans +=1
            head = head.next
        return ans

Trick: A component ends when the current node is in nums but the next node is not.

Moving Towards State-Driven Programming

Instead of relying on explicit if statements, we can drive computation using a state table:

Map each value in nums to a logical state (1 if present, 0 otherwise).
For each node, compute if it ends a component using only its state and the next node's state.
Accumulate the result without explicit branching.

Step 1: Create a Logical Hashtable

from collections import defaultdict

table = defaultdict(lambda: 0)
for n in nums:
    table[n] = 1

Here, table[val] is 1 if val is in nums, 0 otherwise.

Step 2: Traverse and Accumulate Using State

ans = 0
while head:
    state = table[head.val]
    ans += state * (not (head.next and table[head.next.val]))
    head = head.next

state = 1 → current node is part of a component.
not (head.next and table[head.next.val]) → next node is not part of a component, i.e., component ends here.
Multiply these logical values to count component closures without an if statement.

Full State-Driven Solution

from collections import defaultdict

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        table = defaultdict(lambda: 0)
        for n in nums:
            table[n] = 1

        ans = 0
        while head:
            state = table[head.val]
            ans += state * (not (head.next and table[head.next.val]))
            head = head.next

        return ans

Diagram: State Propagation

Linked List: 0 -> 1 -> 2 -> 3
Nums: {0, 1, 3}

State Table: {0:1, 1:1, 2:0, 3:1}

Step by Step:
Node 0: state=1, next_state=1 → not counted
Node 1: state=1, next_state=0 → counts as 1 component
Node 2: state=0 → skipped
Node 3: state=1, next_state=None → counts as 1 component

Total Components = 2

Why State-Driven Programming Helps

Reduces branching → more predictable code execution.
Encodes logical conditions in a data structure → easier to reason about.
Scales to more complex state transitions without additional if statements.

Think of it as treating each node as a finite state machine, where the table drives the transitions and outputs.

Conclusion

State-driven programming is particularly useful when:

You have logical conditions depending on neighbors or sequence.
You want to eliminate scattered if statements.
You want to model computation as state transitions.

This linked list connected components problem is a simple yet powerful illustration of the concept.

DEV Community