LeetCode 4006: imperative vs functional solution

Link to LeetCode 4006. Count Valid Prefixes problem.

I this post I compare how Python, Java, and Erlang solve the same LeetCode 4006 problem using imperative and functional programming.
Python and Java use loops and mutable variables, while Erlang takes a different approach with pattern matching and tail recursion. The code looks quite different, but all three solutions achieve the same O(n) time and O(1) space complexity.

All three solutions use the same algorithm: tracking the difference between the number of '1's and '0's in each prefix. If abs(Diff) <= 1, the prefix can be rearranged into an alternating string, so we increment the result.

Java

class Solution {
  public int countValidPrefixes(String s) {
    int diff = 0;
    int result = 0;

    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '1') diff++;
      else diff--;

      if (Math.abs(diff) <= 1) result++;
    }

    return result;
  }
}

Python

class Solution:
  def countValidPrefixes(self, s: str) -> int:
    diff = 0
    result = 0

    for char in s:
      if char == '1':
        diff += 1
      else:
        diff -= 1

      if abs(diff) <= 1:
        result += 1

    return result

Erlang

-spec count_valid_prefixes(S :: unicode:unicode_binary()) -> integer().
count_valid_prefixes(S) -> count(S, 0, 0).

% Return the total number of valid prefixes.
count(<<>>, _Diff, Result) -> Result;

% Process '1' and increase the difference.
count(<<$1, Rest/binary>>, Diff, Result) ->
  NewDiff = Diff + 1,
  NewResult = Result + valid(NewDiff),
  count(Rest, NewDiff, NewResult);

% Process '0' and decrease the difference.
count(<<$0, Rest/binary>>, Diff, Result) ->
  NewDiff = Diff - 1,
  NewResult = Result + valid(NewDiff),
  count(Rest, NewDiff, NewResult).

% Check whether the prefix can be alternating.
valid(Diff) when abs(Diff) =< 1 -> 1;
valid(_) -> 0.

Key differences

Python and Java - imperative approach

Both languages use a for loop and update the values of diff and result during each iteration. For example, in Java:

diff++;
result++;

The variables are mutable, meaning their values can change throughout the execution of the program.

Erlang - functional approach

In Erlang, variables are immutable, meaning their values cannot be changed after assignment. Instead, new variables are introduced to hold updated values:

NewDiff = Diff + 1,
NewResult = Result + valid(NewDiff),
count(Rest, NewDiff, NewResult).

The count/3 function recursively calls itself with the updated values. Erlang also uses Binary Pattern Matching to process the input string:

count(<<$1, Rest/binary>>, Diff, Result) ->

This pattern matches a binary beginning with the character '1' and binds the remaining binary data to Rest. Unlike Python and Java, Erlang does not require an explicit loop or index to process each character.

Why does Erlang use Tail Recursion?

Very interesting question: Why does Erlang use Tail Recursion?

Let's consider the following code:

count(Rest, NewDiff, NewResult).

This is the last operation performed by the function. No additional computation is required after the recursive call returns. This makes the function tail-recursive.
Erlang supports Tail Call Optimization (TCO), allowing the runtime to reuse the current stack frame instead of creating a new one for every recursive call.
As a result:

• Python uses a loop without recursion.
• Java uses a loop without recursion.
• Erlang uses tail recursion with constant stack space.

Without tail recursion, a recursive implementation could require O(n) stack space because each recursive call might need to remain on the call stack.

Complexity analysis

Time complexity: O(n)
Each character is processed exactly once.

• Python iterates through the string using a for loop.
• Java accesses each character using charAt(i).
• Erlang processes each character using binary pattern matching and tail recursion.

All three implementations perform constant-time operations for each character, resulting in O(n) time complexity.

Space complexity: O(1)
Each solution uses a constant amount of additional memory.

• Python maintains two variables: diff and result.
• Java maintains the same two variables along with a loop index.
• Erlang passes the current difference and result through tail-recursive function calls.

Erlang's binary pattern matching creates sub-binaries that reference the original binary data rather than copying the remaining characters.
Therefore, all three solutions have O(1) auxiliary space complexity.

Conclusion

Let's sum it all up.

All three solutions use the Prefix Sum pattern and Counting technique and achieve the same O(n) time complexity and O(1) auxiliary space complexity.
The main difference lies in their programming paradigms. Python and Java use imperative programming with loops and mutable variables, while Erlang follows a functional approach based on immutable variables, pattern matching, and tail recursion.
Erlang's implementation demonstrates how recursion can replace traditional loops without increasing stack usage, making it an efficient approach for processing binary strings.