algoadvance

Leetcode 66. Plus One

Problem Statement

LeetCode 66: Plus One

Given a non-empty array of digits representing a non-negative integer, increment the integer by one. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Example:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Clarifying Questions

1. Q: Can the input array be empty? A: No, the problem states that the array is non-empty.

2. Q: Should I consider edge cases like [9, 9, 9]? A: Yes, your solution should handle cases where there’s a carry-over that impacts the most significant digit.

3. Q: Can the digits array contain negative values or values greater than 9? A: No, each element in the array represents a single digit from 0 to 9.

Strategy

1. Start from the last digit of the array and move backwards.
2. Add 1 to the last element. If it becomes 10, set it to 0 and move to the next digit on the left, adding 1 to it.
3. Continue this process until there are no more carry-overs.
4. If after processing all digits a carry is left, insert 1 at the beginning of the array.
5. Return the modified array.

Code

public class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        
        // If control comes here means digits were all 9's
        int[] result = new int[n + 1];
        result[0] = 1; // the most significant digit is 1
        return result;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the digits array. We may need to scan the entire array once in the worst-case scenario.
• Space Complexity: O(1) for the input array in-place change, O(n) only if a new array is required (like in the case of all 9’s).

This solution effectively handles the primary edge cases, including carry-over logic when all digits are 9.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?