🚀 Day 35 of DSA Problem Solving

❓ Question 1: Print Numbers from 1 to N

Write a recursive function that prints numbers from 1 to n.

🧭 Approach

To solve this problem, we use a simple recursive function to print numbers from 1 to n in ascending order.

🎯 Goal

We want to print all numbers starting from 1 up to n, each on a new line.

🔁 Using Recursion

We define a function called printAscending(n, x) where:

• n is the upper limit — the number we want to count up to.
• x is the current number being printed (starts from 1 by default).

🛑 Base Case

If x > n, we stop the recursion. This prevents further function calls once we’ve printed all numbers.

🔄 Recursive Step

If x <= n:

1. Print the current number x.
2. Call the function again with x + 1.

This continues until the base case is reached.

---

📌 Example

If n = 5, the output should be:

1
2
3
4
5

🧑‍💻 JavaScript Code

function printAscending(n, x = 1) {
  if (x > n) return;           // base case
  console.log(x);              // print current number
  printAscending(n, ++x);      // recursive call with incremented x
}

console.log(printAscending(10));

🕒 Time Complexity: O(n)

The function runs once for each number from 1 to n.

Each call performs a constant-time operation (printing and a single recursive call), so the total time is proportional to n.

🧠 Space Complexity: O(n)

Since the function is recursive, each call is placed on the call stack.

For n numbers, there will be n recursive calls, resulting in n stack frames.

So, the space used grows linearly with n.

❓ Question 2: Climbing Stairs

You are given a staircase with n steps.
You can climb either 1 step or 2 steps at a time.
Your goal is to find how many distinct ways you can climb to the top.

🔸 Example

If n = 5, you can climb in these 8 ways:

1+1+1+1+1  
1+1+1+2  
1+1+2+1  
1+2+1+1  
2+1+1+1  
2+2+1  
2+1+2  
1+2+2

🧠 The Idea Behind the Solution

This is a classic recursion problem, very similar to computing the Fibonacci sequence.

To reach step n, you must have come from:

• Step n - 1 (by taking 1 step), or
• Step n - 2 (by taking 2 steps)

So, the total ways to reach step n is:

climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)

✅ Your Code

let arr = []; // Memoization array to store results

function climbStairs(n) {
  if (n <= 2) return n; // Base cases

  if (!arr[n]) {
    arr[n] = climbStairs(n - 2) + climbStairs(n - 1); // Recursive relation
    console.log(arr); // To show how the array fills up
  }

  return arr[n]; // Return memoized result
}

console.log(climbStairs(5)); // Output: 8

📌 Step-by-Step Execution for climbStairs(5)

Step 1:

climbStairs(5)

Since arr[5] is not defined:

It needs climbStairs(3) and climbStairs(4)

Step 2: climbStairs(4)

Since arr[4] is not defined:

It needs climbStairs(2) and climbStairs(3)

Step 3: climbStairs(3)

Since arr[3] is not defined:

It needs climbStairs(1) and climbStairs(2)

Step 4: Base Cases

climbStairs(1) → returns 1

climbStairs(2) → returns 2

Backtracking and Storing

Now we go back up and store results:

climbStairs(3) = 1 + 2 = 3 → arr[3] = 3  
climbStairs(4) = 2 + 3 = 5 → arr[4] = 5  
climbStairs(5) = 3 + 5 = 8 → arr[5] = 8

Final Output:

console.log(climbStairs(5)); // Output: 8

🧮 Visualization of Calls:

climbStairs(5)
 ├── climbStairs(4)
 │    ├── climbStairs(3)
 │    │    ├── climbStairs(2) → 2
 │    │    └── climbStairs(1) → 1
 │    └── climbStairs(2) → 2 (already known)
 └── climbStairs(3) → 3 (from arr)

⏱ Time and Space Complexity

✅ Time Complexity: O(n)

• Each number from 1 to n is calculated only once.
• After it's calculated, we store the result in the array arr[] (memoization).
• So, we do n unique calculations, and never repeat them.

🔁 No repeated work → Linear time complexity → O(n)

---

✅ Space Complexity: O(n)

There are two main reasons for the space usage:

1. 🧠 Memoization Array arr[]

   • We store up to n results in an array.
   • This takes O(n) space.

2. 📞 Recursive Call Stack

   • In the worst case (e.g., no memoization yet), the recursion can go as deep as n calls.
   • So the call stack uses up to O(n) space too.

---

https://leetcode.com/problems/letter-combinations-of-a-phone-number/submissions/1750272767/

❓ Question 3: Letter Combinations of a Phone Number

var letterCombinations = function(digits) {
    const phoneMapping = [
      "", // 0
      "" , // 1
     "abc",  // 2
    "def",  // 3
    "ghi",  // 4
     "jkl",  // 5
    "mno",  // 6
  "pqrs", // 7
  "tuv",  // 8
  "wxyz"  // 9
];

  const Combo = [];

  if(digits.length < 1) return Combo

  let backTrack = (index,path) =>{

    if(index === digits.length){
      Combo.push(path)
      return;
    }

     const digit = digits[index];
     const letters = phoneMapping[digit];



  for(let char of letters){
     backTrack(index + 1, path + char);
  }

  }

    backTrack(0, '')
   return Combo;

};


console.log(letterCombinations('23'))