leetcode

Plus One solution using TypeScript

Below is my TypeScript solution to the LeetCode "Plus One" question.

Time Complexity: Because there will be, at most, one iteration over the array, the time complexity is O(n) where n represents the number of elements in the array.

Space Complexity: In cases where the array contains a value that is not 9, the operations will all happen in-place, making the space complexity O(1). In cases where the array contains only values of 9, a copy of the array will need to be made, making the space complexity O(n).

/**
 * Plus One
 * Given a non-empty array of digits representing a 
 * non-negative integer, increment one to the integer.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 *
 * plusOne([1,2,3]) // [1,2,4]
 * plusOne([9,9,9]) // [1,0,0,0]
 */
function plusOne(digits: number[]): number[] {
    // create a pointer at the end of the array
    let ptr = digits.length;

    // iterate over the array in reverse order
    while (ptr > 0) {
        ptr -= 1;
        // if digit is 9, carry the 1 again
        if (digits[ptr] === 9) {
            digits[ptr] = 0;
        } 
        // otherwise add it
        else {
            digits[ptr] += 1;
            return digits;
        }
    }
    // create new array element for the carried value
    return [1].concat(digits);
}

more LeetCode posts