The O(n) Club: Plus One Array Madness — Java’s Guide to Not Dropping the Carry

The O(n) Club: Plus One Array Madness — Java’s Guide to Not Dropping the Carry

⚡ TL;DR

Add 1 to an array of digits like a caffeinated accountant, moving right-to-left. Handle carry whenever you slam into a 9, and make more space if you run out of digits. Java version below, caffeine optional:

// Java
for (int i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
        digits[i]++;
        return digits;
    }
    digits[i] = 0;
}
int[] result = new int[digits.length + 1];
result[0] = 1;
return result;

🧠 How Devs Usually Mess This Up

Welcome to the “I forgot the carry” festival!

• Just increment the last digit, ignore any 9s, and hope universe is merciful. Spoiler: it’s not.
• Assume arrays never grow because numbers secretly obey your wishes (hint: [9,9,9] will mess with you).
• Hyperventilate about leading zeros when — fun fact! — this problem says you’ll never see them.

🔍 What’s Actually Going On

Think digital odometer: Last wheel spins, bounces from 9 to 0, and says, “Hey neighbor, your turn!” This ripple moves left until someone isn’t maxed out or you run out of neighbors — in which case, congrats! Your car just hit 10,000 miles and your array just got a free upgrade. This isn’t just addition: it’s a carry conga line. And yes, you’re the DJ.

🛠️ PseudoCode

• Start at the end of the array (least significant digit)
• If the digit is less than 9:
  • Increment it
  • Return the digits (Done! Early exit FTW)
• If the digit is a 9:
  • Turn it into a 0
  • Proceed to the next digit with the carry
• If you fall out of the loop (every digit was a 9):
  • Allocate a shiny new array, length + 1
  • Put a 1 at the front, zeros everywhere else
  • Return your glorious achievement

// Java
for (int i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
        digits[i]++;
        return digits;
    }
    digits[i] = 0;
}
int[] result = new int[digits.length + 1];
result[0] = 1;
return result;

💻 The Code

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Input like [9,9,9]? You must create a bigger array. Not doing so = outputting existential sadness ([0,0,0]).
• A single digit [9]? Your output is [1,0], not [10] (don’t anger the LeetCode gods).
• Space: At worst, you jump to an O(n) array on overflow — most of the time, the array stays put.
• Time: O(n) for a single glorious sweep from the right, no recursion, no array acrobatics, no tears.

🧠 Interviewer Brain-Tattoo

“Mess up your carry, and you’ll always carry regret.” Or as Java would put it: If you don’t catch the overflow, you’ll definitely be out of bounds — in life and arrays.