DEV Community: rezzcode ∞

Leetcode Sunday #5

rezzcode ∞ — Tue, 10 Mar 2026 19:51:17 +0000

LeetCode 1980: Find Unique Binary String

Difficulty: Medium

Despite this problem being labelled as a Medium problem, I found this challenge more approachable than expected once I understood the key idea.

The Problem

We are given an array nums containing unique binary strings, all of the same length n. The goal is to return any binary string of length n that does not exist in the array.

At first glance, the problem seems to require generating and checking many possible binary strings until we find one that isn’t in the list.

My First Thought

Since the problem explicitly says the binary strings are unique, my first instinct was to use a map:

The key would be the binary string.
The value would be a boolean (true).

This way, I could quickly check whether a generated string already existed in the array.

check := make(map[string]bool)
for _, s := range nums {
    check[s] = true
}

The idea of this structure was to help prevent returning a string that already appears in nums.

The Hard Part: Generating a Unique Binary String

The bigger challenge was now how to construct a binary string that is guaranteed not to exist in the input.

Since binary strings only contain two digits: 0 and 1's, one idea was to flip bits:

0 → 1

1 → 0

then would flip the bits recursively until I get the unique binary string, but somewhere along the lines, I realised that this was not the way to go since I was not getting to what I wanted to achieve. This led me to try a different approach.

A Better Insight

The breakthrough came when I started comparing characters across different strings.

Consider this example:

Initially, I would compare the values of all four binary strings at a given index to come up with the final flipped binary. Instead of that, I was now flipping the combinations diagonally to come up with the final binary.

Look at the index-th string
Flip the index-th bit

example:

Index	Original Bit	Flipped Bit
nums[0][0]	1	0
nums[1][1]	1	0
nums[2][2]	0	1
nums[3][3]	0	1

This approach gave me mostly all the time a unique value.

My Implementation

Here is the Go implementation I wrote:

func findDifferentBinaryString(nums []string) string {
    ret := []rune{}
    check := make(map[string]bool)

    for i, s := range nums {
        check[s] = true

        if s[i] == '0' {
            ret = append(ret, '1')
        } else {
            ret = append(ret, '0')
        }
    }

    if !check[string(ret)] {
        return string(ret)
    }

    return ""
}

Possible Optimisation

Since by diagonally flipping the values, the generated string is guaranteed to be unique, I could have simplified the code as:

func findDifferentBinaryString(nums []string) string {
    ret := make([]rune, 0, len(nums))

    for i, s := range nums {
        if s[i] == '0' {
            ret = append(ret, '1')
        } else {
            ret = append(ret, '0')
        }
    }

    return string(ret)
}

I decided to move forward with the first aproach so if at all I come up with a duplicate binary string, only an empty string would be returned, signifying that there was an error in binary generation.

Lastly

Sometimes the best solution isn't usually about generating more possibilities, but about constructing the right one directly.

Leetcode Sunday #4

rezzcode ∞ — Sun, 22 Feb 2026 21:12:34 +0000

How My “Worst” Complexity Solution Beat 100% Runtime — Binary Gap in Go

When I solved the Binary Gap problem, I expected the cleaner, theoretically optimal solution to dominate.

Instead, something unexpected happened. Guess which one ranked higher?

My O(n log n) solution beat 100% of submissions in runtime, while my O(n), O(1) solution used more memory.

That forced me to pause and rethink what I thought I understood about complexity.

Let’s break it down.

Problem Recap — What Is a Binary Gap?

A binary gap is the distance between two consecutive 1s in the binary representation of a number.

More precisely:

A binary gap is the number of consecutive 0s between two adjacent 1s, plus one (to include the closing 1).

Trailing zeros do not count, because a valid gap must be bounded by 1s on both sides.

Example

Given a binary list represented as:

Binary: 00010001001
Index:  01234567890

Valid gaps:

Between index 3 and 7 → 000 → gap = 3 + 1 = 4
Between index 7 and 10 → 00 → gap = 2 + 1 = 3

Largest gap = 4

First Approach — Store All Gaps and Sort (O(n log n))

Instead of tracking the maximum directly, I stored all computed gaps in a slice, sorted it, and returned the largest. At this point, I was only thinking about solving the problem... not making a great solution.

And yes, that introduced sorting.

Implementation

func binaryGap(n int) int {
    binR := []rune(strconv.FormatInt(int64(n), 2))
    count := 0
    gaps := []int{}
    gotOne := false

    for _, x := range binR {
        if x == '1' {
            if gotOne {
                gaps = append(gaps, count+1)
                count = 0
            }
            gotOne = true
        } else if x == '0' && gotOne {
            count++
        }
    }

    if len(gaps) == 0 {
        return 0
    }

    sort.Ints(gaps)
    return gaps[len(gaps)-1]
}

Complexity

Time: O(n log n)
Space: O(n)

As you know, this is theoretically worse, so I decided to refactor my code like...

Second Approach — Track the Maximum On the Fly (O(1) Space)

The idea:

Convert the number to binary
Count zeros between 1s
Track the maximum gap as we iterate
Ignore leading and trailing zeros

Implementation

func binaryGap(n int) int {
    bin := strconv.FormatInt(int64(n), 2)

    ret := 0
    count := -1

    for _, ch := range bin {
        if ch == '1' {
            if count+1 > ret {
                ret = count+1
            }
            count = 0
        } else if count != -1 {
            count++
        }
    }

    return ret
}

Complexity

Time: O(log n)
Space: O(1)

This should be the optimal solution.

Or so I thought, but this is why theoretical complexity and observed runtime diverge...

The Surprise

When I submitted both:

Approach	Runtime	Memory	Beets Runtime/Memory
O(1) Space	0 ms	~4.0 MB	100% / 40.63%
O(n log n)	0 ms	~3.85 MB	100% / 78.13%

And the second one beat 100% of submissions in runtime.

If you are shocked by this, don't fret, I also were.

Why the “Worse” Algorithm Won?

The Input Size Is Tiny

The key detail:

The binary length of an integer is at most 32 bits.

That means:

Maximum binary length ≈ 32
Maximum number of gaps ≈ 16

Sorting 10–15 integers is effectively constant time.

So:

O(32 log 32) ≈ constant

In bounded problems, asymptotic complexity barely matters.

Online Judge Timing Granularity

Platforms measure runtime in milliseconds.

If both implementations run in less than 1 ms:

They both show 0 ms.

“Beats 100%” often just means it landed in the fastest measurable bucket.

Not that it is fundamentally superior.

The Memory RSS Differences Are Not Just About Variables

The platform measures total memory footprint, including:

Go runtime overhead
String allocation behaviour
Slice capacity growth
Garbage collector behaviour

A difference between:

4.0 MB vs 3.89 MB

is allocator-level noise.

It doesn’t necessarily reflect algorithmic superiority.

The Real Lesson

This tiny problem taught me more about real-world performance than many “hard” ones, and not just about binary gaps:

Big-O complexity only dominates when the input size grows.

When the input is capped and tiny:

O(n)
O(n log n)
Even O(n²)

may behave identically in practice.

Always write for clarity first, then optimise only when needed. But understand why something is faster/slower.

The Last Optimal Refactor

After spending some time refactoring the code, I realised that I could eliminate string conversion and use bitwise operations, which led me to this solution:

func binaryGap(n int) int {
    ret, prev := 0, -1
    for i := 0; n > 0; n >>= 1 {
        if n&1 == 1 {
            if prev != -1 {
                ret = max(ret, i-prev)
            }
            prev = i
        }
        i++
    }
    return ret
}

With this solution, we now have:

No string allocation
No slice allocation
True O(1) extra space
Pure bitwise operations

I also learnt that, stracturing your code differently can byfar improve your code. For exmple:

While using for range in go, passing a string directly uses more memory than changing the string to runs.
You can write bitwise but if you write it correctly, it can enhance how:
- The Go compiler schedules registers/spills
- The micro-variations are generated in machine code
- And overally reduce the Noise factors that make your code perfomace fluctuate.

Final Takeaway

My “worse” algorithm didn’t magically become better.

It benefited from:

Bounded input size
Measurement granularity
Runtime implementation details

And that’s the real lesson:

Never interpret performance badges without understanding why performance looks the way it does.

Sometimes, the numbers lie — or at least, they don’t tell the full story.

Leetcode Sunday #3

rezzcode ∞ — Mon, 16 Feb 2026 12:35:41 +0000

LeetCode 67: Add Binary

Difficulty: Easy

Time Spent: ~1 hour

This Sunday’s LeetCode challenge was about adding two binary strings, for example:

a = "1000"
b = "1011"

At first glance, this looked straightforward.

The Confident First Attempt

I immediately reached for what felt natural:

import strconv
Convert both binary strings to integers
Perform normal integer addition
Convert the result back to binary
Return the final string using strconv.Itoa

In Go, that meant importing strconv, parsing the strings, doing integer arithmetic, and then converting everything back.

Parse binary → integer
Add integers
Convert sum → binary string

Clean. Simple. Done.

However, this approach fails for very large inputs.

The problem constraints allow strings of significant length. If you assume something like:

len(a) = 1e9 + 1

the value will overflow a 64-bit integer. In fact, during submission, I encountered cases where the result turned negative due to overflow.

That immediately made it clear, and I knew I had to rethink of my approach:

The problem was not about numeric conversion.

It’s about simulating binary addition manually.

And was testing whether I understood binary addition itself.

Rethinking the Problem

Binary arithmetic only uses two digits: 0 and 1.

Binary addition follows the exact same logic as base-10 addition — only the threshold changes.

Base 10 Example

9 + 9 = 18

Write 8
Carry 1

Binary Equivalent

1 + 1 = 10

Write 0
Carry 1

So the process is identical:

Add digits from right to left
Keep track of a carry
Append the current digit
Move to the next position

and instead of converting entire strings into integers, I needed to simulate the manual addition process — digit by digit, from right to left.

Designing the Logic

To simulate this properly, I needed:

A variable to store the carry (upV)
A result string (str)
Two pointers starting from the end of each string

We always process from right to left, because addition starts from the least significant digit.

At each step:

Add the current digits
Add the carry
Store sum % 2
Update carry as sum / 2

For example illustration:

If we have...

a = "111"
b = "101"

We start with:

a[len(a)-1]
b[len(b)-1]

If both digits are 1, then:

1 + 1 = 0 (write)
carry = 1

One important implementation detail:

If we use:

str += "0"

we would build the string in reverse order.

So instead, we prepend:

str = "0" + str

About String Concatenation

You might ask:

Why not use strings.Builder for better performance?

The issue is that strings.Builder efficiently appends to the end — not the beginning.

Since we are prepending digits, what i needed was:

str = newDigit + str

so strings.Builder is efficient for appending — but not for prepending.

And since we’re building the number from right to left, prepending felt like the most straightforward option at the time.

If you know a cleaner or more performant approach for efficiently building the string in reverse order, feel free to share in the comments.

Final Working Solution

Here is the simplified implementation:

import "strconv"

func addBinary(a string, b string) string {
    x, y := len(a)-1, len(b)-1
    upV := 0
    str := ""

    for x >= 0 || y >= 0 {
        sum := upV

        if x >= 0 {
            sum += int(a[x] - '0')
            x--
        }

        if y >= 0 {
            sum += int(b[y] - '0')
            y--
        }

        str = strconv.Itoa(sum%2) + str
        upV = sum / 2
    }

    if upV > 0 {
        str = strconv.Itoa(upV) + str
    }

    return str
}

Why This Worked

We iterate once.
We simulate real binary addition.
We never convert the full string into an integer.
Time complexity is O(n).
Space complexity is O(n).

Key Takeaway

Sometimes, the problem labeled easy is not usually hard.

The logic is simple, but only if you think about it the right way.

This question isn’t about conversion — it’s about understanding how addition fundamentally works.

Leetcode Sunday #2

rezzcode ∞ — Sun, 08 Feb 2026 19:42:57 +0000

LeetCode 110: Balanced Binary Tree

Difficulty: Easy

Time Spent: ~3 hours

This was one of those problems that reminded me why difficulty labels can be misleading. What initially looked like a straightforward tree check turned into a deep lesson on recursion, abstraction, and problem framing.

The problem statement was short and deceptively simple:

A binary tree is balanced if the heights of the left and right subtrees of every node differ by no more than 1.

Given a binary tree, determine if it is height-balanced, and that was it.

That single sentence hides the real challenge.

My Initial Misinterpretation

My first instinct was to think in terms of values rather than structure.

I initially reasoned along these lines:

Check the left and right nodes
Compare some “minimum” and “maximum”
If the difference is <= 1, return true; otherwise false
Done ✔️

But something felt off.

Despite passing some cases, I kept failing others. That was the signal that my mental model of the problem was wrong.

The Key Realization

The breakthrough came when I realized this:

Tree balance has nothing to do with node values.

It is purely about height.

Once that clicked, my first approach was completely invalidated.

Why This Is a Height Problem

For every node in the tree, you must ask:

What is the height of my left subtree?
What is the height of my right subtree?
Is the difference between them more than 1?

If any node violates this rule, the entire tree is unbalanced.

This immediately suggests a recursive solution, but designing the recursion correctly is where things get interesting.

The First Recursive Attempt (And Why It Failed)

I started with this idea:

func isBalanced(node *TreeNode) bool {
    if node == nil {
        return true
    }

    left := isBalanced(node.Left)
    right := isBalanced(node.Right)

    // ... now what?
}

I quickly hit a wall.

The Problem With Returning `bool`

At each node, I actually need two pieces of information:

Is my subtree balanced?
What is the height of my subtree?

A bool can only answer the first question.

Once you commit to returning bool, you lose access to height information higher up the recursion. This makes isBalanced a poor abstraction for this problem, at least one that I could use to create my solution.

Designing a Better Recursive Contract

Instead of returning only whether a subtree is balanced, I decided to return more information.

That led to a key insight:

A recursive function can encode multiple meanings into its return value.

The Sentinel-Value Trick (Almost Right)

I introduced a helper function:

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := height(node.Left)
    right := height(node.Right)

    if left == -1 || right == -1 {
        return -1
    }

    if (left-right) < 0 {
        return 0
    } else if (left-right) > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

The Idea

If the subtree is balanced, return its height
If the subtree is unbalanced, return -1
Since height can never be negative, -1 becomes a clear sentinel value
Once -1 appears, it propagates upward and short-circuits the recursion

This is a powerful pattern.

Unfortunately… my logic was still flawed.

The Bug: Direction vs Distance

I made a dangerous assumption:

“If left - right is negative, that’s fine.”

That assumption is wrong.

A negative value only tells you direction, not magnitude.

-1 → acceptable
-5 → absolutely not acceptable

By not accounting for absolute difference, I implicitly assumed the right subtree was always taller in a “safe” way.

This caused a failure on the test case:

[1, null, 2, null, 3]

Visualizing the Problem

What Should Happen

height(3) = 1
height(2) = 2
height(1) → detects imbalance → returns -1

What Actually Happened

height(3) = 1
height(2) = 2
height(1) sees left-right = -2 → returns 0

Returning 0 incorrectly marked the tree as balanced.

The Fix: Absolute Difference

The correct balance condition is:

-1 <= left - right <= 1

Which is much clearer and safer when expressed as:

abs(left - right) <= 1

Once I made that change, everything on the check was smiling green.

The Final Solution

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return height(root) != -1
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := height(node.Left)
    right := height(node.Right)

    if left == -1 || right == -1 {
        return -1
    }

    if int(math.Abs(float64(left-right))) > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

What This Problem Actually Taught Me

How to design better recursive contracts
Why sentinel values are powerful
Why correctness often beats premature optimisation
Why tree problems are more about information flow than traversal

Final Thoughts

This problem took me around three hours, not because it was hard to code, but because it forced me to rethink how recursion communicates information.

Tree recursion isn’t about memorising patterns.

It’s about understanding what each node needs to know and what it must pass upward.

If this problem confused you at first, that’s a good sign. That confusion is where real understanding begins.

Leetcode Sunday #1

rezzcode ∞ — Sun, 01 Feb 2026 22:53:11 +0000

Leetcode 3010: Divide an Array Into Subarrays With Minimum Cost I

Difficulty: Easy

Time Spent: ~1 hour 47 minutes

This problem looks simple at first glance, but it took me some time to fully understand what actually matters and what doesn’t.

This post documents my thinking process, my initial (overcomplicated) solution, and how I eventually arrived at a clean and optimal approach.

Problem Summary

You are given an integer array nums.

You must split it into 3 contiguous, non-empty subarrays
The cost of a subarray is the value of its first element
Return the minimum possible sum of the costs

First Observation: `nums[0]` Is Always Included

The first thing I noticed is that the first subarray always starts at index 0.

For example, given:

[1, 2, 3, 4, 5]

The first subarray can be:

[1]
[1, 2]
[1, 2, 3]

But the cost is always 1, because the cost only depends on the first element.

So I started treating:

nums[0]

as a constant.

What Actually Affects the Minimum Cost

Since addition is addition, and nums[0] is always included, the real problem becomes:

Which two values should start the second and third subarrays to minimize the total cost?

For example:

[1, 2, 33, 44, 55, 5, 77, 3]

Even though the array looks large and messy, the minimum cost is:

1 + 2 + 3

Why?

1 → first subarray (always)
2 → second subarray
3 → third subarray

The exact shape of the subarrays doesn’t matter —

what matters is where the subarrays start, not how long they are.

Early Implementation (Accepted but Fragile)

My first solution worked and was accepted, but it was not robust.

I tried to manually manage indices to avoid conflicts when finding minimum values.

func minimumCost(nums []int) int {
    numLen := len(nums)
    if numLen < 3 {
        return 0 // array too short
    }

    sum := 0
    currentSum := 0

    // Handle first 3 elements directly
    for x := 0; x < 3; x++ {
        sum += nums[x]
        currentSum += nums[x]
    }

    if numLen > 3 {
        currentSum = nums[0]
        firstCheck := nums[1]
        idx := 1
        lastCheck := nums[1]

        // Find first minimum
        for x := 1; x < numLen; x++ {
            if firstCheck > nums[x] {
                firstCheck = nums[x]
                idx = x
            }
        }

        // Find second minimum (avoid index conflict)
        for x := 1; x < numLen; x++ {
            if x == idx {
                continue
            }
            if nums[x] < lastCheck {
                lastCheck = nums[x]
            }
        }

        currentSum += firstCheck + lastCheck
    }

    if currentSum < sum {
        sum = currentSum
    }

    return sum
}

Why I Needed the Index

Without tracking the index of the first minimum, both firstCheck and lastCheck could end up referencing the same value.

Example:

[2, 3, 4, 7, 3, 1]

Without index tracking:

both minimums could incorrectly become 3 (same index)

With index tracking:

first minimum = 1
second minimum = 3

This solution passed, but it felt forced, duplicated logic, and was hard to reason about.

The Key Realization

Eventually, I realized something important:

I don’t need to simulate splitting the array at all.

As long as:

the first subarray starts at index 0
the other two start somewhere after it

I can always split the array like this:

[0 : i] | [i : j] | [j : n]

So the problem reduces to:

Find the two smallest values in nums[1:].

That’s it.

Final Refactored Solution (Clean & Optimal)

This part took me an additional 15 minutes to produce.

func minimumCost(nums []int) int {
    firstMin, lastMin := int(1e9), int(1e9)

    for x := 1; x < len(nums); x++ {
        num := nums[x]
        if num < firstMin {
            lastMin = firstMin
            firstMin = num
        } else if num < lastMin {
            lastMin = num
        }
    }

    return nums[0] + firstMin + lastMin
}

Why I initialised with a large number?

To find a minimum, you must compare against something larger than any possible input.

firstMin, lastMin := int(1e9), int(1e9)

This guarantees the first real value replaces them.

Understanding the `else if` Clause

Consider the array:

[1, 4, 8, 2]

We start scanning from index 1.

Step	num	firstMin	lastMin
init	—	∞	∞
4	4	4	∞
8	8	4	8
2	2	2	4

Explanation:

If num < firstMin, the old firstMin becomes lastMin
If num is not smaller than firstMin but smaller than lastMin, it becomes the second minimum

This maintains the invariant:

firstMin ≤ lastMin

at all times.

Final Takeaways

nums[0] is always part of the cost → treat it as constant
The problem is about choosing start indices, not subarrays
You don’t need to split the array — the split is implicit
A single-pass O(n) solution is enough

This problem taught me an important lesson:

When a problem looks structural, it’s often really about values.

Sometimes the clean solution only appears after you overthink it once.

Happy coding 🚀

DEV Community: rezzcode ∞

Leetcode Sunday #5

LeetCode 1980: Find Unique Binary String

The Problem

My First Thought

The Hard Part: Generating a Unique Binary String

A Better Insight

My Implementation

Possible Optimisation

Leetcode Sunday #4

How My “Worst” Complexity Solution Beat 100% Runtime — Binary Gap in Go

Problem Recap — What Is a Binary Gap?

Example

First Approach — Store All Gaps and Sort (O(n log n))

Implementation

Complexity

Second Approach — Track the Maximum On the Fly (O(1) Space)

Implementation

Complexity

The Surprise

Why the “Worse” Algorithm Won?

The Input Size Is Tiny

Online Judge Timing Granularity

The Memory RSS Differences Are Not Just About Variables

The Real Lesson

The Last Optimal Refactor

Final Takeaway

Leetcode Sunday #3

LeetCode 67: Add Binary

The Confident First Attempt

Rethinking the Problem

Base 10 Example

Binary Equivalent

Designing the Logic

About String Concatenation

Final Working Solution

Why This Worked

Key Takeaway

Leetcode Sunday #2

LeetCode 110: Balanced Binary Tree

My Initial Misinterpretation

The Key Realization

Why This Is a Height Problem

The First Recursive Attempt (And Why It Failed)

The Problem With Returning bool

Designing a Better Recursive Contract

The Sentinel-Value Trick (Almost Right)

The Idea

The Bug: Direction vs Distance

Visualizing the Problem

What Should Happen

What Actually Happened

The Fix: Absolute Difference

The Final Solution

What This Problem Actually Taught Me

Final Thoughts

Leetcode Sunday #1

Leetcode 3010: Divide an Array Into Subarrays With Minimum Cost I

Problem Summary

First Observation: nums[0] Is Always Included

What Actually Affects the Minimum Cost

Early Implementation (Accepted but Fragile)

Why I Needed the Index

The Key Realization

Final Refactored Solution (Clean & Optimal)

Why I initialised with a large number?

Understanding the else if Clause

Final Takeaways

The Problem With Returning `bool`

First Observation: `nums[0]` Is Always Included

Understanding the `else if` Clause