Skip to content

Commit 97fdaae

Browse files
darecoderdarecoder
authored
Merge branch 'kunal-kushwaha:main' into stack-problems
2 parents 4251e57 + 493cda3 commit 97fdaae

File tree

10 files changed

+347
-12
lines changed

10 files changed

+347
-12
lines changed

‎SYLLABUS.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -88,7 +88,7 @@
8888
- Recursion String Problems
8989
- [Recursion Array Problems](https://youtu.be/sTdiMLom00U)
9090
- [Recursion Pattern Problems](https://youtu.be/ymgnIIclCF0)
91-
- Subset Questions
91+
- [Subset Questions](https://youtu.be/9ByWqPzfXDU)
9292
- [Space and Time Complexity Analysis](https://youtu.be/mV3wrLBbuuE)
9393
- [Introduction](https://youtu.be/mV3wrLBbuuE)
9494
- [Comparisons of various cases](https://youtu.be/mV3wrLBbuuE?t=1039)

‎assignments/10-recursion.md

Lines changed: 34 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,5 @@
11
# Videos
2-
- [Introduction to Recursion](https://youtu.be/M2uO2nMT0Bk)
3-
- [Recursion Level 1 Questions](https://youtu.be/JxILxTwHukM)
4-
- [Recursion Array Questions](https://youtu.be/sTdiMLom00U)
5-
- [Pattern Questions + Bubble Sort + Selection Sort with Recursion](https://youtu.be/ymgnIIclCF0)
6-
- [Merge Sort](https://youtu.be/iKGAgWdgoRk)
7-
- [Quick Sort](https://youtu.be/Z8svOqamag8)
2+
- [Complete Recursion Course](https://www.youtube.com/playlist?list=PL9gnSGHSqcnp39cTyB1dTZ2pJ04Xmdrod)
83

94
# Problems
105

@@ -13,11 +8,11 @@
138
- [Maximum and Minimum value in an array](https://www.geeksforgeeks.org/recursive-programs-to-find-minimum-and-maximum-elements-of-array/) `GFG`
149
- [First Uppercase Letter in a String](https://www.geeksforgeeks.org/first-uppercase-letter-in-a-string-iterative-and-recursive/) `GFG`
1510
- [Reverse String](https://leetcode.com/problems/reverse-string/) `leetcode`
16-
- [Print 1 To N Without Loop](https://practice.geeksforgeeks.org/problems/print-1-to-n-without-using-loops-1587115620/1/?category[]=Recursion&category[]=Recursion&difficulty[]=-2&page=1&query=category[]Recursiondifficulty[]-2page1category[]Recursion/) `GFG`
11+
- [Print 1 To N Without Loop](https://practice.geeksforgeeks.org/problems/print-1-to-n-without-using-loops-1587115620/1/) `GFG`
1712
- [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) `leetcode`
1813
- [Special Fibonacci](https://www.codechef.com/problems/FIBXOR01/) `CodeChef`
1914
- [Length of string using Recursion](https://www.geeksforgeeks.org/program-for-length-of-a-string-using-recursion/) `GFG`
20-
- [Geek-onacci Number](https://practice.geeksforgeeks.org/problems/geek-onacci-number/0/?category[]=Recursion&category[]=Recursion&difficulty[]=0&page=1&query=category[]Recursiondifficulty[]0page1category[]Recursion/) `GFG`
15+
- [Geek-onacci Number](https://practice.geeksforgeeks.org/problems/geek-onacci-number/0/) `GFG`
2116
- [Recursive Bubble Sort](https://www.geeksforgeeks.org/recursive-bubble-sort/) `GFG`
2217
- [Recursive Insertion Sort](https://www.geeksforgeeks.org/recursive-insertion-sort/) `GFG`
2318
- [Sum of digit of a number using Recursion](https://www.geeksforgeeks.org/sum-digit-number-using-recursion/) `GFG`
@@ -42,13 +37,16 @@
4237
- [Power Set of permutations of a string in Lexicographic order.](https://www.geeksforgeeks.org/powet-set-lexicographic-order/) `GFG`
4338

4439
## Medium
40+
- [Combination Sum](https://leetcode.com/problems/combination-sum/) `leetcode`
41+
- [Word Search](https://leetcode.com/problems/word-search/) `leetcode`
42+
- [Target sum](https://leetcode.com/problems/target-sum/) `leetcode`
4543
- [Find Kth Bit in Nth Binary String](https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/) `leetcode`
4644
- [K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/) `leetcode`
4745
- [Count Good Numbers](https://leetcode.com/problems/count-good-numbers/) `leetcode`
48-
- [N Digit numbers with digits in increasing order](https://practice.geeksforgeeks.org/problems/n-digit-numbers-with-digits-in-increasing-order5903/1/?category[]=Recursion&category[]=Recursion&difficulty[]=1&page=1&query=category[]Recursiondifficulty[]1page1category[]Recursion/) `GFG`
46+
- [N Digit numbers with digits in increasing order](https://practice.geeksforgeeks.org/problems/n-digit-numbers-with-digits-in-increasing-order5903/1/) `GFG`
4947
- [Pow(x, n)](https://leetcode.com/problems/powx-n/) `leetcode`
5048
- [Minimum Non-Zero Product of the Array Elements](https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/) `leetcode`
51-
- [Handshakes](https://practice.geeksforgeeks.org/problems/handshakes1303/1/?category[]=Recursion&category[]=Recursion&difficulty[]=1&page=1&query=category[]Recursiondifficulty[]1page1category[]Recursion/) `GFG`
49+
- [Handshakes](https://practice.geeksforgeeks.org/problems/handshakes1303/1/) `GFG`
5250
- [HackerRank](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=recursion&filters%5Bdifficulty%5D%5B%5D=medium)
5351
- [Divisible Subset](https://www.codechef.com/problems/DIVSUBS) `Codechef`
5452
- [Perfect squares](https://leetcode.com/problems/perfect-squares/)`leetcode`
@@ -57,13 +55,38 @@
5755
- [Different ways to add parantheses in the expression](https://leetcode.com/problems/different-ways-to-add-parentheses/) `leetcode`
5856
- [Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/) `leetcode`
5957
- [Predict the winner.](https://leetcode.com/problems/predict-the-winner/) `leetcode`
58+
- [Gray code](https://practice.geeksforgeeks.org/problems/gray-code-1611215248/1/) `GFG` `Google`
59+
- [Combination Sum II](https://leetcode.com/problems/combination-sum-ii/) `leetcode`
60+
- [combination Sum III](https://leetcode.com/problems/combination-sum-iii/) `leetcode`
61+
- [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/) `leetcode`
62+
- [Letter tile possibilities](https://leetcode.com/problems/letter-tile-possibilities/) `leetcode`
63+
- [All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/) `leetcode`
64+
- [Sort a stack using recursion](https://www.geeksforgeeks.org/sort-a-stack-using-recursion/) `GFG`
65+
- [Reverse a stack using recursion](https://www.geeksforgeeks.org/reverse-a-stack-using-recursion/) `GFG`
66+
- [Beautiful Arrangement](https://leetcode.com/problems/beautiful-arrangement/) `leetcode`
67+
- [Lowest Common Ancestor of a Binary Tree](https://practice.geeksforgeeks.org/problems/lowest-common-ancestor-in-a-binary-tree/1/) `GFG` `Amex`
68+
- [Prime numbers after prime P with sum S](https://www.geeksforgeeks.org/prime-numbers-after-prime-p-with-sum-s/) `GFG`
69+
- [Path with Maximum Gold](https://leetcode.com/problems/path-with-maximum-gold/) `leetcode`
70+
- [Longest Possible Route in a Matrix with Hurdles](https://www.geeksforgeeks.org/longest-possible-route-in-a-matrix-with-hurdles/) `GFG`
71+
- [Tug of war](https://www.geeksforgeeks.org/tug-of-war/) `GFG` `Adobe`
72+
- [Rat in a maze](https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/) `GFG`
6073

6174
## Hard
6275
- [Parsing A Boolean Expression](https://leetcode.com/problems/parsing-a-boolean-expression/) `leetcode`
6376
- [Special Binary String](https://leetcode.com/problems/special-binary-string/) `leetcode`
6477
- [Permutation Sequence](https://leetcode.com/problems/permutation-sequence/) `leetcode`
65-
- [Next Happy Number](https://practice.geeksforgeeks.org/problems/next-happy-number4538/1/?category[]=Recursion&category[]=Recursion&difficulty[]=2&page=1&query=category[]Recursiondifficulty[]2page1category[]Recursion/) `GFG`
78+
- [Next Happy Number](https://practice.geeksforgeeks.org/problems/next-happy-number4538/1/) `GFG`
6679
- [Basic Calculator](https://leetcode.com/problems/basic-calculator/) `leetcode`
6780
- [Integer to English Words](https://leetcode.com/problems/integer-to-english-words/) `leetcode`
6881
- [Maximize Number of Nice Divisors](https://leetcode.com/problems/maximize-number-of-nice-divisors/) `leetcode`
82+
- [N Queens](https://leetcode.com/problems/n-queens/) `leetcode`
83+
- [N Queens II](https://leetcode.com/problems/n-queens-ii/) `leetcode`
84+
- [Word break II](https://leetcode.com/problems/word-break-ii/) `leetcode` `Google`
85+
- [Unique paths III](https://leetcode.com/problems/unique-paths-iii/) `leetcode`
86+
- [Find shortest safe route in a path with landmines](https://www.geeksforgeeks.org/find-shortest-safe-route-in-a-path-with-landmines/) `GFG` `Google`
87+
- [Minimum steps to destination](https://practice.geeksforgeeks.org/problems/minimum-number-of-steps-to-reach-a-given-number5234/1/) `GFG` `Amex` `Adobe`
88+
- [Hamiltonian Cycle](https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/) `GFG`
89+
- [M colorning problem](https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/) `GFG`
90+
- [The Knight's tour](https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/) `GFG`
91+
- [Maximum number possible by doing at-most K swaps](https://www.geeksforgeeks.org/find-maximum-number-possible-by-doing-at-most-k-swaps/) `GFG`
6992
- [HackerRank](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=recursion&filters%5Bdifficulty%5D%5B%5D=hard)

‎lectures/11-sorting/cyclic_sort_notes.pdf

404 KB
Binary file not shown.

‎lectures/12-strings/Strings in detail .pdf

1.42 MB
Binary file not shown.

‎lectures/14-recursion/Backtracking.pdf

1.7 MB
Binary file not shown.

‎lectures/14-recursion/Recursion - Numbers & Dice.pdf

476 KB
Binary file not shown.

‎lectures/14-recursion/code/src/com/kunal/backtracking/AllPaths.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.kunal.backtracking;
2+
3+
import java.util.Arrays;
4+
5+
public class AllPaths {
6+
public static void main(String[] args) {
7+
boolean[][] board = {
8+
{true, true, true},
9+
{true, true, true},
10+
{true, true, true}
11+
};
12+
int[][] path = new int[board.length][board[0].length];
13+
allPathPrint("", board, 0, 0, path, 1);
14+
}
15+
16+
static void allPath(String p, boolean[][] maze, int r, int c) {
17+
if (r == maze.length - 1 && c == maze[0].length - 1) {
18+
System.out.println(p);
19+
return;
20+
}
21+
22+
if (!maze[r][c]) {
23+
return;
24+
}
25+
26+
// i am considering this block in my path
27+
maze[r][c] = false;
28+
29+
if (r < maze.length - 1) {
30+
allPath(p + 'D', maze, r+1, c);
31+
}
32+
33+
if (c < maze[0].length - 1) {
34+
allPath(p + 'R', maze, r, c+1);
35+
}
36+
37+
if (r > 0) {
38+
allPath(p + 'U', maze, r-1, c);
39+
}
40+
41+
if (c > 0) {
42+
allPath(p + 'L', maze, r, c-1);
43+
}
44+
45+
// this line is where the function will be over
46+
// so before the function gets removed, also remove the changes that were made by that function
47+
maze[r][c] = true;
48+
}
49+
50+
51+
52+
static void allPathPrint(String p, boolean[][] maze, int r, int c, int[][] path, int step) {
53+
if (r == maze.length - 1 && c == maze[0].length - 1) {
54+
path[r][c] = step;
55+
for(int[] arr : path) {
56+
System.out.println(Arrays.toString(arr));
57+
}
58+
System.out.println(p);
59+
System.out.println();
60+
return;
61+
}
62+
63+
if (!maze[r][c]) {
64+
return;
65+
}
66+
67+
// i am considering this block in my path
68+
maze[r][c] = false;
69+
path[r][c] = step;
70+
if (r < maze.length - 1) {
71+
allPathPrint(p + 'D', maze, r+1, c, path, step+1);
72+
}
73+
74+
if (c < maze[0].length - 1) {
75+
allPathPrint(p + 'R', maze, r, c+1, path, step+1);
76+
}
77+
78+
if (r > 0) {
79+
allPathPrint(p + 'U', maze, r-1, c, path, step+1);
80+
}
81+
82+
if (c > 0) {
83+
allPathPrint(p + 'L', maze, r, c-1, path, step+1);
84+
}
85+
86+
// this line is where the function will be over
87+
// so before the function gets removed, also remove the changes that were made by that function
88+
maze[r][c] = true;
89+
path[r][c] = 0;
90+
}
91+
}

‎lectures/14-recursion/code/src/com/kunal/backtracking/Maze.java

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
package com.kunal.backtracking;
2+
3+
import java.util.ArrayList;
4+
5+
public class Maze {
6+
public static void main(String[] args) {
7+
// System.out.println(count(3, 3));
8+
// path("", 3, 3);
9+
// System.out.println(pathRet("", 3, 3));
10+
11+
// System.out.println(pathRetDiagonal("", 3, 3));
12+
13+
boolean[][] board = {
14+
{true, true, true},
15+
{true, false, true},
16+
{true, true, true}
17+
};
18+
19+
pathRestrictions("", board, 0, 0);
20+
}
21+
22+
static int count(int r, int c) {
23+
if (r == 1 || c == 1) {
24+
return 1;
25+
}
26+
int left = count(r-1, c);
27+
int right = count(r, c-1);
28+
return left + right;
29+
}
30+
31+
static void path(String p, int r, int c) {
32+
if (r == 1 && c == 1) {
33+
System.out.println(p);
34+
return;
35+
}
36+
37+
if (r > 1) {
38+
path(p + 'D', r-1, c);
39+
}
40+
41+
if (c > 1) {
42+
path(p + 'R', r, c-1);
43+
}
44+
}
45+
46+
static ArrayList<String> pathRet(String p, int r, int c) {
47+
if (r == 1 && c == 1) {
48+
ArrayList<String> list = new ArrayList<>();
49+
list.add(p);
50+
return list;
51+
}
52+
53+
ArrayList<String> list = new ArrayList<>();
54+
55+
if (r > 1) {
56+
list.addAll(pathRet(p + 'D', r-1, c));
57+
}
58+
59+
if (c > 1) {
60+
list.addAll(pathRet(p + 'R', r, c-1));
61+
}
62+
63+
return list;
64+
}
65+
66+
static ArrayList<String> pathRetDiagonal(String p, int r, int c) {
67+
if (r == 1 && c == 1) {
68+
ArrayList<String> list = new ArrayList<>();
69+
list.add(p);
70+
return list;
71+
}
72+
73+
ArrayList<String> list = new ArrayList<>();
74+
75+
if (r > 1 && c > 1) {
76+
list.addAll(pathRetDiagonal(p + 'D', r-1, c-1));
77+
}
78+
79+
if (r > 1) {
80+
list.addAll(pathRetDiagonal(p + 'V', r-1, c));
81+
}
82+
83+
if (c > 1) {
84+
list.addAll(pathRetDiagonal(p + 'H', r, c-1));
85+
}
86+
87+
return list;
88+
}
89+
90+
static void pathRestrictions(String p, boolean[][] maze, int r, int c) {
91+
if (r == maze.length - 1 && c == maze[0].length - 1) {
92+
System.out.println(p);
93+
return;
94+
}
95+
96+
if (!maze[r][c]) {
97+
return;
98+
}
99+
100+
if (r < maze.length - 1) {
101+
pathRestrictions(p + 'D', maze, r+1, c);
102+
}
103+
104+
if (c < maze[0].length - 1) {
105+
pathRestrictions(p + 'R', maze, r, c+1);
106+
}
107+
}
108+
109+
}

‎lectures/14-recursion/code/src/com/kunal/strings/Dice.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.kunal.strings;
2+
3+
import java.util.ArrayList;
4+
5+
public class Dice {
6+
public static void main(String[] args) {
7+
dice("", 4);
8+
System.out.println(diceRet("", 4));
9+
}
10+
11+
static void dice(String p, int target) {
12+
if (target == 0) {
13+
System.out.println(p);
14+
return;
15+
}
16+
17+
for (int i = 1; i <= 6 && i <= target; i++) {
18+
dice(p + i, target - i);
19+
}
20+
}
21+
22+
static ArrayList<String> diceRet(String p, int target) {
23+
if (target == 0) {
24+
ArrayList<String> list = new ArrayList<>();
25+
list.add(p);
26+
return list;
27+
}
28+
ArrayList<String> list = new ArrayList<>();
29+
for (int i = 1; i <= 6 && i <= target; i++) {
30+
list.addAll(diceRet(p + i, target - i));
31+
}
32+
return list;
33+
}
34+
35+
static void diceFace(String p, int target, int face) {
36+
if (target == 0) {
37+
System.out.println(p);
38+
return;
39+
}
40+
41+
for (int i = 1; i <= face && i <= target; i++) {
42+
diceFace(p + i, target - i, face);
43+
}
44+
}
45+
46+
static ArrayList<String> diceFaceRet(String p, int target, int face) {
47+
if (target == 0) {
48+
ArrayList<String> list = new ArrayList<>();
49+
list.add(p);
50+
return list;
51+
}
52+
ArrayList<String> list = new ArrayList<>();
53+
for (int i = 1; i <= face && i <= target; i++) {
54+
list.addAll(diceFaceRet(p + i, target - i, face));
55+
}
56+
return list;
57+
}
58+
59+
}

0 commit comments

Comments
 (0)