66.Plus One

📘 LeetCode 66: Plus One

📌 Problem Overview

• Problem Number: 66
• Problem Name: Plus One
• Difficulty: Easy
• Category: Math and Geometry
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Math and Geometry algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/66.Plus-one/:

System.Console.WriteLine(string.Join(", ", PlusOne([1, 2, 3]))); // 1234
System.Console.WriteLine(string.Join(", ", PlusOne([4, 3, 2, 1])));//4322
System.Console.WriteLine(string.Join(", ", PlusOne([9])));//10
System.Console.WriteLine(string.Join(", ", PlusOne([9, 9, 9, 9])));//10000
System.Console.WriteLine(string.Join(", ", PlusOne([0])));//1
 
int[] PlusOne(int[] digits)
{
    for (var i = digits.Length - 1; i >= 0; i--)
    {
        if (digits[i] < 9)
        {
            digits[i]++;
            return digits;
        }
        else
        {
            digits[i] = 0;
        }
    }
    var newDigits = new int[digits.Length + 1];
    newDigits[0] = 1;
    return newDigits;
}
 
 
int[] PlusOne1(int[] digits)
{
    // last element is 9
    // all elements are 9
    // last element is not 9
    bool flag = false;
    foreach (var i in digits)
    {
        if (i == 9)
        {
            flag = true;
        }
    }
    if (flag)
    {
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            if (digits[i] == 9)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i] += 1;
                break;
            }
        }
        Array.Resize(ref digits, digits.Length + 1);
        digits[0] = 1;
        return digits;
    }
    if (digits[digits.Length - 1] == 9)
    {
        digits[digits.Length - 1] = 1;
        Array.Resize(ref digits, digits.Length + 1);
        digits[digits.Length - 1] = 0;
    }
    else
    {
        digits[digits.Length - 1] += 1;
    }
 
    return digits;
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.