66. Plus One

📝 Problem Details

• Title: 66. Plus One
• Link: https://leetcode.com/problems/plus-one/
• Difficulty: Easy
• Tags/Categories: Math Arrays

💭What Were My Initial Thoughts?

- start from the back of the array
- carry a 1 forward to the next element if the current element + 1 is == 10
- if the first element (the largest value) is 9, then we need to emplace a new element of 1 at the front of the array
- return the array

🤔What Did I Struggle With?

~

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
      int n = digits.size() - 1;
      
      for (int i = n; i >= 0; --i) { // traverse digits from the last element (least significant)
        // since we begin with the last digit, increasing that digit by one
        // results in overflow.  Therefore, all elements PRIOR to digits[0]
        // need to be considered since there may be additional nines between
        // digits[0], ... , digits[n].
        if (digits[i] == 9) {  
          digits[i] = 0;
        } else {  // current digit is not 9 so we can safely increment by one
          digits[i] += 1;
          return digits;
        }
      }
      // if the program runs to this point, each 9 is now a 0.
      // to get a correct solution, we need to add one more element with 
      // a value of zero AND set digits[0] to 1 (in the most significant position)
      // to account for the carry digit.
      digits.push_back(0);
      digits[0] = 1;
      return digits;
    }
};