DEV Community

Ertugrul
Ertugrul

Posted on

πŸ—“ Daily LeetCode Progress – Day 16

Problems Solved:

  • #118 Pascal's Triangle
  • #66 Plus One

This continues my daily series (Day 16: Constructive Row Generation + Carry Handling). Today I explored how to build Pascal's Triangle row by row using previous results and how to handle digit addition with proper carry management.


πŸ’‘ What I Learned

  • For Pascal's Triangle, dynamic row generation is the key. Each new row starts and ends with 1, while the middle values come from the sum of two numbers directly above. This can be done in O(numRowsΒ²) time without extra complexity.
  • For Plus One, directly converting digits into an integer can cause overflow in C++, so the robust way is to simulate addition with a carry. This ensures correctness for arbitrarily large digit arrays.
  • Both problems demonstrate how iterative construction with local state (row or carry) can elegantly solve array-based challenges.

🧩 #118 β€” Pascal's Triangle

Python (Row Construction)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = [[1]]

        for i in range(1, numRows):
            prev = result[-1]
            row = [1]
            for j in range(1, len(prev)):
                row.append(prev[j-1] + prev[j])
            row.append(1)
            result.append(row)

        return result
Enter fullscreen mode Exit fullscreen mode

C++ (Row Construction)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        result.push_back({1});

        for (int i = 1; i < numRows; i++) {
            vector<int> prev = result.back();
            vector<int> row;
            row.push_back(1);

            for (int j = 1; j < prev.size(); j++) {
                row.push_back(prev[j-1] + prev[j]);
            }

            row.push_back(1);
            result.push_back(row);
        }

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Why it works: each row is fully determined by the row before, so we can build the triangle iteratively.

Time: O(numRowsΒ²)
Space: O(numRowsΒ²)


🧩 #66 β€” Plus One

Python (String Conversion)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        new_int = int(''.join(map(str, digits)))
        new_int += 1
        liste = [int(x) for x in str(new_int)]
        return liste
Enter fullscreen mode Exit fullscreen mode

C++ (Carry Simulation)

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        int carry = 1; // start with +1

        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }

        if (carry > 0) {
            digits.insert(digits.begin(), carry);
        }

        return digits;
    }
};
Enter fullscreen mode Exit fullscreen mode

Why it works: simulating addition with carry prevents integer overflow and works even for very large arrays.

Time: O(n)
Space: O(1) (in-place modification)


πŸ“Έ Achievements

  • Pascal's Triangle (Python & C++)

pascal py

pascal cpp

  • Plus One (Python & C++)

plusone py

plusone cpp


πŸ“¦ Complexity Recap

  • Pascal's Triangle: quadratic in number of rows.
  • Plus One: linear in digit length, constant extra space.

πŸ“£ Join the Journey

I’m solving and documenting problems daily in both Python and C++, covering arrays, linked lists, dynamic programming, and more. Follow along if you’re interested in systematic problem solving.

Links

Top comments (0)