Paths to Reach Origin

Problem Description

Imagine you are standing on a grid at point (x, y). You can only move down (y decreases) or right (x increases). Your goal is to reach the origin (0, 0). This document discusses how to find the total number of unique paths you can take to reach the origin.

Example

Input: x = 3, y = 2 (Starting at point (3, 2))

Output: 3

There are three unique paths to reach the origin:

1. Down, Down, Right (D-D-R)
2. Down, Right, Down (D-R-D)
3. Right, Down, Down (R-D-D)

---

Solutions for Finding Paths

There are multiple approaches to solve this problem. Here, we will explore four common techniques:

• Recursive
• Memoization
• Tabulation
• Space Optimization

Approach 1: Recursive

A recursive approach solves the problem by breaking down the larger problem into smaller subproblems.

Implementation

class Solution {
    ways(x, y) {
        return this.help(x, y);
    }

    help(i, j) {
        // Base case
        if (i === 0 && j === 0) return 1;
        if (i < 0 || j < 0) return 0;

        // Recursive calls
        const down = this.help(i - 1, j);
        const right = this.help(i, j - 1);

        return down + right;
    }
}

Codes in Different Languages

JavaScript

Written by @Vipullakum007

class Solution {
    ways(x, y) {
        return this.help(x, y);
    }

    help(i, j) {
        // Base case
        if (i === 0 && j === 0) return 1;
        if (i < 0 || j < 0) return 0;

        // Recursive calls
        const down = this.help(i - 1, j);
        const right = this.help(i, j - 1);

        return down + right;
    }
}

Python

Written by @Vipullakum007

class Solution:
    def ways(self, x, y):
        return self.help(x, y)

    def help(self, i, j):
        # Base case
        if i == 0 and j == 0:
            return 1
        if i < 0 or j < 0:
            return 0

        # Recursive calls
        down = self.help(i - 1, j)
        right = self.help(i, j - 1)

        return down + right

Java

Written by @Vipullakum007

  class Solution {
      public int ways(int x, int y) {
          return help(x, y);
      }

      private int help(int i, int j) {
          // Base case
          if (i == 0 && j == 0) return 1;
          if (i < 0 || j < 0) return 0;

          // Recursive calls
          int down = help(i - 1, j);
          int right = help(i, j - 1);

          return down + right;
      }
  }

C++

Written by @Vipullakum007

class Solution {
public:
    int ways(int x, int y) {
        return help(x, y);
    }

    int help(int i, int j) {
        // Base case
        if (i == 0 && j == 0) return 1;
        if (i < 0 || j < 0) return 0;

        // Recursive calls
        int down = help(i - 1, j);
        int right = help(i, j - 1);

        return down + right;
    }
};

Complexity Analysis

Time Complexity: $O(2^{x+y})$

• In the worst case, each move (left or down) results in two recursive calls, leading to an exponential number of calls.

Space Complexity: $O(x + y)$

• The space complexity is due to the maximum depth of the recursion stack.

tip

When choosing an approach, consider both time and space complexities. For smaller inputs, simpler approaches like recursion might be sufficient, but for larger inputs, optimized solutions like memoization, tabulation, or space-optimized tabulation are more efficient and practical. Always analyze the constraints and requirements of your problem to select the most appropriate method.

Would you like any additional information or another example?

---

References

• LeetCode Problem: Maximum Depth of Binary Tree
• Solution Link: LeetCode Solution
• Authors GeeksforGeeks Profile: Vipul