Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to copy the same process that's done on paper.

    We start at the rightmost index of digits and set the carry as 1. We then perform addition operations until we no longer need to carry a 1 forward OR we're out of bounds of digits.

    If we're out of bounds and carry is still equal to 1, since digits contained all 9s, than we need to create a new array of size digits.length + 1.

    Ex. digits = {9, 9, 9, 9} becomes {1, 0, 0, 0, 0}

    Time Complexity
    The time complexity is O(n) where n is the size of digits, since we may traverse through all numbers if they are all 9s. Example: digits = {9, 9, 9, 9}.

    class Solution {
        public int[] plusOne(int[] digits) {
            int carry = 1;
            int index = digits.length - 1;
            
            // Keep adding 1 if carry == 1 and in bounds
            while (carry == 1 && index >= 0) {
                int sum = carry + digits[index];
                carry = sum / 10;
                digits[index] = sum % 10;
                index--;
            }
            // Need to create a new array of size digits.length+1
            if (index < 0 && carry == 1) {
                digits = new int [digits.length + 1]; // Init to 0s
                digits[0] = 1;
            }
            return digits;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.