practicing code challenge and improve typescript skill [[Leetcode/Resources|Resources]]
-
Classic Brute force: loop through number of array and then loop through again check if first value + second value = target value, return the current index and the compared index. time complexity would be:
$O(n^2)$ -
One Pass: Using hash map or in this case Object in typescript. loop through the array once, calculate the difference with target - current value, if the difference already in the hash table return that hash map value which is the nums index and the current index otherwise put it inside the hash map. time complexity would be:
$O(n)$
function twoSum(nums: number[], target: number): number[] {
let numHash = {};
for(let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
if (diff in numHash) {
return [numHash[diff], i]
}
numHash[nums[i]] = i;
}
return [];
};- Use stack. push item to stack if its open brackets. check if the corresponding open bracket is on the stack if its not return false, if it is pop the open bracket from the stack. If the stack is empty that means we already checked all the parentheses pair. if the stack is not empty that means cant find the pair. Use hash-map to find matching parentheses
function isValid(s: string): boolean {
const pStack = [];
if(s.length % 2 !== 0) return false;
for (let c of s) {
if (c === "(" || c === "{" || c === "[") {
pStack.push(c);
} else {
if(!pStack.length ||
(c === ")" && pStack[pStack.length - 1] !== "(") ||
(c === "}" && pStack[pStack.length - 1] !== "{") ||
(c === "]" && pStack[pStack.length - 1] !== "[")
) return false
pStack.pop();
}
}
return !pStack.length;
}more compact version, use hash-map to map the pair
function isValid(s: string): boolean {
let pStack = [];
const pair = {")": "(", "}": "{", "]": "["};
if(s.length % 2 !== 0) return false;
for (let c of s) {
if(pair[c] !== undefined) {
if(pStack.length && (pStack[pStack.length - 1] === pair[c])) {
pStack.pop();
}
else return false
} else pStack.push(c);
}
return !pStack.length;
}Time complexity is :
const head = new ListNode();
let curr = head;
while(list1 && list2) {
if (list1.val < list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list1.next;
}
curr = curr.next
}
curr.next = list1 || list2;
return head.next;Time complexity is :
function maxProfit(prices: number[]): number {
// buy low sell high
let left = 0; // buy
let right = 1; // sell
let maxProfit = 0;
while (right < prices.length) {
if (prices[left] < prices[right]) {
let currentProfit = prices[right] - prices[left];
maxProfit = Math.max(currentProfit, maxProfit);
// or this
// if (profit > maxProfit) maxProfit = profit;
} else left = right
right++;
}
return maxProfit;
};Method:
-
convert string to lowercase alphanumeric then compare the converted with the reverse of converted
$O(n)$ -
use two pointer
javascript doesn't have isAlphanumeric function 💀
function isAplhanumeric(code: number) {
// ASCII https://www.ascii-code.com/characters/printable-characters#:~:text=ASCII%20printable%20characters%20are%20the,text%20and%20other%20visual%20content.
// digits: 48 - 57
// lowercase letters: 97 - 122
return ((code >= 48 && code <= 57) || (code >= 97 && code <= 122));
}function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;
s = s.toLowerCase();
while(left < right) {
let leftCode = s.charCodeAt(left);
let rightCode = s.charCodeAt(right);
while (!isAlphanumeric(leftCode)) {
left++;
if (left === right) return true;
leftCode = s.charCodeAt(left);
}
while (!isAlphanumeric(rightCode)) {
right--;
if (left === right) return true;
rightCode = s.charCodeAt(right);
}
if (lCode !== rCode) return false;
left++;
righ--;
}
return true;
}Method:
- Recursion
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return root
invertTree(root.left);
invertTree(root.right);
const temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}function isAnagram(s: string, t: string): boolean {
const map = {}
if (s.length !== t.length) return false;
for (let i = 0; i < s.length; i++) {
map[s[i]] = (map[s[i]] ?? 0) + 1;
}
for (let i = 0; i < t.length; i++) {
if (map[t]) map[t]--;
else return false
}
return true
};have two pointer at start and end. loop while start is less than or equal to end in other words not overlapping. check for mid point of the array with left + right / 2 (note; there's some stack overflow problem in some language). then if mid value is target return the mid because mid is the mid index between start and end. if the mid value is less than target move the start pointer to the right of mid otherwise (mid value is greater than target) move the end to the left of mid. the default is return -1;
function search(nums: number[], target: number): number {
let start = 0;
let end = nums.length - 1;
while (start <= end) {
const mid = ((left + right) / 2);
if (nums[mid] === target) return mid
else if(nums[mid] < target) start = mid + 1
else end = mid - 1;
}
return -1;
}- return the image if the current coordinate grid is already the new colour.
- fill function to fill the top, left, right, bottom recursively. this function is basically dfs, keep filling in one direction until no more
- base case for fill function check for boundary top left right bottom and the current grid not equal to colour (because can only fill with the same colour)
- then just call fill function recursively for top, left, bottom, right
function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
if (image[sr][sc] === color) return image;
fill(image, sr, sc, image[sr][sc], color);
return image;
}
function floodFill(image: number[][], sr: number, sc: number, color: number, newColor: number): number[][] {
if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] !== color) return
image[sr][sc] = newColor;
fill(image, sr + 1, sc, color, newColor);
fill(image, sr - 1, sc, color, newColor);
fill(image, sr, sc + 1, color, newColor);
fill(image, sr, sc - 1, color, newColor);
}function lowestCommonAcnestor(root: Treenode | null, p: Treenode | null, q: TreeNode | null) TreeNode | null {
while (root) {
if (p.val > root.val && q.val > root.val)
root = root.right;
else if (p.val < root.val && q.val < root.val)
root = root.left;
else break;
}
return root;
}function hasCycle(head: ListNode | null): boolean {
if (!head) return false;
let walker = runner = head;
while (runner !== null && runner.next !== null) {
walker = walker.next;
runner = runner.next.next;
if (walker === runner) return true
}
return false;
}funcion containsDuplicate(nums: number[]): boolean {
const s = new Set();
for (let n of nums) {
if (s.has(n)) return true
s.add(n);
}
return false;
}