Given two integers r and c, where positions are 1-indexed in Pascal's Triangle and 1 <= c <= r. Every boundary value is 1, and every interior value is the sum of the two values directly above it from the previous row. Return the value at the rth row and cth column.
Example 1
Input: r = 4, c = 2
Output: 3
Explanation: The fourth row is [1, 3, 3, 1]. The second value in this row is 3.
Example 2
Input: r = 6, c = 4
Output: 10
Explanation: The sixth row is [1, 5, 10, 10, 5, 1]. The fourth value in this row is 10.
Brute Force Approach
The most direct method builds the full triangle from the first row until row r is available. Since each new row depends on the previous row, all earlier rows are kept.
This mirrors the definition exactly. Boundary values are placed as 1, and interior values are computed from the two adjacent values above them. It uses extra storage because rows before the target row remain saved even after the answer is known.
Algorithm
Create a triangle container and place the first row
[1]; forr = 1, this row already contains the answer.Build every remaining row from row
2through rowr.Start each new row with all values as
1, so both boundary positions are already correct.Fill every interior column by adding the upper-left and upper-right values from the previous row.
Store the completed row so the next row can use it.
Stop after row
ris stored and return the value at columncfrom that row.
Dry Run
Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the value at the requested Pascal position. long long pascalValue(int r, int c) { vector<vector<long long>> triangle; triangle.push_back({1}); // Build every row needed to reach the requested row. for (int row = 2; row <= r; row++) { vector<long long> current(row, 1); // Fill interior cells from adjacent values in the previous row. for (int col = 1; col < row - 1; col++) { current[col] = triangle[row - 2][col - 1] + triangle[row - 2][col]; } triangle.push_back(current); } return triangle[r - 1][c - 1]; }};// Driver codeint main() { int r = 6; int c = 4; // instance for class Solution Solution sol; cout << sol.pascalValue(r, c) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(r²), because all values from row 1 through row r are generated.
Space Complexity: O(r²), because the complete triangle up to row r is stored.
Optimal Approach
Instead of forming previous rows, the same value can be understood by counting paths from the top of Pascal's Triangle. To reach row r, exactly r - 1 downward moves are made. To land at column c, exactly c - 1 of those moves must go toward the right side of the triangle.
So the problem becomes a choice-counting question: among r - 1 moves, choose which c - 1 moves go right. That count is C(r - 1, c - 1). This also matches Pascal's recurrence, because every interior cell receives all paths from the upper-left cell and all paths from the upper-right cell, so the two counts are added.
These choice counts are called binomial coefficients. After the position is converted to C(n, k), the coefficient can be built directly without constructing earlier rows. Symmetric positions have equal values, so the smaller side of the row is enough. This avoids generating values that are not related to the requested cell.
Algorithm
Convert the position to zero-indexed form with
n = r - 1andk = c - 1.Replace
kwith the smaller ofkandn - k, because symmetric columns have the same value.Start the answer as
1, representingC(n, 0)and also covering boundary columns.Multiply by the next numerator factor and divide by the current denominator factor to form the next coefficient exactly.
Continue until
kfactors have been processed.Return the final answer, which equals
C(r - 1, c - 1).
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the value at the requested Pascal position. long long pascalValue(int r, int c) { int n = r - 1; int k = min(c - 1, r - c); long long answer = 1; // Build the coefficient using exact multiplication and division. for (int step = 1; step <= k; step++) { answer = answer * (n - k + step) / step; } return answer; }};// Driver codeint main() { int r = 6; int c = 4; // instance for class Solution Solution sol; cout << sol.pascalValue(r, c) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(min(c - 1, r - c)), because only the shorter side of the binomial coefficient is processed.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
The requested position is on the boundary of the triangle. The optimal formula naturally returns 1 because the number of processed factors becomes 0.
Be the first to add a comment.