Skip to content

Commit 9c883b7

Browse files
gouthampradhangouthampradhan
committed
Solved problems
1 parent 964f49e commit 9c883b7

11 files changed

Lines changed: 756 additions & 0 deletions

‎README.md‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,9 @@ My accepted leetcode solutions to some of the common interview problems.
4343
- [Employee Free Time](problems/src/array/EmployeeFreeTime.java) (Hard)
4444
- [Best Meeting Point](problems/src/array/BestMeetingPoint.java) (Hard)
4545
- [My Calendar III](problems/src/array/MyCalendarThree.java) (Hard)
46+
- [Champagne Tower](problems/src/array/ChampagneTower.java) (Medium)
47+
- [Valid Tic-Tac-Toe State](problems/src/array/ValidTicTacToeState.java) (Medium)
48+
- [Number of Subarrays with Bounded Maximum](problems/src/array/SubArraysWithBoundedMaximum.java) (Medium)
4649

4750
#### [Backtracking](problems/src/backtracking)
4851

@@ -116,6 +119,7 @@ My accepted leetcode solutions to some of the common interview problems.
116119
- [Bricks Falling When Hit](problems/src/depth_first_search/BricksFallingWhenHit.java) (Hard)
117120
- [Robot Room Cleaner](problems/src/depth_first_search/RobotRoomCleaner.java) (Hard)
118121
- [Cracking the Safe](problems/src/depth_first_search/CrackingTheSafe.java) (Hard)
122+
- [All Paths From Source to Target](problems/src/depth_first_search/AllPathsFromSourceToTarget.java) (Medium)
119123

120124
#### [Design](problems/src/design)
121125

@@ -188,6 +192,7 @@ My accepted leetcode solutions to some of the common interview problems.
188192
- [Cat and Mouse](problems/src/dynamic_programming/CatAndMouse.java) (Hard)
189193
- [Stone Game](problems/src/dynamic_programming/StoneGame.java) (Medium)
190194
- [Odd Even Jump](problems/src/dynamic_programming/OddEvenJump.java) (Hard)
195+
- [Profitable Schemes](problems/src/dynamic_programming/ProfitableSchemes.java) (Hard)
191196

192197

193198
#### [Greedy](problems/src/greedy)
@@ -225,6 +230,7 @@ My accepted leetcode solutions to some of the common interview problems.
225230
- [Meeting Rooms II](problems/src/heap/MeetingRoomsII.java) (Medium)
226231
- [Top K Frequent Words](problems/src/heap/TopKFrequentWords.java) (Medium)
227232
- [Candy](problems/src/heap/Candy.java) (Hard)
233+
- [Smallest Rotation with Highest Score](problems/src/heap/SmallestRotationWithHighestScore.java) (Hard)
228234

229235
#### [Linked List](problems/src/linked_list)
230236

@@ -301,6 +307,8 @@ My accepted leetcode solutions to some of the common interview problems.
301307
- [Shortest Palindrome](problems/src/string/ShortestPalindrome.java) (Hard)
302308
- [Valid Word Abbreviation](problems/src/string/ValidWordAbbreviation.java) (Easy)
303309
- [Longest Palindrome](problems/src/string/LongestPalindrome.java) (Easy)
310+
- [Replace Words](problems/src/string/ReplaceWords.java) (Medium)
311+
- [Rotate String](problems/src/string/RotateString.java) (Easy)
304312

305313
#### [Tree](problems/src/tree)
306314

@@ -361,4 +369,5 @@ My accepted leetcode solutions to some of the common interview problems.
361369
- [Minimum Window Substring](problems/src/two_pointers/MinimumWindowSubstring.java) (Hard)
362370
- [Smallest Range](problems/src/two_pointers/SmallestRange.java) (Hard)
363371
- [Subarray Product Less Than K](problems/src/two_pointers/SubarrayProductLessThanK.java) (Medium)
372+
- [Number of Matching Subsequences](problems/src/two_pointers/NumberOfMatchingSubsequences.java) (Medium)
364373

‎problems/src/array/ChampagneTower.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package array;
2+
3+
/**
4+
* Created by gouthamvidyapradhan on 28/03/2019
5+
* We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the
6+
* 100th row. Each glass holds one cup (250ml) of champagne.
7+
*
8+
* Then, some champagne is poured in the first glass at the top. When the top most glass is full, any excess liquid
9+
* poured will fall equally to the glass immediately to the left and right of it. When those glasses become full,
10+
* any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom
11+
* row has it's excess champagne fall on the floor.)
12+
*
13+
* For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are
14+
* poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two
15+
* cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row
16+
* has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.
17+
*
18+
*
19+
*
20+
* Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is
21+
* (both i and j are 0 indexed.)
22+
*
23+
*
24+
*
25+
* Example 1:
26+
* Input: poured = 1, query_glass = 1, query_row = 1
27+
* Output: 0.0
28+
* Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will
29+
* be no excess liquid so all the glasses under the top glass will remain empty.
30+
*
31+
* Example 2:
32+
* Input: poured = 2, query_glass = 1, query_row = 1
33+
* Output: 0.5
34+
* Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is
35+
* one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid
36+
* equally, and each will get half cup of champange.
37+
*
38+
*
39+
* Note:
40+
*
41+
* poured will be in the range of [0, 10 ^ 9].
42+
* query_glass and query_row will be in the range of [0, 99].
43+
*
44+
* Solution: Calculate for every glass and for each row at a time. Use the value from the previous row to calculate the
45+
* current value.
46+
* @see PascalsTriangle
47+
*/
48+
public class ChampagneTower {
49+
/**
50+
* Main method
51+
* @param args
52+
*/
53+
public static void main(String[] args) {
54+
System.out.println(new ChampagneTower().champagneTower(4, 2, 1));
55+
}
56+
57+
public double champagneTower(int poured, int query_row, int query_glass) {
58+
double[][] A = new double[query_row + 1][query_row + 1];
59+
A[0][0] = poured;
60+
for(int i = 1; i <= query_row; i ++){
61+
for(int j = 0; j <= query_row; j ++){
62+
if(A[i - 1][j] > 1.0){
63+
A[i][j] += (A[i - 1][j] - 1.0) / 2;
64+
}
65+
if(j == 0) continue;
66+
if(A[i - 1][j - 1] > 1.0){
67+
A[i][j] += (A[i - 1][j - 1] - 1.0) / 2;
68+
}
69+
}
70+
}
71+
if(A[query_row][query_glass] > 1.0) return 1;
72+
else return A[query_row][query_glass];
73+
}
74+
}

‎problems/src/array/SubArraysWithBoundedMaximum.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package array;
2+
3+
/**
4+
* Created by gouthamvidyapradhan on 29/03/2019
5+
* We are given an array A of positive integers, and two positive integers L and R (L <= R).
6+
*
7+
* Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that
8+
* subarray is at least L and at most R.
9+
*
10+
* Example :
11+
* Input:
12+
* A = [2, 1, 4, 3]
13+
* L = 2
14+
* R = 3
15+
* Output: 3
16+
* Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
17+
* Note:
18+
*
19+
* L, R and A[i] will be an integer in the range [0, 10^9].
20+
* The length of A will be in the range of [1, 50000].
21+
*/
22+
public class SubArraysWithBoundedMaximum {
23+
/**
24+
* Main method
25+
* @param args
26+
*/
27+
public static void main(String[] args) {
28+
int[] A = {2, 1, 4, 3};
29+
System.out.println(new SubArraysWithBoundedMaximum().numSubarrayBoundedMax(A, 2, 3));
30+
}
31+
32+
public int numSubarrayBoundedMax(int[] A, int L, int R) {
33+
int[] DP = new int[A.length];
34+
int v = -1;
35+
for(int i = A.length - 1; i >= 0; i --){
36+
if(A[i] >= L && A[i] <= R){
37+
if(v != -1){
38+
DP[i] = v - i + 1;
39+
} else {
40+
DP[i] = 1;
41+
v = i;
42+
}
43+
} else if(A[i] < L){
44+
if(v == -1){
45+
v = i;
46+
} if(i + 1 < A.length){
47+
if(A[i + 1] < L || (A[i + 1] >= L && A[i + 1] <= R)){
48+
DP[i] = DP[i + 1];
49+
} else {
50+
DP[i] = 0;
51+
}
52+
}
53+
} else {
54+
v = -1;
55+
}
56+
}
57+
int sum = 0;
58+
for(int i = 0; i < DP.length; i ++){
59+
sum += DP[i];
60+
}
61+
return sum;
62+
}
63+
}

‎problems/src/array/ValidTicTacToeState.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package array;
2+
3+
/**
4+
* Created by gouthamvidyapradhan on 29/03/2019
5+
* A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this
6+
* board position during the course of a valid tic-tac-toe game.
7+
*
8+
* The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty
9+
* square.
10+
*
11+
* Here are the rules of Tic-Tac-Toe:
12+
*
13+
* Players take turns placing characters into empty squares (" ").
14+
* The first player always places "X" characters, while the second player always places "O" characters.
15+
* "X" and "O" characters are always placed into empty squares, never filled ones.
16+
* The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
17+
* The game also ends if all squares are non-empty.
18+
* No more moves can be played if the game is over.
19+
* Example 1:
20+
* Input: board = ["O ", " ", " "]
21+
* Output: false
22+
* Explanation: The first player always plays "X".
23+
*
24+
* Example 2:
25+
* Input: board = ["XOX", " X ", " "]
26+
* Output: false
27+
* Explanation: Players take turns making moves.
28+
*
29+
* Example 3:
30+
* Input: board = ["XXX", " ", "OOO"]
31+
* Output: false
32+
*
33+
* Example 4:
34+
* Input: board = ["XOX", "O O", "XOX"]
35+
* Output: true
36+
* Note:
37+
*
38+
* board is a length-3 array of strings, where each string board[i] has length 3.
39+
* Each board[i][j] is a character in the set {" ", "X", "O"}.
40+
*
41+
* Solution: Do a brute-force check for each row, column and diagonals and keep track of count of 'X' and 'O'
42+
*/
43+
public class ValidTicTacToeState {
44+
/**
45+
* Main method
46+
* @param args
47+
*/
48+
public static void main(String[] args) {
49+
String[] board = {"XXX", "XOO", "OO "};
50+
System.out.println(new ValidTicTacToeState().validTicTacToe(board));
51+
}
52+
53+
public boolean validTicTacToe(String[] board) {
54+
boolean xWon = hasWon(board, 'X');
55+
boolean oWon = hasWon(board, 'O');
56+
int xcount = 0, ocount = 0;
57+
for(int i = 0; i < 3; i ++){
58+
for(int j = 0; j < 3; j ++){
59+
if(board[i].charAt(j) == 'X'){
60+
xcount++;
61+
}else if(board[i].charAt(j) == 'O'){
62+
ocount++;
63+
}
64+
}
65+
}
66+
if(xWon && oWon) return false;
67+
if(xWon){
68+
return ((xcount - 1 == ocount));
69+
} else if(oWon){
70+
return ((xcount == ocount));
71+
} else {
72+
return (xcount == ocount || xcount - 1 == ocount);
73+
}
74+
}
75+
76+
private boolean hasWon(String[] board, char c){
77+
boolean diagnol = ((board[0].charAt(0) == c && board[1].charAt(1) == c && board[2].charAt(2) == c) ||
78+
(board[0].charAt(2) == c && board[1].charAt(1) == c && board[2].charAt(0) == c));
79+
if(diagnol) return true;
80+
for(int i = 0; i < 3; i ++){
81+
if(board[i].charAt(0) == c && board[i].charAt(1) == c && board[i].charAt(2) == c) return true;
82+
}
83+
for(int i = 0; i < 3; i ++){
84+
if(board[0].charAt(i) == c && board[1].charAt(i) == c && board[2].charAt(i) == c) return true;
85+
}
86+
return false;
87+
}
88+
}

‎problems/src/depth_first_search/AllPathsFromSourceToTarget.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package depth_first_search;
2+
3+
import java.util.*;
4+
/**
5+
* Created by gouthamvidyapradhan on 28/03/2019
6+
* Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in
7+
* any order.
8+
*
9+
* The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for
10+
* which the edge (i, j) exists.
11+
*
12+
* Example:
13+
* Input: [[1,2], [3], [3], []]
14+
* Output: [[0,1,3],[0,2,3]]
15+
* Explanation: The graph looks like this:
16+
* 0--->1
17+
* | |
18+
* v v
19+
* 2--->3
20+
* There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
21+
* Note:
22+
*
23+
* The number of nodes in the graph will be in the range [2, 15].
24+
* You can print different paths in any order, but you should keep the order of nodes inside one path.
25+
*
26+
* Solution: Do a dfs to reach every path. Since its a DAG there can be no cycles and safe to proceed without
27+
* checking if the node has already been visited. Maintain a stack to keep track of the path and when a leaf node
28+
* has been reached add the elements in the stack to the result array
29+
*/
30+
public class AllPathsFromSourceToTarget {
31+
/**
32+
* Main method
33+
* @param args
34+
*/
35+
public static void main(String[] args) {
36+
int[][] graph = {{1, 2}, {3}, {3}, {}};
37+
System.out.println(new AllPathsFromSourceToTarget().allPathsSourceTarget(graph));
38+
}
39+
40+
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
41+
Set<Integer> done = new HashSet<>();
42+
Stack<Integer> stack = new Stack<>();
43+
List<List<Integer>> result = new ArrayList<>();
44+
dfs(result, done, 0, stack, graph);
45+
return result;
46+
}
47+
48+
private void dfs(List<List<Integer>> result, Set<Integer> done, int i, Stack<Integer> stack, int[][] graph){
49+
done.add(i);
50+
stack.push(i);
51+
int[] children = graph[i];
52+
if(children.length == 0){
53+
List<Integer> childList = new ArrayList<>(stack);
54+
result.add(childList);
55+
} else{
56+
for(int c : children){
57+
dfs(result, done, c, stack, graph);
58+
}
59+
}
60+
stack.pop();
61+
done.remove(i);
62+
}
63+
}

0 commit comments

Comments
 (0)