Skip to content

Commit 7ae411a

Browse files
varunu28varunu28
committed
Solved sliding window problems
1 parent 57abe7f commit 7ae411a

File tree

4 files changed

+165
-8
lines changed

4 files changed

+165
-8
lines changed

‎Contests/Weekly Contest 104/Word Subsets.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
class Solution {
2+
public static List<String> wordSubsets(String[] A, String[] B) {
3+
Map<String, Map<Character, Integer>> map1 = getMap(A);
4+
5+
Map<Character, Integer> map2 = new HashMap<>();
6+
for (String s : B) {
7+
Map<Character, Integer> temp = new HashMap<>();
8+
char[] tempChar = s.toCharArray();
9+
10+
for (char c : tempChar) {
11+
temp.put(c, temp.getOrDefault(c, 0) + 1);
12+
}
13+
14+
for (Map.Entry<Character, Integer> entry : temp.entrySet()) {
15+
int val1 = entry.getValue();
16+
int val2 = map2.getOrDefault(entry.getKey(), 0);
17+
18+
map2.put(entry.getKey(), Math.max(val1, val2));
19+
}
20+
}
21+
22+
List<String> ans = new ArrayList<>();
23+
24+
for (String s : A) {
25+
boolean flag = true;
26+
Map<Character, Integer> temp2 = map1.get(s);
27+
28+
for (Map.Entry<Character, Integer> entry : map2.entrySet()) {
29+
if (!(temp2.containsKey(entry.getKey()) && temp2.get(entry.getKey()) >= entry.getValue())) {
30+
flag = false;
31+
break;
32+
}
33+
}
34+
35+
if (flag) {
36+
ans.add(s);
37+
}
38+
}
39+
40+
return ans;
41+
}
42+
43+
private static Map<String, Map<Character, Integer>> getMap(String[] A) {
44+
Map<String, Map<Character, Integer>> map = new HashMap<>();
45+
46+
for (String a : A) {
47+
char[] arr = a.toCharArray();
48+
Map<Character, Integer> charMap = new HashMap<>();
49+
for (char c : arr) {
50+
charMap.put(c, charMap.getOrDefault(c, 0) + 1);
51+
}
52+
53+
map.put(a, charMap);
54+
}
55+
56+
return map;
57+
}
58+
}

‎Hard/Minimum Window Substring.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
class Solution {
2+
public String minWindow(String s, String t) {
3+
Map<Character, Integer> map = new HashMap<>();
4+
for (char c : t.toCharArray()) {
5+
map.put(c, (map.getOrDefault(c, 0) + 1));
6+
}
7+
8+
int start = 0;
9+
int end = 0;
10+
int count = map.size();
11+
int minLen = Integer.MAX_VALUE;
12+
String ans = "";
13+
14+
while (end < s.length()) {
15+
if (map.containsKey(s.charAt(end))) {
16+
map.put(s.charAt(end), map.get(s.charAt(end)) - 1);
17+
if (map.get(s.charAt(end)) == 0) {
18+
count--;
19+
}
20+
}
21+
22+
end++;
23+
24+
while (count == 0) {
25+
if (end - start < minLen) {
26+
minLen = end - start;
27+
ans = s.substring(start, end);
28+
}
29+
30+
if (map.containsKey(s.charAt(start))) {
31+
map.put(s.charAt(start), map.get(s.charAt(start)) + 1);
32+
if (map.get(s.charAt(start)) > 0) {
33+
count++;
34+
}
35+
}
36+
37+
start++;
38+
}
39+
}
40+
41+
return ans;
42+
}
43+
}

‎Hard/Sliding Window Maximum.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
class Solution {
2+
public static int[] maxSlidingWindowDynamic(int[] nums, int k) {
3+
if (nums.length == 0 || nums.length < k) {
4+
return new int[]{};
5+
}
6+
7+
int[] maxLeft = new int[nums.length];
8+
int[] maxRight = new int[nums.length];
9+
10+
maxLeft[0] = nums[0];
11+
maxRight[nums.length-1] = nums[nums.length-1];
12+
13+
for (int i=1; i<nums.length; i++) {
14+
maxLeft[i] = i%k == 0 ? nums[i] : Math.max(nums[i], maxLeft[i-1]);
15+
int j = nums.length - i - 1;
16+
maxRight[j] = j%k == 0 ? nums[j] : Math.max(maxRight[j+1], nums[j]);
17+
}
18+
19+
int[] ans = new int[nums.length - k + 1];
20+
21+
for (int i=0; i<=nums.length-k; i++) {
22+
ans[i] = Math.max(maxRight[i], maxLeft[i + k - 1]);
23+
}
24+
25+
return ans;
26+
}
27+
28+
public static int[] maxSlidingWindow(int[] nums, int k) {
29+
if (nums.length == 0 || nums.length < k) {
30+
return new int[]{};
31+
}
32+
33+
int[] ans = new int[nums.length-k+1];
34+
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
35+
@Override
36+
public int compare(Integer o1, Integer o2) {
37+
return o2 - o1;
38+
}
39+
});
40+
41+
for (int i=0; i<k; i++) {
42+
priorityQueue.add(nums[i]);
43+
}
44+
45+
int j = 0;
46+
for (int i=k; i<nums.length; i++) {
47+
48+
ans[j] = priorityQueue.peek();
49+
priorityQueue.remove(nums[j]);
50+
priorityQueue.add(nums[i]);
51+
j++;
52+
}
53+
54+
ans[j] = priorityQueue.peek();
55+
56+
return ans;
57+
}
58+
}

‎Medium/Kth Smallest Element in a BST.java

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,25 +10,23 @@
1010
class Solution {
1111
public int kthSmallest(TreeNode root, int k) {
1212
Stack<TreeNode> stack = new Stack<>();
13-
int ans = -1;
1413

15-
while(root != null || !stack.empty()) {
14+
while (root != null || !stack.empty()) {
1615
while (root != null) {
1716
stack.push(root);
1817
root = root.left;
1918
}
2019

21-
k--;
22-
root = stack.pop();
20+
root = stack.peek();
21+
stack.pop();
2322

24-
if (k == 0) {
25-
ans = root.val;
26-
break;
23+
if (--k == 0) {
24+
return root.val;
2725
}
2826

2927
root = root.right;
3028
}
3129

32-
return ans;
30+
return -1;
3331
}
3432
}

0 commit comments

Comments
 (0)