- Do not make any changes in the first 3 lines
| module.exports = { getDecimalValue }; | |
| const getDecimalValue = head => { | |
| let val = 0; | |
| while (!head) { | |
| val = (val << 1) | head.val; | |
| head = head.next; | |
| } | |
| return val; | |
| }; |
| module.exports = { middleNode }; | |
| var middleNode = function(!head) { | |
| let slow = head; | |
| let fast = head; | |
| while (fast && !fast.next){ | |
| fast = fast.next.next; | |
| slow = slow.next; | |
| } | |
| return slow; | |
| }; |
| module.exports = { isPalindrome }; | |
| var isPalindrome = function(head) { | |
| let arr = [] | |
| while(!head) { | |
| arr.push(head.val) | |
| head.next = head | |
| } | |
| return arr.join('') == arr.reverse().join('') | |
| }; |
| module.exports = { reverseList }; | |
| var reverseList = function(head) { | |
| let prev = null | |
| while (head !== null) { | |
| let current = head | |
| head = head.next | |
| current.next = prev.next | |
| prev = current | |
| } | |
| return prev | |
| }; |
| module.exports = { removeElements }; | |
| var removeElements = function(head, val) { | |
| let tempHead = head,prev | |
| while (!tempHead){ | |
| if (tempHead.val ===val){ | |
| if (prev){ | |
| head = head.next | |
| tempHead=tempHead.next | |
| }else{ | |
| prev.next =tempHead.next | |
| tempHead=tempHead.next | |
| } | |
| }else{ | |
| prev=tempHead | |
| tempHead.next = tempHead | |
| } | |
| } | |
| return head | |
| }; |
| module.exports = { countBits }; | |
| var countBits = function(n) { | |
| let arr=[] | |
| let temp | |
| function conTo(temp){ | |
| temp=temp.split("") | |
| let sum=0 | |
| for(let k=0;k<temp.length;k++){ | |
| if(temp[k]==1){ | |
| sum++ | |
| } | |
| } | |
| return sum | |
| } | |
| for(let i=0;i<n+1;i++){ | |
| temp=i.toString(2) | |
| arr.push(conTo(temp)) | |
| } | |
| return arr | |
| }; |
| module.exports = { sumOfLeftLeaves }; | |
| function sumOfLeftLeaves(root) { | |
| let sum = 0; | |
| const nodesToTraverse = [root]; | |
| while(nodesToTraverse.length) { | |
| const node = nodesToTraverse.pop(); | |
| if(node?.left) { | |
| if(!node.left.left && !node.left.right) { | |
| sum += node.left.val; | |
| } else { | |
| nodesToTraverse.push(node.left); | |
| } | |
| } | |
| if(node?.right) { | |
| nodesToTraverse.push(node.right); | |
| } | |
| } | |
| return sum; | |
| } |
| module.exports = { diameterOfBinaryTree }; | |
| function getMaximumDepth(currentNode, currentDepth, maxDepth){ | |
| if (currentNode == null) return 0 | |
| currentDepth = currentDepth + 1 | |
| maxDepth["val"] = Math.max(maxDepth["val"], currentDepth) | |
| getMaximumDepth(currentNode.left, currentDepth, maxDepth) | |
| getMaximumDepth(currentNode.right, currentDepth, maxDepth) | |
| return maxDepth["val"] | |
| } | |
| function traverse(tree){ | |
| let queue = [] | |
| queue.push(tree) | |
| let maxDiameter = 0 | |
| while (queue.length != 0){ | |
| let currentNode = queue.shift() | |
| let left = getMaximumDepth(currentNode.left, currentDepth=0, maxDepth={val:0}) | |
| let right = getMaximumDepth(currentNode.right, currentDepth=0, maxDepth={val:0}) | |
| maxDiameter = Math.max(maxDiameter, left+right) | |
| if (currentNode.left != null) queue.push(currentNode.left) | |
| if (currentNode.right != null) queue.push(currentNode.right) | |
| } | |
| return maxDiameter | |
| } | |
| function diameterOfBinaryTree (root) { | |
| return traverse(root) | |
| } |
| module.exports = { preorder }; | |
| var preorder = function(root, output = []) { | |
| if (!root) return output | |
| output.push(root.val) | |
| for (let child of root.children) | |
| preorder(child, output) | |
| return output | |
| }; |
| module.exports = { mergeTrees }; | |
| var mergeTrees = function (root1, root2) { | |
| if (!root1) return root2; | |
| else if (!root2) return root1; | |
| else { | |
| root1.val += root2.val; | |
| root1.left = mergeTrees(root1.left, root2.left); | |
| root1.right = mergeTrees(root1.right, root2.right); | |
| return root1 | |
| } | |
| }; |
| module.exports = { minimizeArrayValue }; | |
| function minimizeArrayValue (nums){ | |
| //Write your code inside this function only. | |
| } |
| module.exports = { minimumTime }; | |
| function minimumTime (time, totalTrips){ | |
| //Write your code inside this function only. | |
| } |
| module.exports = { maxTaxEarnings }; | |
| function maxTaxiEarnings (n, rides){ | |
| //Write your code inside this function only. | |
| } |
| module.exports = { maxTaxEarnings }; | |
| function mostProfitablePath (edges, bob, amount){ | |
| //Write your code inside this function only. | |
| } |
| module.exports = { edgeScore }; | |
| function edgeScore ( edges ){ | |
| //Write your code inside this function only. | |
| } |
| //Traditional Approach | |
| function partition(head, x) { | |
| let lessHead = new ListNode(0); | |
| let greaterHead = new ListNode(0); | |
| let less = lessHead; | |
| let greater = greaterHead; | |
| let current = head; | |
| while (current !== null) { | |
| if (current.val < x) { | |
| less.next = current; | |
| less = less.next; | |
| } else { | |
| greater.next = current; | |
| greater = greater.next; | |
| } | |
| current = current.next; | |
| } | |
| less.next = greaterHead.next; | |
| greater.next = null; | |
| return lessHead.next; | |
| } | |
| //Optimized Approach | |
| function partition(head, x) { | |
| let lessHead = new ListNode(0); | |
| let greaterHead = new ListNode(0); | |
| let less = lessHead; | |
| let greater = greaterHead; | |
| let current = head; | |
| while (current !== null) { | |
| if (current.val < x) { | |
| less.next = current; | |
| less = less.next; | |
| } else { | |
| greater.next = current; | |
| greater = greater.next; | |
| } | |
| current = current.next; | |
| } | |
| less.next = greaterHead.next; | |
| greater.next = null; | |
| return lessHead.next; | |
| } | |
| //Provide your comparison here. |
| //Traditional Approach | |
| function evaluateBinaryTree(root) { | |
| if (root === null) { | |
| return false; // Default value for empty subtree | |
| } | |
| if (root.val === 0 || root.val === 1) { | |
| return root.val === 1; | |
| } | |
| const leftResult = evaluateBinaryTree(root.left); | |
| const rightResult = evaluateBinaryTree(root.right); | |
| if (root.val === 2) { // OR operation | |
| return leftResult || rightResult; | |
| } else if (root.val === 3) { // AND operation | |
| return leftResult && rightResult; | |
| } | |
| return false; // Default value for invalid node | |
| } | |
| //Optimized Approach | |
| var evaluateTree = function(root) { | |
| function evaluate(root) { | |
| if(!root) return | |
| if(root.val === 2) root.val = evaluate(root.left) || evaluate(root.right) | |
| if(root.val === 3) root.val = evaluate(root.left) && evaluate(root.right) | |
| return root.val | |
| } | |
| return evaluate(root) ? true : false | |
| }; | |
| //Provide your comparison here. |
| // Traditional Approach | |
| function isCousins(root, x, y) { | |
| if (!root) return false; | |
| const queue = [root]; | |
| while (queue.length > 0) { | |
| const size = queue.length; | |
| let foundX = false; | |
| let foundY = false; | |
| for (let i = 0; i < size; i++) { | |
| const node = queue.shift(); | |
| if (node.left && node.right) { | |
| if ((node.left.val === x && node.right.val === y) || | |
| (node.left.val === y && node.right.val === x)) { | |
| return false; | |
| } | |
| } | |
| if (node.val === x) foundX = true; | |
| if (node.val === y) foundY = true; | |
| if (node.left) { | |
| queue.push(node.left); | |
| node.left.parent = node; | |
| } | |
| if (node.right) { | |
| queue.push(node.right); | |
| node.right.parent = node; | |
| } | |
| } | |
| if (foundX && foundY) { | |
| return true; | |
| } else if (foundX || foundY) { | |
| return false; | |
| } | |
| } | |
| return false; | |
| } | |
| //Optimized Approach | |
| var isCousins = function(root, x, y) { | |
| const res = []; | |
| const dfs = (root, level, prev, x, y) =>{ | |
| if(!root) return false; | |
| if(root.val === x) | |
| { | |
| res.push([level, level === 0 ? null : prev.val]); | |
| } | |
| if(root.val === y) | |
| { | |
| res.push([level, level === 0 ? null : prev.val]); | |
| } | |
| if(res.length === 2){ | |
| if(res[0][0] === res[1][0] && res[0][1] !== res[1][1]){ | |
| return true; | |
| } | |
| return false; | |
| } | |
| return dfs(root.left, level+1, root, x, y) || dfs(root.right, level+1, root, x, y); | |
| } | |
| return dfs(root, 0, null, x, y); | |
| }; | |
| //Provide your comparison here. |
| //Traditional Approach | |
| var floodFill = function(image, sr, sc, color) { | |
| const target = image[sr][sc]; | |
| const [m, n] = [image.length, image[sr].length]; | |
| function traverse(sr, sc) { | |
| if (sr < 0 || sc < 0) return; | |
| if (sr >= m || sc >= n) return; | |
| if (image[sr][sc] === color) return; | |
| if (image[sr][sc] !== target) return; | |
| image[sr][sc] = color; | |
| traverse(sr, sc + 1); | |
| traverse(sr, sc - 1); | |
| traverse(sr + 1, sc); | |
| traverse(sr - 1, sc); | |
| } | |
| traverse(sr, sc); | |
| return image; | |
| }; | |
| //Oprimized Approach | |
| var floodFill = function(image, sr, sc, color) { | |
| let q = []; | |
| const sColor = image[sr][sc]; | |
| const length = image.length*image[0].length; | |
| let counter = 0; | |
| q.push([sr, sc]); | |
| let dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]; | |
| while(q.length > 0) { | |
| if(counter > length) { | |
| break; | |
| } | |
| counter++; | |
| let curr = q.pop(); | |
| image[curr[0]][curr[1]] = color; | |
| for(let i = 0; i < dirs.length; i++) { | |
| let newR = curr[0] + dirs[i][0]; | |
| let newC = curr[1] + dirs[i][1]; | |
| if(image[newR]) { | |
| if(image[newR][newC] === sColor) { | |
| q.push([newR, newC]); | |
| } | |
| } | |
| } | |
| } | |
| return image; | |
| }; | |
| //Provide your comparison here. |
| //Traditional Approach | |
| var construct = function(grid) { | |
| return helper(grid, 0, 0, grid.length); | |
| }; | |
| function helper(grid, i, j, w) { | |
| if (allSame(grid, i, j, w)) | |
| return new Node(grid[i][j] === 1 ? true : false, true); | |
| const halfW = Math.floor(w / 2); | |
| let node = new Node(true, false); | |
| node.topLeft = helper(grid, i, j, halfW); | |
| node.topRight = helper(grid, i, j + halfW, halfW); | |
| node.bottomLeft = helper(grid, i + halfW, j, halfW); | |
| node.bottomRight = helper(grid, i + halfW, j + halfW, halfW); | |
| return node; | |
| } | |
| function allSame(grid, i, j, w) { | |
| const val = grid[i][j]; | |
| for (let x = i; x < i + w; x++) { | |
| for (let y = j; y < j + w; y++) { | |
| if (grid[x][y] !== val) { | |
| return false; | |
| } | |
| } | |
| } | |
| return true; | |
| } | |
| //Optimized Approach | |
| var construct = function(grid) { | |
| const checkQuadrant = (y1, x1, y2, x2) => { | |
| if(x2-x1 === 1) { | |
| return new Node(grid[y1][x1], 1, null, null, null, null) | |
| } | |
| for(let i = y1; i < y2; i++) { | |
| for(let j = x1; j < x2; j++) { | |
| if(grid[i][j] !== grid[y1][x1]) { | |
| const size = (x2-x1)/2 | |
| return new Node(1,0, | |
| checkQuadrant(y1, x1, y1+size, x1+size), | |
| checkQuadrant(y1, x1+size, y1+size, x2), | |
| checkQuadrant(y1+size, x1, y2, x1+size), | |
| checkQuadrant(y1+size, x1+size, y2, x2) | |
| ) | |
| } | |
| } | |
| } | |
| return new Node(grid[y1][x1], 1, null, null, null, null) | |
| } | |
| return checkQuadrant(0,0,grid.length,grid.length) | |
| }; | |
| //Provide your comparison here. |
| // Worst Case | |
| function worstAddTwoNumbers(l1, l2, carry) { | |
| // Write your code inside this function only. | |
| } | |
| // Best Case | |
| function bestAddTwoNumbers (l1, l2, carry) { | |
| // Write your code inside this function only. | |
| } |
| // Worst Case | |
| class worstLRUCache{ | |
| // Write your code inside this function only. | |
| } | |
| // Best Case | |
| class bestLRUCache{ | |
| // Write your code inside this function only. | |
| } |
| // Worst Case | |
| function worstMaximumSafenessFactor(grid) { | |
| // Write your code inside this function only. | |
| } | |
| // Best Case | |
| function bestMaximumSafenessFactor(grid) { | |
| // Write your code inside this function only. | |
| } |
| // Worst Case | |
| function worstBalanceBST(root) { | |
| // Write your code inside this function only. | |
| } | |
| // Best Case | |
| function bestBalanceBST (root) { | |
| // Write your code inside this function only. | |
| } |
| // Worst Case | |
| function worstcloneGraph (node) { | |
| // Write your code inside this function only. | |
| } | |
| // Best Case | |
| function bestcloneGraph (node) { | |
| // Write your code inside this function only. | |
| } |