Understanding Array Manipulation — Level 2: Implementation Guide

The Plus One Algorithm

Let's implement the "add one" operation from Level 1. Here's the algorithm:

1. Start from the last element (rightmost digit)
2. While we haven't processed all elements:
   • If current element < 9: increment it and return
   • If current element == 9: set it to 0 and move left
3. If loop completes, insert 1 at the beginning

Python Implementation

def plus_one(digits):
    n = len(digits) - 1

    # Process from right to left
    while n >= 0:
        if digits[n] < 9:
            digits[n] += 1
            return digits
        digits[n] = 0
        n -= 1

    # All digits were 9, insert 1 at beginning
    return [1] + digits

Key points:

• Modifies the array in-place for most cases
• Only creates a new array when all digits are 9
• Time complexity: O(n) worst case, O(1) best case

Java Implementation

public int[] plusOne(int[] digits) {
    int n = digits.length - 1;

    while (n >= 0) {
        if (digits[n] < 9) {
            digits[n]++;
            return digits;
        }
        digits[n] = 0;
        n--;
    }

    // All digits were 9, create new array
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    return result;
}

Key points:

• Arrays in Java have fixed size, so we need a new array for the all-9s case
• Uses digits.length instead of len(digits)
• Postfix increment (++) adds 1 and returns the value

C++ Implementation

vector<int> plusOne(vector<int>& digits) {
    int n = digits.size() - 1;

    while (n >= 0) {
        if (digits[n] < 9) {
            digits[n]++;
            return digits;
        }
        digits[n] = 0;
        n--;
    }

    // All digits were 9, insert 1 at beginning
    digits.insert(digits.begin(), 1);
    return digits;
}

Key points:

• Pass by reference (&) to avoid copying
• vector::insert() shifts all elements when inserting at the beginning
• Uses size() method instead of length

Common Array Manipulation Patterns

Beyond the "plus one" operation, here are fundamental patterns you'll use frequently:

1. Two Pointers Technique

# Reverse an array in-place
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

2. In-Place Removal

# Remove all instances of a value
def remove_element(arr, val):
    write_index = 0
    for read_index in range(len(arr)):
        if arr[read_index] != val:
            arr[write_index] = arr[read_index]
            write_index += 1
    return arr[:write_index]

3. Running Sum

# Calculate running sum in-place
def running_sum(arr):
    for i in range(1, len(arr)):
        arr[i] += arr[i - 1]
    return arr

Common Pitfalls and Solutions

# BAD: Can overflow for large arrays
num = int(''.join(map(str, digits)))
num += 1
return list(map(int, str(num)))

# BAD: Uses extra space
result = digits.copy()
# modify result...

# BAD: Misses the first element
for i in range(len(digits) - 1, 0, -1):
    # process...

Production Tips

• Validate input: Check for empty arrays, negative numbers, or invalid digits
• Use meaningful variable names: write_index instead of i
• Document edge cases: Comment the all-9s case explicitly
• Write tests: Cover empty array, single digit, all 9s, and normal cases
• Consider constraints: For very large arrays, even O(n) might be slow

Complexity Analysis