Skip to content

Commit da7cf0d

Browse files
CHAUDHARY ShikharCHAUDHARY Shikhar
CHAUDHARY Shikhar
authored and
CHAUDHARY Shikhar
committed
Added medium problems
1 parent 0397a43 commit da7cf0d

10 files changed

+638
-0
lines changed

‎Medium/BreadthFirstSearch.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package AlgoExpert_Medium;
2+
import java.util.ArrayList ;
3+
import java.util.List;
4+
5+
public class BreadthFirstSearch {
6+
7+
static class Node {
8+
String name;
9+
List<Node> children = new ArrayList<Node>();
10+
11+
public Node(String name) {
12+
this.name = name;
13+
}
14+
15+
public List<String> breadthFirstSearch(List<String> array) { // bfs starting at this node.
16+
// Write your code here.
17+
return null;
18+
}
19+
20+
public Node addChild(String name) {
21+
Node child = new Node(name);
22+
children.add(child);
23+
return this;
24+
}
25+
}
26+
27+
}

‎Medium/Kadane.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package AlgoExpert_Medium;
2+
3+
public class Kadane {
4+
public static void main(String[] args) {
5+
6+
}
7+
8+
public static int kadanesAlgorithm(int[] array) {
9+
10+
int[] solution = array.clone();
11+
12+
int max = solution[0];
13+
14+
for(int i=1 ; i<array.length ; i++ ) {
15+
16+
if( solution[i-1] > 0 ) // only want this if there is a positive change from previous subproblem.
17+
solution[i] = array[i] + solution[i-1];
18+
else
19+
solution[i] = array[i];
20+
21+
if(max < solution[i])
22+
max = solution[i] ;
23+
}
24+
25+
return max;
26+
}
27+
28+
29+
// If arr[i] is +ve or -ve, then having solution[i-1] as positive will improve the answer.
30+
// If solution[i-1] is -ve then solution[i-1] will worsen the sum, so we take array[i]
31+
32+
33+
// We can also solve it using O(1) space and O(n) time
34+
public static int kadane(int[] array) {
35+
36+
int maxEndingHere = array[0];
37+
int maxSoFar = array[0] ;
38+
39+
for(int i=1; i< array.length ; i++) {
40+
int num = array[i];
41+
maxEndingHere = Math.max(num, maxEndingHere + num) ;
42+
maxSoFar = Math.max(maxSoFar, maxEndingHere) ;
43+
}
44+
45+
return maxSoFar;
46+
47+
}
48+
49+
}
50+
51+
52+
53+
54+
55+
56+
57+

‎Medium/LongestPeak.java

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package AlgoExpert_Medium;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class LongestPeak {
7+
8+
public static void main(String[] args) {
9+
10+
int[] array = { 1, 2, 3, 3, 4, 0, 10, 6, 5, -1, -3, 2 } ;
11+
12+
System.out.println(longestPeak(array));
13+
}
14+
15+
public static int longestPeak(int[] array) {
16+
17+
int max = 0 ;
18+
int currentLength = 0;
19+
20+
List<Integer> list = new ArrayList<>() ;
21+
22+
23+
for ( int i=0 ; i<array.length-1 ; i++ ) {
24+
25+
System.out.println("List is : " + list );
26+
27+
if(array[i] < array[i+1] ) {
28+
29+
if( list.isEmpty() ) { // Corner Case: When filling the list first time.
30+
currentLength = currentLength+2 ;
31+
list.add(array[i]) ;
32+
list.add(array[i+1]);
33+
34+
}
35+
else {
36+
currentLength++ ;
37+
list.add(array[i+1]);
38+
}
39+
40+
} else if(array[i] > array[i+1]) { // 4 > 0
41+
42+
// Peak will be found here. So, we set max in this else if.
43+
44+
if(currentLength > 1 ) { // Now look for strictly decreasing
45+
46+
currentLength++;
47+
list.add(array[i+1]) ;
48+
49+
for (int j=i+1 ; j<array.length-1; j++) {
50+
51+
if(array[j+1] < array[j] ) {
52+
currentLength++;
53+
list.add(array[j+1]) ;
54+
} else {
55+
i= j-1; // for optimization
56+
break;
57+
}
58+
59+
}
60+
61+
if( currentLength > max ) {
62+
max = currentLength;
63+
}
64+
65+
66+
}
67+
68+
System.out.println("Peak numbers are : " + list);
69+
70+
currentLength = 0;
71+
72+
list = new ArrayList<Integer>() ;
73+
74+
} else {
75+
currentLength = 0;
76+
list = new ArrayList<Integer>() ;
77+
}
78+
79+
}
80+
81+
return max;
82+
}
83+
84+
public static int peak(int[] array) {
85+
86+
return 1;
87+
}
88+
89+
}

‎Medium/MaxSubsetSumNoAdjacent.java

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package AlgoExpert_Medium;
2+
3+
public class MaxSubsetSumNoAdjacent {
4+
5+
public static void main(String[] args) {
6+
7+
int[] array = { 75, 105, 120, 75, 95, 135} ; // array of +ve integers.
8+
9+
System.out.println( maxSubsetSumNoAdjacent(array) );
10+
11+
}
12+
13+
// Maximum sum of non-adjacent elements in the array.
14+
15+
public static int maxSubsetSumNoAdjacent(int[] array) { // bottom up.
16+
17+
int[] solution = new int[array.length] ; // This approach takes O(n^2)
18+
19+
solution[0] = array[0];
20+
21+
for(int i=1 ; i< array.length; i++ ) {
22+
23+
for( int j=i-2 ; j >=0 ; j-- ) {
24+
solution[i] = Math.max(array[i], solution[j] + array[i]) ;
25+
}
26+
27+
solution[i] = Math.max(solution[i] , solution[i-1]) ;
28+
29+
}
30+
31+
for(int i=0 ; i<solution.length ; i++) {
32+
System.out.println("solution["+ i + "] : " + solution[i]);
33+
}
34+
35+
return solution[array.length-1] ;
36+
37+
}
38+
39+
// In top down, fill the cache initially with the array elements.
40+
41+
public static int maxSubsetSumNoAdjacent2(int[] array) { // O(n)
42+
43+
if( array.length == 0 ) {
44+
return 0 ;
45+
} else if (array.length == 1) {
46+
return array[0];
47+
}
48+
49+
int[] solution = array.clone(); // Can solve this in O(n) if all the elements of the array are positive.
50+
51+
solution[1] = Math.max(array[0], array[1]) ;
52+
53+
for(int i=2 ; i< array.length; i++ ) {
54+
55+
solution[i] = Math.max(solution[i-1], solution[i-2] + array[i]) ;
56+
57+
// Important case.
58+
}
59+
60+
61+
return solution[array.length-1] ;
62+
}
63+
64+
// Can also solve this in O(1) space.
65+
public static int maxSubsetSumNoAdjacentO1Space(int[] array) {
66+
67+
if( array.length == 0 ) {
68+
return 0 ;
69+
} else if (array.length == 1) {
70+
return array[0];
71+
}
72+
73+
int second = array[0];
74+
int first = Math.max(array[0], array[1]) ;
75+
76+
for(int i=2 ; i< array.length; i++ ) {
77+
78+
int current = Math.max(second + array[i], first ) ;
79+
second = first ;
80+
first = current;
81+
82+
}
83+
84+
return first ;
85+
}
86+
87+
88+
89+
90+
// If the numbers are also negative, then we will need to add solution[i] in the max() function as well.
91+
92+
93+
}

‎Medium/MinEditDistance.java

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
package AlgoExpert_Medium;
2+
3+
public class MinEditDistance {
4+
public static void main(String[] args) {
5+
6+
String s1 = "abc" ;
7+
String s2 = "yabd" ;
8+
9+
System.out.println(levenshteinDistance(s1, s2));
10+
11+
}
12+
13+
public static int levenshteinDistance(String str1, String str2) {
14+
15+
int[][] solution = new int[str1.length()+1][str2.length()+1] ;
16+
17+
for(int i=0 ; i < str2.length()+1 ; i++ ) {
18+
solution[0][i] = i ;
19+
}
20+
21+
for(int i=0 ; i < str1.length()+1 ; i++ ) {
22+
solution[i][0] = i ;
23+
}
24+
25+
return levenshteinDistance(str1, str2, solution) ;
26+
27+
}
28+
29+
public static int levenshteinDistance(String str1, String str2, int[][] solution){
30+
31+
for(int i=1 ; i<str1.length()+1 ; i++ ) {
32+
33+
for(int j=1; j<str2.length()+1 ; j++) {
34+
35+
if(str1.charAt(i-1) == str2.charAt(j-1) ) {
36+
solution[i][j] = solution[i-1][j-1] ;
37+
} else {
38+
solution[i][j] = 1+ Math.min( solution[i][j-1] ,Math.min(solution[i-1][j-1], solution[i-1][j]) );
39+
}
40+
}
41+
}
42+
43+
return solution[str1.length()][str2.length()];
44+
45+
}
46+
47+
public static int ld (String str1, String str2){ // Can solve this in O(min(m, n)) space.
48+
49+
// See the AlgoExpert video solution.
50+
51+
String small = str1.length() < str2.length() ? str1 : str2 ;
52+
53+
String big = str1.length() >= str2.length() ? str1 : str2;
54+
55+
int[] evenEdits = new int[small.length()+1] ;
56+
int[] oddEdits = new int[small.length()+1];
57+
58+
for(int j=0; j<small.length()+1 ; j++) {
59+
evenEdits[j] = j ;
60+
}
61+
62+
int[] currentEdits;
63+
int[] previousEdits;
64+
65+
for (int i=1; i<big.length()+1 ; i++) { // O(mn) time, O(min(n, m)) space.
66+
67+
if(i%2 == 1) {
68+
currentEdits = oddEdits;
69+
previousEdits = evenEdits;
70+
} else {
71+
currentEdits = evenEdits;
72+
previousEdits = oddEdits;
73+
}
74+
75+
currentEdits[0] = i;
76+
77+
for( int j=1 ; j<small.length()+1 ; j++ ) {
78+
79+
if(big.charAt(i-1) == small.charAt(j-1) ) {
80+
currentEdits[j] = previousEdits[j-1] ;
81+
} else {
82+
currentEdits[j] = 1 + Math.min(previousEdits[j-1],
83+
Math.min(previousEdits[j], currentEdits[j-1] ) ) ;
84+
}
85+
}
86+
}
87+
88+
return big.length() % 2 == 0 ? evenEdits[small.length()] : oddEdits[small.length()] ;
89+
90+
}
91+
92+
93+
94+
95+
}
96+
97+
98+
99+
100+
101+
102+
103+
104+

0 commit comments

Comments
 (0)