Skip to content

Commit d51281d

Browse files
anxious-coder-lhsanxious-coder-lhs
committed
Added solutions for 103, 33 and 1576.
1 parent d93c6bb commit d51281d

8 files changed

+340
-0
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,10 @@ Happy to accept any contributions to this in any langugage.
6464
29. [Leet Code 1573 - Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/) | [Solution 1](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String_1.ts) | [Solution](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String.ts)
6565
30. [Leet Code 322: Coin Change](https://leetcode.com/problems/coin-change/) | [Solution](./level_medium/LeetCode_322_Coins_Change_1.ts) | [Sol 2](./level_medium/LeetCode_322_Coins_Change_2.TS) | [Sol 3](./level_medium/LeetCode_322_Coins_Change.ts)
6666
31. [Leet Code 927 - 3 Equal Parts](https://leetcode.com/problems/three-equal-parts/) | [Solution 1](./level_medium/LeetCode_927_Three_Equal_Parts.ts) | [Solution 1](./level_medium/LeetCode_927_Three_Equal_Parts_1.ts)
67+
32. [Leet Code 103 - Tree Zig Zag](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) | [Solution](./level_medium/LeetCode_103_Tree_ZigZag_1.ts) | [Solution](./level_medium/LeetCode_103_Tree_ZigZag_2.ts) | [Solution](./level_medium/LeetCode_103_Tree_ZigZag_3.ts)
68+
33. [Leet Code 33 - Search in rotated](https://leetcode.com/problems/search-in-rotated-sorted-array/) | [Solution 1](./level_medium/LeetCode_33_Search_In_Rotated_Array_1.ts) | [Solution 2](./level_medium/LeetCode_33_Search_In_Rotated_Array.ts)
69+
34. [Leet Code 1578 - Minimum Deletion Cost to Avoid Repeating Letters](https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/) | [Solution](./level_medium/LeetCode_1578_Min_Chars_To_Remove_Duplicates.ts)
70+
35. [Leet Code 1576 - Replace All ?s](https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters/) | [Solution](./level_medium/LeetCode_1576_Replace_All_?.ts)
6771

6872

6973
## Hard

‎level_medium/LeetCode_103_Tree_ZigZag_1.ts

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* class TreeNode {
4+
* val: number
5+
* left: TreeNode | null
6+
* right: TreeNode | null
7+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.left = (left===undefined ? null : left)
10+
* this.right = (right===undefined ? null : right)
11+
* }
12+
* }
13+
*/
14+
15+
function zigzagLevelOrder(root: TreeNode | null): number[][] {
16+
17+
// Base Condition
18+
if (root === null) return []
19+
20+
// Level by level storage of visited nodes.
21+
const queue: (TreeNode | null)[][] = [[root]];
22+
23+
// Iterate over the queue
24+
let pos = 0, curr;
25+
while((curr = queue[pos++]) !== undefined) {
26+
const next: (TreeNode | null)[] = [];
27+
curr.forEach(elem => {
28+
if (elem.left !== null) next.push(elem.left);
29+
if (elem.right !== null) next.push(elem.right);
30+
})
31+
if (next.length >= 1) queue.push(next);
32+
}
33+
34+
return reverseAndEval(queue);
35+
};
36+
37+
function reverseAndEval(queue: (TreeNode | null)[][]): number[][] {
38+
let level = 0;
39+
const result: number[][] = [];
40+
queue.forEach(curr => {
41+
level++;
42+
const next: number[] = [];
43+
curr.forEach(item => next.push(item.val));
44+
if (level % 2 === 1)
45+
result.push(next);
46+
else
47+
result.push(next.reverse());
48+
})
49+
return result;
50+
}

‎level_medium/LeetCode_103_Tree_ZigZag_2.ts

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* class TreeNode {
4+
* val: number
5+
* left: TreeNode | null
6+
* right: TreeNode | null
7+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.left = (left===undefined ? null : left)
10+
* this.right = (right===undefined ? null : right)
11+
* }
12+
* }
13+
*/
14+
15+
/**
16+
* LeetCode 103
17+
*
18+
* BFS approach, standard DFS for navigation, also adds an indicator for level.
19+
* Inserts the results in the left->right or right->left order for the final result.
20+
*
21+
* Time: O(n), Space: O(n)
22+
*
23+
* @param root
24+
*/
25+
function zigzagLevelOrder(root: TreeNode | null): number[][] {
26+
27+
// Base Condition
28+
if (root === null) return []
29+
30+
// Level by level storage of visited nodes.
31+
let lastLevel: (TreeNode | null)[] = [root], result: number[][] = [];
32+
33+
// Iterate over the queue
34+
let pos = 0, curr, hasNext = true, level = 0;
35+
while(hasNext) {
36+
const next: (TreeNode | null)[] = [];
37+
const vals: number[] = Array(lastLevel.length).fill(0);
38+
let pos, offset;
39+
if (level % 2 === 0) {
40+
pos = 0; offset = 1;
41+
} else {
42+
pos = lastLevel.length - 1; offset = -1;
43+
}
44+
45+
lastLevel.forEach(elem => {
46+
vals[pos] = elem.val;
47+
if (elem.left !== null) next.push(elem.left);
48+
if (elem.right !== null) next.push(elem.right);
49+
pos += offset;
50+
});
51+
52+
hasNext = next.length > 0;
53+
result.push(vals);
54+
55+
lastLevel = next;
56+
level++;
57+
}
58+
59+
return result;
60+
};

‎level_medium/LeetCode_103_Tree_ZigZag_3.ts

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* class TreeNode {
4+
* val: number
5+
* left: TreeNode | null
6+
* right: TreeNode | null
7+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.left = (left===undefined ? null : left)
10+
* this.right = (right===undefined ? null : right)
11+
* }
12+
* }
13+
*/
14+
/**
15+
* LeetCode 103
16+
*
17+
* DFS approach, standard DFS for navigation, also adds an indicator for level.
18+
* Inserts the results in the left->right or right->left order for the final result.
19+
*
20+
* Time: O(n), Space: O(H)
21+
*
22+
* @param root
23+
*/
24+
function zigzagLevelOrder(root: TreeNode | null): number[][] {
25+
26+
// Base Condition
27+
if (root === null) return []
28+
29+
const result: number[][] = [];
30+
traverseHelper(root, 0, result);
31+
return result;
32+
};
33+
34+
function traverseHelper(node: TreeNode | null, level: number, result: number[][]) {
35+
36+
if (node === null) return
37+
38+
result[level] = result[level] || [];
39+
if (level % 2 === 0) {
40+
result[level].push(node.val);
41+
} else {
42+
result[level].unshift(node.val);
43+
}
44+
45+
traverseHelper(node.left, level + 1, result);
46+
traverseHelper(node.right, level + 1, result);
47+
}

‎level_medium/LeetCode_1576_Replace_All_?.ts

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Solution uses multiple pointer approach to point to the next and last element. With eachs step, we just need
3+
* to find a suitable replacement char, which can be from 'a,b,c'. This can be find in linear time.
4+
*
5+
* Time: O(n), Space: O(1)
6+
* @param s
7+
*/
8+
function modifyString(s: string): string {
9+
const strArr = s.split('');
10+
let last = 0;
11+
for (let pos = 0; pos < strArr.length; pos++) {
12+
if (s[pos] === '?') {
13+
const next = pos < strArr.length - 1 ? s.charCodeAt(pos + 1) : 0; const replaceCode = getReplacementCode(last, next);
14+
strArr[pos] = String.fromCharCode(replaceCode);
15+
last = replaceCode;
16+
} else {
17+
last = s.charCodeAt(pos);
18+
}
19+
}
20+
21+
return strArr.join("");
22+
};
23+
24+
function getReplacementCode(last: number, next: number) {
25+
for (let char = 97; char <= 122; char++) {
26+
if (char !== last && char !== next) return char;
27+
}
28+
}

‎level_medium/LeetCode_1578_Min_Chars_To_Remove_Duplicates.ts

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/**
2+
* Leet Code 1578
3+
*
4+
* Solution finds out all the duplicate elements using a single iteration. The problem requires removing all but
5+
* one duplicate consequitive chars. The only character remaining should be the most expensive char. This can
6+
* be done by calculating the total cost of the group and the max cost of any item in the group.
7+
*
8+
* Time: O(n), Space: O(1)
9+
*
10+
* @param s
11+
* @param cost
12+
*/
13+
function minCost(s: string, cost: number[]): number {
14+
let totalCost = 0, last = '';
15+
let totalCostCurr = 0, maxCostCurr = 0;
16+
for (let pos = 0; pos < s.length; pos++) {
17+
const curr = s[pos];
18+
if (last === curr) {
19+
totalCostCurr += cost[pos];
20+
maxCostCurr = Math.max(cost[pos], maxCostCurr);
21+
} else {
22+
totalCost += (totalCostCurr - maxCostCurr);
23+
totalCostCurr = cost[pos];
24+
maxCostCurr = cost[pos];
25+
}
26+
last = curr;
27+
}
28+
29+
// Adding for possible duplicates at the tail.
30+
totalCost += (totalCostCurr - maxCostCurr);
31+
32+
return totalCost;
33+
};

‎level_medium/LeetCode_33_Search_In_Rotated_Array.ts

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
/**
2+
* Leet Code 33
3+
*
4+
* Solution uses a binary search approach. We use binary search to find the rotation point, i.e. the smallest
5+
* element in the array. Since, now all the elements before and after rotation point are in ascending order, we
6+
* can use the binary search to either search in the left side or the right side.
7+
*
8+
* Time and Space: O(log n)
9+
*
10+
* @param nums
11+
* @param target
12+
*/
13+
function search(nums: number[], target: number): number {
14+
15+
// Base Conditions.
16+
if (nums.length <= 0) return -1;
17+
if (nums.length === 1) return nums[0] === target ? 0 : -1;
18+
19+
const rotationPos = findRotationPivot(nums);
20+
if (rotationPos === -1)
21+
return binarySearch(nums, target, 0, nums.length - 1);
22+
23+
if (target >= nums[0] && target <= nums[rotationPos - 1]) {
24+
return binarySearch(nums, target, 0, rotationPos - 1);
25+
} else if (target >= nums[rotationPos] && target <= nums[nums.length - 1]) {
26+
return binarySearch(nums, target, rotationPos, nums.length - 1);
27+
}
28+
29+
return -1;
30+
};
31+
32+
function binarySearch(nums: number[], target: number, beg: number, end: number) {
33+
34+
// Base Condition, no match found.
35+
if (end < beg) {
36+
return -1;
37+
}
38+
39+
const pivot = Math.floor((beg+end)/2);
40+
const elem = nums[pivot];
41+
42+
if (target > elem) {
43+
// Finding bigger element.
44+
return binarySearch(nums, target, pivot + 1, end);
45+
} else if (target < elem) {
46+
// Finding smaller element.
47+
return binarySearch(nums, target, beg, pivot - 1);
48+
} else {
49+
return pivot;
50+
}
51+
}
52+
53+
54+
// Returns the smallest element of the array, i.e. the rotation point.
55+
function findRotationPivot(nums: number[], beg: number = 0, end: number = nums.length - 1): number {
56+
57+
// No rotation point, not rotated.
58+
if (end < beg) return -1;
59+
60+
let pivot = Math.floor((beg + end)/2);
61+
const curr = nums[pivot];
62+
const prev = pivot > 0 ? nums[pivot - 1] : -Infinity;
63+
if (curr < prev) {
64+
// Found the smallest, since this is supposed to be a bigger element.
65+
return pivot;
66+
} else {
67+
if (nums[0] <= curr) {
68+
// Smallest element on the right side.
69+
return findRotationPivot(nums, pivot + 1, end);
70+
} else {
71+
// Smallest element on the left side.
72+
return findRotationPivot(nums, 0, pivot - 1);
73+
}
74+
}
75+
}
76+
77+
console.log(search([5, 1, 2], 5));

‎level_medium/LeetCode_33_Search_In_Rotated_Array_1.ts

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/**
2+
* Leet Code 33
3+
*
4+
* Solution uses a binary search approach. We do it without searching the rotation point. The trick is simple.
5+
* While doing the regular binary search, check based on 1st and last element, where the element might be.
6+
*
7+
* Time: O(log n), Space: O(1).
8+
*
9+
* @param nums
10+
* @param target
11+
*/
12+
function search(nums: number[], target: number): number {
13+
14+
// Base Conditions.
15+
if (nums.length <= 0) return -1;
16+
if (nums.length === 1) return nums[0] === target ? 0 : -1;
17+
18+
let left = 0, right = nums.length - 1;
19+
const first = nums[0], last = nums[nums.length - 1];
20+
while(left <= right) {
21+
const pivot = Math.floor((left+right)/2);
22+
const current = nums[pivot];
23+
if (current === target) return pivot;
24+
25+
if (current >= first) {
26+
// Left side is not rotated.
27+
if (target < current && target >= first)
28+
right = pivot - 1;
29+
else
30+
left = pivot + 1;
31+
} else {
32+
// Left side is rotated.
33+
if (target > current && target <= last)
34+
left = pivot + 1;
35+
else
36+
right = pivot - 1;
37+
}
38+
}
39+
40+
return -1;
41+
};

0 commit comments

Comments
 (0)