RECUR25 - Editorial

editorial
, , ,
1

Problem Link - Pascal Triangle Element in Recursion

Problem Statement:

Given an integer N, representing the row number, and an integer M, representing the column number, find the value at the intersection of the Nth row and Mth column of Pascal’s Triangle.

Approach:

The logic is based on the fact that each element in Pascal’s Triangle is the sum of the two elements directly above it.

  • Base Case: If M=0 or M=N, the answer is 1. This corresponds to the edges of Pascal’s Triangle, where the first and last elements of each row are always 1. An additional check ensures that the column value M is within a valid range. If M>N, it’s an invalid input.

  • Recursive Case: For other positions, the value at the Nth row and Mth column is the sum of the values from the previous row:
    Pascal’s value at (N, M) = Pascal’s value at (N−1, M−1) + Pascal’s value at (N−1, M).

Complexity:

  • Time Complexity: Since this recursive solution has overlapping subproblems, its time complexity is exponential, specifically O(2^N) because each recursive call contains two more recursive calls, leading to a binary tree-like recursion.

  • Space Complexity: O(N) because of the recursion stack, where N is the depth of the recursion (equal to the row number).