Skip to content

Commit db62f4d

Browse files
15-Ab15-Ab
committed
2023 august
1 parent bf05f2a commit db62f4d

7 files changed

+370
-0
lines changed

‎2023 August/Daily 01-08-23.md

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Little change the Subset problem ( 78 )
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
Simply extract subsets of length 'k' after finding all subsets of[ 1, 2, ... , n]
8+
9+
To find all subsets :
10+
( 78. Subsets : https://leetcode.com/problems/subsets/solutions/3740278/78-subsets-simple-intuition/ )
11+
12+
Just attach the current number to every single subsets created before.
13+
14+
nums = [1, 2, 3, 4]
15+
subsets
16+
[
17+
[ ] ,
18+
[ 1 ] ,
19+
[ 2 ] , [ 1, 2 ] ,
20+
[ 3 ] , [ 1, 3 ] , [ 2, 3 ], [ 1, 2, 3 ] ,
21+
[ 4 ] , [ 1, 4 ] , [ 2, 4 ] , [ 1, 2, 4 ] , [ 3, 4 ] , [ 1, 3, 4 ] , [ 2, 3, 4 ] , [ 1, 2, 3, 4 ]
22+
]
23+
24+
After extracting of '2' length :
25+
26+
[ 1, 2 ] , [ 1, 3 ] , [ 2, 3 ] , [ 1, 4 ] , [ 2, 4 ] , [ 3, 4 ]
27+
28+
29+
Have a look at the code , still have any confusion then please let me know in the comments
30+
Keep Solving.:)
31+
32+
33+
# Complexity
34+
- Time complexity : $$O(n^2)$$
35+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
36+
37+
- Space complexity:
38+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
39+
40+
# Code
41+
```
42+
class Solution {
43+
public List<List<Integer>> combine(int n, int k) {
44+
List<List<Integer>> ans = new ArrayList<>(); // to store answer of list of length 'k'
45+
List<List<Integer>> li = new ArrayList<>(); // to store all subsets
46+
List<Integer> t = new ArrayList<>();
47+
li.add( t);
48+
49+
int s = li.size();
50+
for( int i = 1; i <= n; i++){
51+
for( int j = 0; j < s; j++){
52+
List<Integer> tl = new ArrayList<>(li.get(j));
53+
tl.add( i);
54+
//System.out.println( tl.toString());
55+
if( tl.size() == k){ // if current formed subset is of length 'k' then add to answer list
56+
ans.add( tl);
57+
}
58+
59+
li.add( tl);
60+
}
61+
s = li.size();
62+
}
63+
//System.out.println( li.toString()); // to print all subsets
64+
return ans;
65+
}
66+
}
67+
```

‎2023 August/Daily 02-08-23.md

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Applying unitary method of doing permutations in code way.
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
8+
Permutations basically means arrangements, so when we permute we keep a record of what we have already included and look for various ways to arrange the numbers.
9+
10+
Same here :
11+
- I have considered all numbers of the given array as starting number one-by-one
12+
- In next step include next number but not that one which is already included in that way
13+
- Keep iterating till our way reach the array size
14+
- Add that way to answer
15+
- Now step back and explore other numbers
16+
- All this will happen recursively
17+
18+
19+
20+
21+
22+
Have a look at the code , still have any confusion then please let me know in the comments
23+
Keep Solving.:)
24+
# Complexity
25+
- Time complexity : $$O(n*n!)$$
26+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
27+
28+
- Space complexity : $$O(n*n!)$$
29+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
30+
31+
# Code
32+
```
33+
class Solution {
34+
public List<List<Integer>> permute(int[] nums) {
35+
36+
List<List<Integer>> a = new ArrayList<>();
37+
recursepermute( nums, new boolean[nums.length], new ArrayList<>(), a);
38+
return a;
39+
}
40+
41+
static void recursepermute( int[] nums, boolean[] included, List<Integer> way, List<List<Integer>> a){
42+
43+
if( way.size() == nums.length){
44+
a.add( new ArrayList<>( way ) );
45+
return;
46+
}
47+
48+
for( int i = 0; i < nums.length; i++){
49+
if( included[i] ){ // if that number is already included in our that way , then look for next numbers
50+
continue;
51+
}
52+
way.add( nums[i]); // if not , then add to our way
53+
included[i] = true;
54+
recursepermute( nums, included, way, a); // now recurse until our way size equals desired array size
55+
way.remove( way.size() - 1 ); // remove last numbers to look for another way
56+
included[i] = false;
57+
}
58+
}
59+
}
60+
```

‎2023 August/Daily 03-08-23 Iterative Approach.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Can be solved by using Unitary method , keep a char in hand and add one-by-one .
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
This approach is iterative and similar to Permutations(46) : https://leetcode.com/problems/permutations/solutions/3851382/daily-02-08-23/
8+
9+
- iterate for all digits present in digits string
10+
- a temporary list of string that will get modified after each iteration
11+
- for every string present in answer list add characters of currently iterated digit
12+
- change the answer list to currently updated answer list
13+
---
14+
Have a look at the code , still have any confusion then please let me know in the comments
15+
Keep Solving.:)
16+
17+
---
18+
Recursive Approach : https://leetcode.com/problems/letter-combinations-of-a-phone-number/solutions/3857876/recursive-approach-daily-03-08-23/
19+
20+
# Complexity
21+
- Time complexity : $$O(n*4^n)$$
22+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
23+
24+
- Space complexity : $$O(4^n)$$
25+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
26+
27+
# Code
28+
```
29+
class Solution {
30+
public List<String> letterCombinations(String digits) { // recursive approach : similar to permutations 46
31+
if (digits.isEmpty()){
32+
return new ArrayList<>();
33+
}
34+
35+
List<String> ans = new ArrayList<>();
36+
ans.add( ""); // initialise answer list as empty string
37+
38+
String[] numTochar = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; // it stores the keypad in array form
39+
// each index correponds to respective possible characters
40+
41+
for( char s : digits.toCharArray() ){ // iterate for all digits present in digits string
42+
List<String> a = new ArrayList<>(); // a temporary list of string that will get modified after each iteration
43+
for( String p : ans){ // for every string present in answer list ...
44+
for( char n : numTochar[ s - '0'].toCharArray() ){ // ... add characters of currently iterated digit
45+
a.add( p + n);
46+
}
47+
}
48+
ans = a; // update the answer list to currently updated answers
49+
}
50+
return ans;
51+
}
52+
}
53+
```

‎2023 August/Daily 03-08-23 Recursive Approach.md

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Tried to solve by using permutations
4+
( https://leetcode.com/problems/permutations/solutions/3851382/daily-02-08-23/ )
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
Stored the first characters that will be generated by first digit of 'digits' string : then keep repeating the same fashion on rest of the characters present in 'digits' string
8+
9+
10+
- I have considered all characters of the given digits as starting number one-by-one
11+
- In next step include next digit which is in the digits string
12+
- Keep iterating till our string reach the given digit size
13+
- Add that way to answer
14+
- Now step back and explore other numbers
15+
- All this will happen recursively
16+
---
17+
18+
Have a look at the code , still have any confusion then please let me know in the comments
19+
Keep Solving.:)
20+
21+
>
22+
Unitary/Iterative Approach : https://leetcode.com/problems/letter-combinations-of-a-phone-number/solutions/3857796/iterative-approach-daily-03-08-23/ ---
23+
24+
25+
# Complexity
26+
- Time complexity : $$O(n*4^n)$$
27+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
28+
29+
- Space complexity : $$O(4^n)$$
30+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
31+
32+
# Code
33+
```
34+
class Solution {
35+
public List<String> letterCombinations(String digits) {
36+
37+
if( digits.isEmpty() ){
38+
return new ArrayList<>();
39+
}
40+
List<String> ans = new ArrayList<>();
41+
recurseLetterCombine( digits, 0, new StringBuilder(), ans);
42+
return ans;
43+
}
44+
45+
static String[] digitTochar = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; // it stores the keypad in array form
46+
// each index correponds to respective possible characters
47+
48+
static void recurseLetterCombine( String digits, int i, StringBuilder s, List<String> ans){
49+
50+
if( i == digits.length() ){ // when size reached then add to answer
51+
ans.add( s.toString() );
52+
return;
53+
}
54+
for( char c : digitTochar[ digits.charAt(i) - '0' ].toCharArray() ){ // initially start from first digit : so i = 0
55+
s.append( c); // add current char to build string
56+
recurseLetterCombine( digits, i + 1, s, ans); // now recurse until our typed characters size equals desired digit size
57+
s.deleteCharAt( s.length() - 1); // remove last character(way) to look for another way
58+
}
59+
}
60+
61+
62+
}
63+
```

‎2023 August/Daily 04-08-23.md

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Recursion again came ( consecutive third day in daily )
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
Solve by recursive approach similar to permutations(46) and Letter Combination of Phone Number(17).
8+
9+
---
10+
11+
Have a look at the code , still have any confusion then please let me know in the comments
12+
Keep Solving.:)
13+
# Complexity
14+
- Time complexity : $$O(n^3)$$
15+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
16+
17+
- Space complexity : $$O(n^2 + |wordDict|)$$
18+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
19+
20+
# Code
21+
```
22+
class Solution {
23+
static boolean wordBreak(String s, List<String> wordDict){
24+
25+
return recurseWordBreak( s, 0, new HashSet<>( wordDict) ,new Boolean[ s.length() ] );
26+
27+
}
28+
29+
static boolean recurseWordBreak( String s, int i, Set<String> Dict , Boolean[] record){
30+
31+
if( i == s.length() ){
32+
return true;
33+
}
34+
if( record[i] != null){
35+
return record[i];
36+
}
37+
38+
for( int j = i ; j < s.length(); j++){
39+
if( Dict.contains( s.substring(i, j+1) ) && recurseWordBreak( s, j+1, Dict, record) ){
40+
return record[i] = true;
41+
}
42+
}
43+
return record[i] = false;
44+
}
45+
}
46+
```

‎2023 August/Daily 16-08-23.md

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Deque properties of letting operations at both start and end will help.
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
Find maximum of each window and add to answer array.
8+
9+
- Keep an array to store maximum numbers of each window
10+
- Keep a deque to maintain the sliding window
11+
- - if next number is greater than previous then no need of previous one
12+
- - maintain window size length 'k'
13+
- - after reaching 'k' numbers start adding to answer array
14+
15+
---
16+
17+
Have a look at the code , still have any confusion then please let me know in the comments
18+
Keep Solving.:)
19+
20+
# Complexity
21+
- Time complexity : $$O(n)$$
22+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
23+
24+
- Space complexity : $$O(n)$$
25+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
26+
27+
# Code
28+
```
29+
class Solution {
30+
public int[] maxSlidingWindow(int[] nums, int k) {
31+
int[] a = new int[ nums.length - k + 1]; // to store maximum numbers of each window
32+
Deque<Integer> dq = new ArrayDeque<>(); // to maintain the sliding window
33+
34+
for( int i = 0; i < nums.length; i++){
35+
while( !dq.isEmpty() && dq.peekLast() < nums[i] ){ // if next number is greater than previous then no need of previous one
36+
dq.pollLast();
37+
}
38+
dq.offerLast( nums[i] );
39+
if( i >= k && nums[i-k] == dq.peekFirst()){ // maintain window size length 'k'
40+
dq.pollFirst();
41+
}
42+
if( i >= k - 1){ // after reaching 'k' numbers start adding to answer array
43+
a[i-k+1] = dq.peekFirst();
44+
//System.out.print( a[i-k+1] + " ");
45+
}
46+
}
47+
return a;
48+
}
49+
}
50+
```

‎2023 August/Daily 21-08-23.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
# Intuition
2+
<!-- Describe your first thoughts on how to solve this problem. -->
3+
Whether by hit-n-trial or any other means, this method was developed.
4+
5+
# Approach
6+
<!-- Describe your approach to solving the problem. -->
7+
- Let a new string which is just two original string joined end-to-end.
8+
- Remove first and last element of new string.
9+
- If after removal, original string can be viewed in that, then returns true.
10+
- Otherwise, false
11+
12+
---
13+
Have a look at the code , still have any confusion then please let me know in the comments
14+
Keep Solving.:)
15+
16+
# Complexity
17+
- Time complexity : $$O(n^2)$$
18+
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
19+
20+
- Space complexity : $$O(n)$$
21+
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
22+
23+
# Code
24+
```
25+
class Solution {
26+
public boolean repeatedSubstringPattern(String s) {
27+
String ss = s + s;
28+
return ss.substring(1, ss.length() - 1).contains(s);
29+
}
30+
}
31+
```

0 commit comments

Comments
 (0)