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
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;
}
};
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
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;
}
};
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++)
- Plus One (Python & C++)
π¦ 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
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)