Skip to content

Commit 1b13a38

Browse files
varunu28varunu28
committed
Added Teoplitz Matrix.java & refactored 4 solutions
1 parent c6a4243 commit 1b13a38

5 files changed

+84
-95
lines changed

‎Easy/Teoplitz Matrix.java

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution {
2+
public boolean isToeplitzMatrix(int[][] matrix) {
3+
for (int i = 0; i < matrix.length; i++) {
4+
for (int j = 0; j < matrix[0].length; j++) {
5+
if (i > 0 && j > 0 && matrix[i][j] != matrix[i - 1][j - 1]) {
6+
return false;
7+
}
8+
}
9+
}
10+
return true;
11+
}
12+
}

‎Hard/Longest Substring with At Most K Distinct Characters.java

Lines changed: 18 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,22 @@
11
class Solution {
2-
public int lengthOfLongestSubstringKDistinct(String s, int k) {
3-
int maxLen = 0;
4-
int start = 0;
5-
6-
Map<Character, Integer> map = new HashMap<>();
7-
for (int i = 0; i < s.length(); i++) {
8-
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
9-
10-
while (map.size() > k) {
11-
map.put(s.charAt(start), map.get(s.charAt(start)) - 1);
12-
if (map.get(s.charAt(start)) == 0) {
13-
map.remove(s.charAt(start));
14-
}
15-
16-
start++;
17-
}
18-
19-
maxLen = Math.max(maxLen, i - start + 1);
2+
public int lengthOfLongestSubstringKDistinct(String s, int k) {
3+
Map<Character, Integer> map = new HashMap<>();
4+
int slow = 0;
5+
int fast = 0;
6+
int n = s.length();
7+
int maxLength = 0;
8+
while (fast < n) {
9+
map.put(s.charAt(fast), map.getOrDefault(s.charAt(fast), 0) + 1);
10+
while (map.size() > k) {
11+
map.put(s.charAt(slow), map.getOrDefault(s.charAt(slow), 0) - 1);
12+
if (map.get(s.charAt(slow)) == 0) {
13+
map.remove(s.charAt(slow));
2014
}
21-
22-
return maxLen;
15+
slow++;
16+
}
17+
fast++;
18+
maxLength = Math.max(maxLength, fast - slow);
2319
}
20+
return maxLength;
21+
}
2422
}

‎Medium/Binary Search Tree to Greater Sum Tree.java

Lines changed: 22 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -8,19 +8,28 @@
88
* }
99
*/
1010
class Solution {
11-
public TreeNode bstToGst(TreeNode root) {
12-
inorderReverse(root, new int[]{0});
13-
return root;
11+
public TreeNode bstToGst(TreeNode root) {
12+
if (root == null) {
13+
return null;
1414
}
15-
16-
private void inorderReverse(TreeNode root, int[] currVal) {
17-
if (root == null) {
18-
return;
19-
}
20-
21-
inorderReverse(root.right, currVal);
22-
currVal[0] += root.val;
23-
root.val = currVal[0];
24-
inorderReverse(root.left, currVal);
15+
TreeNode curr = root;
16+
Stack<TreeNode> stack = new Stack<>();
17+
int sum = 0;
18+
pushRight(stack, curr);
19+
while (!stack.isEmpty()) {
20+
TreeNode removed = stack.pop();
21+
sum += removed.val;
22+
removed.val = sum;
23+
TreeNode leftNode = removed.left;
24+
pushRight(stack, leftNode);
2525
}
26+
return root;
27+
}
28+
29+
private void pushRight(Stack<TreeNode> stack, TreeNode curr) {
30+
while (curr != null) {
31+
stack.push(curr);
32+
curr = curr.right;
33+
}
34+
}
2635
}

‎Medium/Max Increase to Keep City Skyline.java

Lines changed: 15 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,21 @@
11
class Solution {
22
public int maxIncreaseKeepingSkyline(int[][] grid) {
3-
int[] top = new int[grid.length];
4-
int[] left = new int[grid.length];
5-
int j = 0;
6-
7-
for (int[] g : grid) {
8-
int max = Integer.MIN_VALUE;
9-
for (int i=0; i<g.length; i++) {
10-
max = Math.max(max, g[i]);
11-
}
12-
13-
left[j++] = max;
3+
int numRows = grid.length;
4+
int numCols = grid[0].length;
5+
int[] rowMax = new int[numRows];
6+
int[] colMax = new int[numCols];
7+
for (int i = 0; i < numRows; i++) {
8+
for (int j = 0; j < numCols; j++) {
9+
rowMax[i] = Math.max(rowMax[i], grid[i][j]);
10+
colMax[j] = Math.max(colMax[j], grid[i][j]);
1411
}
15-
16-
j = 0;
17-
for (int i=0; i<grid.length; i++) {
18-
int max = Integer.MIN_VALUE;
19-
for (int k=0; k<grid.length; k++) {
20-
max = Math.max(grid[k][i], max);
21-
}
22-
23-
top[j++] = max;
12+
}
13+
int totalIncrease = 0;
14+
for (int i = 0; i < numRows; i++) {
15+
for (int j = 0; j < numCols; j++) {
16+
totalIncrease += Math.min(rowMax[i], colMax[j]) - grid[i][j];
2417
}
25-
26-
int increase = 0;
27-
28-
for (int i=0; i<grid.length; i++) {
29-
for (int k=0; k<grid[0].length; k++) {
30-
increase += Math.min(left[i], top[k]) - grid[i][k];
31-
}
32-
}
33-
34-
return increase;
18+
}
19+
return totalIncrease;
3520
}
3621
}

‎Medium/Sort Characters By Frequency.java

Lines changed: 17 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,20 @@
11
class Solution {
2-
public String frequencySort(String s) {
3-
List<Character> chars = new ArrayList<>();
4-
for (char c : s.toCharArray()) {
5-
chars.add(c);
6-
}
7-
8-
Map<Character, Integer> map = new HashMap<>();
9-
int val = 0;
10-
for (char c : chars) {
11-
map.put(c, map.getOrDefault(c, 0) + 1);
12-
val = Math.max(val, map.get(c));
13-
}
14-
15-
Map<Integer, List<Character>> revMap = new HashMap<>();
16-
for (Character key : map.keySet()) {
17-
revMap.computeIfAbsent(map.get(key), k -> new ArrayList<>()).add(key);
18-
}
19-
20-
StringBuilder sb = new StringBuilder();
21-
for (int i = val; i >= 0; i--) {
22-
if (revMap.containsKey(i)) {
23-
List<Character> characters = revMap.get(i);
24-
for (Character character : characters) {
25-
int count = i;
26-
while (count-- > 0) {
27-
sb.append(character);
28-
}
29-
}
30-
}
31-
}
32-
33-
return sb.toString();
2+
public String frequencySort(String s) {
3+
Map<Character, Integer> map = new HashMap<>();
4+
for (char c : s.toCharArray()) {
5+
map.put(c, map.getOrDefault(c, 0) + 1);
6+
}
7+
PriorityQueue<Character> pq = new PriorityQueue<>((o1, o2) -> map.get(o2) - map.get(o1));
8+
pq.addAll(map.keySet());
9+
StringBuilder sb = new StringBuilder();
10+
while (!pq.isEmpty()) {
11+
char c = pq.poll();
12+
int count = map.get(c);
13+
while (count-- > 0) {
14+
sb.append(c);
15+
}
3416
}
17+
return sb.toString();
18+
}
3519
}
20+

0 commit comments

Comments
 (0)