Beats 100% || Most optimised solution || Java C++
Intuition\nThe problem requires adding 1 to an array of digits representing a non-negative integer. My initial thought is that this is similar to manually perfo
# Intuition\nThe problem requires adding 1 to an array of digits representing a non-negative integer. My initial thought is that this is similar to manually performing addition with carrying over when digits are 9. If there is no carry, we can return immediately after adding 1 to the last digit. If the number ends with multiple 9s, we need to propagate the carry.\n\n# Approach\n1) Start from the last digit and iterate backward.\n2) If the digit is not 9, simply add 1 to it and return the array.\n3) If the digit is 9, set it to 0 and continue to the next digit.\n4) If all digits are 9, create a new array with one more element than the original array, set the first digit to 1, and return it (as it represents a power of 10).\n\n# Complexity\n- Time complexity:\nThe time complexity is O(n), where n is the length of the input array. This is because, in the worst case, we need to iterate through all digits if they are all 9.\n\n- Space complexity:\nThe space complexity is O(n). In the worst case, if all digits are 9, we need to allocate a new array of size n+1.\n![193730892e8675ebafc11519f6174bee5c4a5ab0.jpeg](https://assets.leetcode.com/users/images/b517d44d-1e73-41c5-bee4-7c3935e6d898_1725904730.5603921.jpeg)\n\n\n# Code\n```java []\nclass Solution {\n    public int[] plusOne(int[] digits) {\n        // Traverse the array from the last digit to the first\n        for (int i = digits.length - 1; i >= 0; i--) {\n            // If the current digit is not 9, simply add 1 to it and return the array\n            if (digits[i] != 9) {\n                digits[i] += 1;\n                return digits;\n            }\n            // If the current digit is 9, set it to 0 and continue\n            digits[i] = 0;\n        }\n        // If all digits were 9, we create a new array with an additional leading 1\n        int[] newDigits = new int[digits.length + 1];\n        newDigits[0] = 1;  // Set the first digit to 1, rest are already 0 by default\n        return newDigits;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> plusOne(vector<int>& digits) {\n        // Traverse the array from the last digit to the first\n        for (int i = digits.size() - 1; i >= 0; i--) {\n            // If the current digit is not 9, simply add 1 to it and return the array\n            if (digits[i] != 9) {\n                digits[i] += 1;\n                return digits;\n            }\n            // If the current digit is 9, set it to 0 and continue\n            digits[i] = 0;\n        }\n        // If all digits were 9, we create a new vector with an additional leading 1\n        vector<int> newDigits(digits.size() + 1, 0); // All elements initialized to 0\n        newDigits[0] = 1;  // Set the first digit to 1\n        return newDigits;\n    }\n};\n\n```
['Array', 'Math', 'C++', 'Java']