🚀 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'))