8000 add personal leetcode solutions · llluis/best-leetcode-resources@aad463a · GitHub
[go: up one dir, main page]
Skip to content

Commit aad463a

Browse files
armankhondkerarmankhondker
committed
add personal leetcode solutions
1 parent 9ae7025 commit aad463a

File tree

311 files changed

+18979
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

311 files changed

+18979
-0
lines changed

‎leetcode-solutions/.DS_Store

32 KB
Binary file not shown.

‎leetcode-solutions/01Matrix.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
// Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
2+
3+
// The distance between two adjacent cells is 1.
4+
5+
//run BFS on the grid
6+
//TC: O(n)
7+
//SC: O(n)
8+
9+
class Solution {
10+
public int[][] updateMatrix(int[][] matrix) {
11+
int m = matrix.length;
12+
int n = matrix[0].length;
13+
14+
Queue<int[]> queue = new LinkedList<>();
15+
for (int i = 0; i < m; i++) {
16+
for (int j = 0; j < n; j++) {
17+
if (matrix[i][j] == 0) {
18+
queue.offer(new int[] {i, j});
19+
}
20+
else {
21+
matrix[i][j] = Integer.MAX_VALUE;
22+
}
23+
}
24+
}
25+
26+
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
27+
28+
while (!queue.isEmpty()) {
29+
int[] cell = queue.poll();
30+
for (int[] d : dirs) {
31+
int r = cell[0] + d[0];
32+
int c = cell[1] + d[1];
33+
if (r < 0 || r >= m || c < 0 || c >= n ||
34+
matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
35+
queue.add(new int[] {r, c});
36+
matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
37+
}
38+
}
39+
40+
return matrix;
41+
}
42+
}

‎leetcode-solutions/132pattern.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k
2+
and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132
3+
pattern in the list.
4+
5+
// Time complexity : O(n). We travesre over the numsnums array of size nn once to fill the minmin array. After this,
6+
// we traverse over numsnums to find the nums[k]nums[k]. During this process, we also push and pop the elements
7+
// on the stackstack. But, we can note that atmost nn elements can be pushed and popped off the stackstack in total.
8+
// Thus, the second traversal requires only O(n) time.
9+
10+
// Space complexity : O(n). The stackstack can grow upto a maximum depth of nn. Furhter, minmin array of size n is used.
11+
12+
class Solution {
13+
public boolean find132pattern(int[] nums) {
14+
if (nums.length < 3)
15+
return false;
16+
Stack < Integer > stack = new Stack < > ();
17+
int[] min = new int[nums.length]; //array to store the minimum elements
18+
min[0] = nums[0];
19+
for (int i = 1; i < nums.length; i++)
20+
min[i] = Math.min(min[i - 1], nums[i]); //populate min array
21+
22+
//fix j
23+
for (int j = nums.length - 1; j >= 0; j--) {
24+
if (nums[j] > min[j]) { //we have found an i, j pair!
25+
while (!stack.isEmpty() && stack.peek() <= min[j]) //pop elements of stack that arent greater than min[j] or the k element
26+
stack.pop();
27+
if (!stack.isEmpty() && stack.peek() < nums[j]) //we have found i,j,k pair
28+
return true;
29+
stack.push(nums[j]);
30+
}
31+
}
32+
return false;
33+
}
34+
}

‎leetcode-solutions/3Sum.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
2+
// Find all unique triplets in the array which gives the sum of zero.
3+
4+
//Intution is to fix the element we are on, and perform TWO SUM on remaining of array to see if we get 0-nums[i],
5+
//WE DO TWO SUM USING TWO POINTERS,
6+
//if we do, then have found a pair i,j,k which add up to 0.
7+
8+
//TC: O(n^2)
9+
//SC: O(n) for memory required for sorting, DONT COUNT O(n^2) space for the output
10+
11+
1. SORT THE INPUT Array
12+
2. FOR LOOP, where you PIN one element, and implement logic to avoid duplicates
13+
3. USE TWO POINTERS, with low and high, to try and find elements that equal, the target which is 0 - pinVALUE
14+
4. If we find a pair append to res, then return
15+
16+
class Solution {
17+
public List<List<Integer>> threeSum(int[] nums) {
18+
Arrays.sort(num); //sort the array so that we can use two pointer with two sum
19+
List<List<Integer>> res = new LinkedList<>();
20+
for (int i = 0; i < num.length-2; i++) {
21+
if (i == 0 || (i > 0 && num[i] != num[i-1])) { //to not get duplicates, we have a good element where we can try to find a pair
22+
int lo = i+1, hi = num.length-1, //MOVE THESE BOUNDS INWARDS
23+
int sum = 0 - num[i]; //this is the value we are trying to get with two sum on rest of array
24+
while (lo < hi) {
25+
if (num[lo] + num[hi] == sum) {
26+
res.add(Arrays.asList(num[i], num[lo], num[hi]));
27+
while (lo < hi && num[lo] == num[lo+1]) lo++; //increment here to avoid duplicates
28+
while (lo < hi && num[hi] == num[hi-1]) hi--; //increment here to avoid dupliactes
29+
lo++; hi--;
30+
} else if (num[lo] + num[hi] < sum) lo++; //we need to increment low
31+
else {hi--;} //increment hi
32+
}
33+
}
34+
}
35+
return res;
36+
}
37+
}

‎leetcode-solutions/3sumClosest.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// Given an array nums of n integers and an integer target, find three integers in nums such that
2+
// the sum is closest to target. Return the sum of the three integers. You may assume that each input
3+
// would have exactly one solution.
4+
5+
6+
//TC: O(n^2)
7+
//SC: O(1)
8+
9+
// Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element.
10+
// If the sum is less than target, it means we have to add a larger element so next element move to the next.
11+
// If the sum is greater, it means we have to add a smaller element so last element move to the second last element.
12+
// Keep doing this until the end. Each time compare the difference between sum and target, if it is less than
13+
// minimum difference so far, then replace result with it, otherwise keep iterating.
14+
15+
class Solution {
16+
public int threeSumClosest(int[] nums, int target) {
17+
int result = num[0] + num[1] + num[num.length - 1]; //initialize result to some value, dont do this
18+
// after sorting cuz will effectively get minimum elements
19+
Arrays.sort(num); //O(nlogn) time to sort
20+
for (int i = 0; i < num.length - 2; i++) {
21+
int start = i + 1, end = num.length - 1;
22+
while (start < end) {
23+
int sum = num[i] + num[start] + num[end];
24+
if (sum > target) {
25+
end--;
26+
} else {
27+
start++;
28+
}
29+
if (Math.abs(sum - target) < Math.abs(result - target)) {
30+
result = sum;
31+
}
32+
}
33+
}
34+
return result;
35+
}
36+
}

‎leetcode-solutions/AddAndSearchWordDataStructureDesign.java

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
Design a data structure that supports the following two operations:
2+
3+
void addWord(word)
4+
bool search(word)
5+
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A .
6+
means it can represent any one letter.
7+
8+
Example:
9+
10+
addWord("bad")
11+
addWord("dad")
12+
addWord("mad")
13+
search("pad") -> false
14+
search("bad") -> true
15+
search(".ad") -> true
16+
search("b..") -> true
17+
18+
19+
INTUITION, build a trie data strucutre!!
20+
21+
FOR ADD, just loop through all of the trie starting from root, if that current char isnt in trie,
22+
create a new trienode, once we reach last char, set the isWord field to true
23+
24+
FOR SEARCH, use a helper function that we call on if we reach a *, so we can iterate on rest of string
25+
26+
27+
//TC: ADD O(N) where is n is length of word, SEARCH O(M) where m is the total number of chars in trie
28+
//SC: ADD O(N) because we may have to allocate n new nodes for newly inserted word,
29+
// SEARCH O(M) stack space for recurisve calls
30+
31+
class WordDictionary {
32+
class Node{
33+
Node[] dict;
34+
boolean isWord;
35+
public Node() {
36+
dict = new Node[26];
37+
isWord = false;
38+
}
39+
}
40+
Node root;
41+
/** Initialize your data structure here. */
42+
public WordDictionary() { //O(1) O(1)
43+
root = new Node();
44+
}
45+
46+
/** Adds a word into the data structure. */
47+
public void addWord(String word) { //O(len) O(26 * len)
48+
Node cur = root;
49+
for (char c : word.toCharArray()) {
50+
int i = c - 'a';
51+
if (cur.dict[i] == null) cur.dict[i] = new Node();
52+
cur = cur.dict[i];
53+
}
54+
cur.isWord = true;
55+
}
56+
57+
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
58+
public boolean search(String word) {
59+
return search(root, word);
60+
}
61+
private boolean search(Node root, String word) { // O(26^len)
62+
if (word.length() == 0) return root.isWord;
63+
Node cur = root;
64+
for (int i = 0; i < word.length(); i++) { // len
65+
char c = word.charAt(i);
66+
if (c == '.') {
67+
for (int j = 0; j < 26; j++) { //
68+
if (cur.dict[j] != null && search(cur.dict[j], word.substring(i + 1))) return true;
69+
}
70+
return false;
71+
}
72+
int ii = c - 'a';
73+
if (cur.dict[ii] == null) return false;
74+
cur = cur.dict[ii];
75+
}
76+
return cur.isWord;
77+
}
78+
}

‎leetcode-solutions/AddTwoNumbersLL.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2+
3+
//TC: O(N) to go throguh the length of the longest LL
4+
//SC: O(1)
5+
6+
class Solution {
7+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
8+
if(l1 == null || l2 == null) return null;
9+
ListNode dummy = new ListNode(-1);
10+
ListNode curr = dummy;
11+
int carry =0;
12+
while(l1 != null || l2!=null){
13+
int total = 0;
14+
if(l1!=null){
15+
total+=l1.val;
16+
l1=l1.next;
17+
}
18+
if(l2!=null){
19+
total+=l2.val;
20+
l2=l2.next;
21+
}
22+
total+=carry;
23+
24+
curr.next = new ListNode(total%10);
25+
carry=total/10;
26+
curr = curr.next;
27+
}
28+
if(carry > 0){
29+
curr.next = new ListNode(carry);
30+
}
31+
32+
return dummy.next;
33+
}
34+
}

0 commit comments

Comments
 (0)
0