Incremental Construction with Invariant Checking

There's a moment in every LeetCode grind where you solve a problem, feel good about it, close the tab, and move on. Then, a day later, the solution taps you on the shoulder and says: you missed something.

That happened to me with Reverse Integer. Twice, actually. And the gap between my first solution and my second isn't really about integers. It's about a decision every one of us makes constantly without noticing: do I figure out the whole plan before I move, or do I move and check my footing with every step?

Let's walk through it.

The Problem, Stripped Down

You're given a signed 32-bit integer x. Reverse its digits. If the reversed number falls outside [-2^31, 2^31 - 1], return 0. Oh, and — twist of the knife — assume you can't just cast to a 64-bit integer to dodge the overflow check. You have to actually reason about the boundary.

That constraint is the whole problem. Reversing digits is trivial. Respecting the 32-bit ceiling without a 64-bit escape hatch is where the thinking happens.

Attempt One: I Went Looking for the Boundary Before I Moved

My instinct was to study the wall before running at it.

I stared at the maximum positive value: 2147483647. And I noticed something almost poetic — the last digit of the original number becomes the first digit of the reversed number. Whatever digit is sitting at the end of x is about to become the leading digit of my answer. That digit alone tells me a lot about whether I'm in danger.

So I built a classification:

1. If that leading digit is less than 2 — I'm safe no matter what. The biggest possible reversed number starting with 0 or 1 can never beat 2147483647. No further checking needed.

2. If that leading digit is exactly 2 — now I'm standing right on the edge. This is the case that actually matters. I have to reverse everything after that digit and compare it against 147483647, because that's the only way to know if the full number would tip past the limit.

3. If that leading digit is greater than 2 — a number starting with 3 through 9 and having 10 digits always overflows. So all I need to check is whether the rest of the number has fewer than 9 digits. If it does, we're fine — the total digit count keeps us under the ceiling regardless of the leading digit.

I want to pause here, because I don't think this deserves the dismissal "overcomplicated" that I initially gave myself in my head. This is a real insight. It's boundary analysis — the same kind of thinking you'd use to prove a mathematical inequality. I looked at the shape of the maximum value, split the problem into cases based on that shape, and pre-validated before doing any actual reversal work.

Here's that solution:

class Solution:

    def reverse_number(self, number):
        is_negative = number < 0
        number = abs(number)

        reversed_number = 0

        while number != 0:
            last_digit = number % 10
            number //= 10

            reversed_number = reversed_number * 10 + last_digit

        return -reversed_number if is_negative else reversed_number

    def get_last_digit(self, number):
        return abs(number - int(number / 10) * 10)

    def get_number_without_last_digit(self, number):
        return int(number / 10)

    def count_digits(self, number):
        number = abs(number)

        if number == 0:
            return 1

        digit_count = 0

        while number != 0:
            number //= 10
            digit_count += 1

        return digit_count

    def is_remaining_number_in_limit(self, number):
        if number < 0:
            return abs(number) <= 147483648

        return number <= 147483647

    def reverse(self, x: int) -> int:
        first_digit_after_reversal = self.get_last_digit(x)
        remaining_number = self.get_number_without_last_digit(x)

        if first_digit_after_reversal < 2:
            return self.reverse_number(x)

        if first_digit_after_reversal == 2:
            remaining_reversed_number = self.reverse_number(
                remaining_number
            )

            if not self.is_remaining_number_in_limit(
                remaining_reversed_number
            ):
                return 0

            return self.reverse_number(x)

        remaining_digit_count = self.count_digits(remaining_number)

        if remaining_digit_count < 9:
            return self.reverse_number(x)

        return 0

It passed. I felt clever. I closed the tab.

The Tap on the Shoulder

The next day, re-reading my own code, something started to itch.

Look at what this solution actually does: it inspects the first digit of the future result before the result exists. It computes remaining_number, fully reverses it in a separate pass, and only then decides if the original reversal is allowed to proceed. It's making a prediction about the outcome of an operation it hasn't performed yet — by partially performing a related operation just to make that prediction.

And that's when the real question surfaced:

Why am I analyzing the whole operation ahead of time — when I'm going to walk through the digits one by one anyway?

I already loop through digits to reverse them. That loop is unavoidable. So instead of doing a pre-flight inspection of where I'll end up, what if I just... checked my footing at each step of the walk itself?

That reframing changed everything. Instead of:

analyze → decide → construct

I could do:

construct → check whether the next step is valid → continue

Attempt Two: Build It, and Ask Permission at Every Step

Here's the idea in plain language. At every iteration of the loop:

1. Take the next digit off the remaining input.
2. Before adding it to my partial answer, ask: would appending this digit push my partial answer outside the valid range?
3. If yes — stop immediately. Return 0. No further work needed.
4. If no — append the digit.
5. Shrink the remaining input by one digit.
6. Repeat.

The key realization is this: I never need to know the final answer to know whether the final answer is illegal. I only need to know whether this specific digit, appended to what I've already built, breaks the rule. If it does, I can bail out on the spot — I don't even need to finish reversing.

This is the invariant at the heart of the whole approach:

The partial reversed_number is always within the valid 32-bit range.

Not "the input is analyzed and therefore the final answer will be in range." Something stricter and more local: at every single point in time during construction, what I currently hold in my hand is legal. I never let an illegal value come into existence, not even for a moment. Before I extend the state, I check whether the extension respects the invariant. If it wouldn't, I simply refuse to take that step.

The overflow check itself becomes almost mechanical once you frame it that way. INT_MAX is 2147483647. If my partial reversed number is already greater than 214748364 (everything except the last digit), then appending any digit will overflow — because that would produce a 10th digit where none is allowed. And if my partial number is exactly 214748364, I only overflow if the new digit is greater than 7 — because 2147483647 is the actual ceiling. The negative side mirrors this with -214748364 and a threshold digit of -8, since the negative floor is -2147483648.

Here's that solution:

class Solution:

    def make_room_for_new_digit(self, number):
        return number * 10

    def append_digit(self, number, digit):
        return self.make_room_for_new_digit(number) + digit

    def get_last_digit(self, number):
        return number - int(number / 10) * 10

    def is_negative(self, number):
        return number < 0

    def would_appending_digit_overflow(self, number, digit):
        if self.is_negative(number):
            return (
                number < -214748364
                or (number == -214748364 and digit < -8)
            )

        return (
            number > 214748364
            or (number == 214748364 and digit > 7)
        )

    def remove_last_digit(self, number):
        return int(number / 10)

    def reverse(self, x: int) -> int:
        reversed_number = 0
        remaining_number = x

        while remaining_number != 0:
            next_digit = self.get_last_digit(remaining_number)

            if self.would_appending_digit_overflow(
                reversed_number, next_digit
            ):
                return 0

            reversed_number = self.append_digit(
                reversed_number, next_digit
            )

            remaining_number = self.remove_last_digit(
                remaining_number
            )

        return reversed_number

No pre-computation of a "remaining reversed number." No separate case for leading digits 0, 1, 2, or 3-through-9. No digit-counting helper. One loop, one check, one invariant. The overflow logic that used to be spread across three branches collapsed into a single guard clause that runs identically on every iteration.

Both solutions are correct. Both pass every test case. But they represent two fundamentally different relationships with the problem — and that difference is the actual article.

The Pattern Underneath: Incremental Construction with Invariant Checking

Here's the thing I want you to take away from this, and it has nothing to do with reversing integers.

My first instinct — and I'd guess it's most people's first instinct — was to scan ahead and decide if the destination is reachable before taking the first step. Figure out the shape of the danger zone, classify where the input falls relative to that zone, then execute.

My second solution replaced that with a different default: take one step, check if that step alone breaks a rule I care about, and only then decide whether to take the next one.

I don't think this pattern has one single, universally agreed-upon textbook name — you'll see pieces of it under "greedy construction," "online algorithms," "streaming validation," or just "short-circuiting." But as a mental model for how I think about these problems now, I call it:

Incremental Construction with Invariant Checking

The shape of it looks like this:

current valid state
       ↓
consider next extension
       ↓
would the extension violate the invariant?
       ↓
   ┌───┴───┐
   no      yes
   ↓        ↓
extend     stop/reject

The state you're building is never allowed to become invalid, not even temporarily. You don't ask "will my final answer be valid?" — a question that usually forces you to either predict the future or do extra work up front to simulate it. You ask a much smaller, much more local question: "does this one next move keep me valid?" And because that question is small, the check is usually cheap, and the logic collapses into something that reads like a single sentence instead of a decision tree.

This shows up everywhere once you start looking for it:

• Parsing and validation — instead of scanning a whole string to check if it will end up well-formed, track a running state (like open-bracket depth) and reject the instant a token breaks it.
• Streaming systems — you often can't see "the whole input" at all, so you're forced into this pattern: validate each incoming chunk against the current state, and reject or buffer accordingly.
• Budget or capacity problems — rather than summing everything first and comparing to a limit, add items one at a time and stop the moment the running total would exceed it.
• Building up a data structure under a constraint (a balanced tree, a bounded queue, a rate limiter) — the invariant is the constraint, and every insertion is guarded by "would this insertion break the invariant?" rather than "let me analyze the whole future sequence of insertions."

The underlying lesson is this:

Don't always scan or analyze the entire input to determine whether the final operation is possible.

When a result can be constructed incrementally, consider constructing it step by step — and at each step, ask only whether the next operation would violate the invariant you're protecting.

It's a smaller question, asked more often, instead of one big question asked once. And smaller questions, asked at the right moment, tend to produce simpler code.

Why I'm Glad I Didn't Stop at the First Solution

If I'd stopped after my first pass, I would have walked away with a working answer to a LeetCode problem. Nothing wrong with that — it was a legitimate insight, and I stand by the boundary-case reasoning behind it.

But sitting with the discomfort of "this feels like more machinery than it should need" is what surfaced the actual transferable skill. The second solution isn't better because it's shorter. It's better because it changed the question I was asking the problem. I stopped asking "what will happen if I do this?" and started asking "is it still safe to do this, right now, given where I already am?"

That's a question worth carrying into the next problem — whichever one it happens to be.