Lv.3 Flashcards

Question

# **Minimum Depth of a Tree** Write a non-recursive method minTreeDepth that takes in the root node of a Binary Tree and returns the minimum depth of the tree. The minimum depth is defined as the least number of node traversals needed to reach a leaf from the root node. Your method should run in linear O(n) time and use at max O(n) space. 🪜 Stepper Hints | https://leetcode.com/problems/minimum-depth-of-binary-tree/ ## Footnote 📚 Related LeetCode Problems

Answer 1

🔹 Hint 1: Understand What a Leaf Is A leaf node is a node with no children (i.e., both left and right are null). 🔹 Hint 2: Why Recursion Isn’t Required While a recursive solution is intuitive, you’re explicitly asked to use an iterative one. That usually means Breadth-First Search (BFS). 🔹 Hint 3: Use Level Order Traversal Think of this like: * Traverse the tree level by level (BFS). * The first time you encounter a leaf node, you can return the current depth — that’s the minimum. 🔹 Hint 4: Use a Queue BFS needs a queue. Each item in the queue can be: * a pair of [node, depth], so we track depth along with the node. ✅ JavaScript Solution ``` class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } } function minTreeDepth(root) { if (!root) return 0; const queue = []; queue.push([root, 1]); // Pair of [node, depth] while (queue.length > 0) { const [node, depth] = queue.shift(); // Check if it's a leaf if (!node.left && !node.right) { return depth; } if (node.left) queue.push([node.left, depth + 1]); if (node.right) queue.push([node.right, depth + 1]); } return 0; // This line shouldn't be hit if the tree is valid } ``` ⏱ Time & Space Complexity ✅ Time Complexity: O(n) Every node is visited once. ✅ Space Complexity: O(n) In worst case (e.g. complete binary tree), queue holds all nodes at a level → up to n/2 nodes. 🔁 Alternate Approaches 🔸 Recursive DFS (Not Required, But Worth Knowing): ``` function minTreeDepthRecursive(root) { if (!root) return 0; if (!root.left) return 1 + minTreeDepthRecursive(root.right); if (!root.right) return 1 + minTreeDepthRecursive(root.left); return 1 + Math.min(minTreeDepthRecursive(root.left), minTreeDepthRecursive(root.right)); } ``` * Useful when space is limited, and depth is low. * Worst-case space = O(h), where h = height of tree.

Answer 2

🔹 Hint 1: What is the Deepest Node? The deepest node is the last node encountered in level-order traversal (BFS) — because BFS processes the tree level by level from left to right. 🔹 Hint 2: Why Not Use DFS? While Depth-First Search (DFS) can be used, it requires more logic to keep track of depth. Breadth-First Search (BFS) naturally gives the deepest node as the last visited node. 🔹 Hint 3: Use a Queue BFS uses a queue. Start from the root, and enqueue left and right children as you go. The last dequeued node will be the deepest. ✅ JavaScript Solution (Iterative) ``` class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } } function findDeepestNode(root) { if (!root) return null; let queue = [root]; let current = null; while (queue.length > 0) { current = queue.shift(); if (current.left) queue.push(current.left); if (current.right) queue.push(current.right); } return current; } ``` ⏱ Time and Space Complexity Time Complexity: O(n) — every node is visited once. Space Complexity: O(n) — in the worst case, queue holds all nodes at the widest level. 🔁 Alternate Approaches 🔸 DFS with Depth Tracking If you'd like to use DFS instead, you can track (node, depth) in a recursive call: ``` function findDeepestNodeDFS(root) { let maxDepth = -1; let deepest = null; function dfs(node, depth) { if (!node) return; if (depth > maxDepth) { maxDepth = depth; deepest = node; } dfs(node.left, depth + 1); dfs(node.right, depth + 1); } dfs(root, 0); return deepest; } ``` This approach is more flexible if you want to collect nodes at specific depths.

Answer 3

🔹 Hint 1: Understand Node Structure A node in a doubly-linked list has: ``` class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } ``` You can go forward (next) and backward (prev). 🔹 Hint 2: Position is 1-Based If pos is 1, you're deleting the head node. Make sure to update the head and adjust the new head's .prev. 🔹 Hint 3: Traverse Carefully Use a loop to move to the node at the given position. ``` let current = head; let count = 1; while (current !== null && count < pos) { current = current.next; count++; } ``` If current is null, the position is out of bounds. 🔹 Hint 4: Handle the Links Properly Once you find the node to delete, rewire its prev and next pointers: * If there's a previous node, update prev.next * If there's a next node, update next.prev ✅ JavaScript Solution ``` class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } function deleteAtPosition(head, pos) { if (!head || pos <= 0) return head; let current = head; let count = 1; // Traverse to the node at position `pos` while (current && count < pos) { current = current.next; count++; } // If position is out of range if (!current) return head; // If it's the head node if (!current.prev) { head = current.next; if (head) head.prev = null; } else { current.prev.next = current.next; if (current.next) { current.next.prev = current.prev; } } return head; } ``` ⏱ Time and Space Complexity Time Complexity: O(n) – you may traverse up to n nodes. Space Complexity: O(1) – in-place operations. 🔁 Alternate Approach If this were a circular doubly linked list, you'd need to check for looping nodes and possibly handle a tail pointer. Otherwise, this linear approach is standard.

Answer 4

🔹 Hint 1: Understand Valid Paths Think of each path as a sequence of connected nodes. A valid path can start and end at any two nodes and pass through parent-child edges only once per node. 🔹 Hint 2: Use Postorder Traversal To find the best path passing through or under each node, use postorder traversal (left-right-root). At each node, calculate: * leftMax: best path sum from left subtree * rightMax: best path sum from right subtree 🔹 Hint 3: Track Global Maximum At every node, compute: `maxAtNode = leftMax + node.val + rightMax` Update a global variable maxSum if maxAtNode is greater. 🔹 Hint 4: Return One-Sided Path for Recursion When returning to the parent, you can only choose one path direction (left or right), so return: `return node.val + Math.max(leftMax, rightMax)` ✅ JavaScript Solution ``` class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } } function maxSumPath(root) { let maxSum = Number.MIN_SAFE_INTEGER; function helper(node) { if (!node) return 0; // Recursively get max from left and right const left = helper(node.left); const right = helper(node.right); // Calculate sum passing through current node const currentMax = node.data + left + right; // Update global max if this is higher maxSum = Math.max(maxSum, currentMax); // Return the one-sided path for parent use return node.data + Math.max(left, right); } helper(root); // Return the maximum path sum found return maxSum; } ``` ⏱ Time and Space Complexity Time: O(n) – Each node is visited once. Space: O(h) – For recursion stack, h is the height of the tree. 🔁 Alternate Approach If you're only allowed to move downwards, then you only compute root-to-leaf max paths — a different problem. In this case, since any direction is allowed, the above recursive approach with postorder traversal is ideal.

Answer 5

🔹 Hint 1: Use Two-Pointer Technique Try to find the middle of the list using slow and fast pointers. * Slow moves one step. * Fast moves two steps. When fast reaches the end, slow will be at the middle. 🔹 Hint 2: Reverse the Second Half Once you find the middle, reverse the second half of the list. This lets you compare it with the first half. 🔹 Hint 3: Compare Halves Compare node-by-node between the first half and the reversed second half. 🔹 Hint 4: Restore (Optional) Optionally, you can restore the list back to its original form if needed (e.g., in production code or interviews). ✅ JavaScript Solution ``` class ListNode { constructor(data) { this.data = data; this.next = null; } } function isListPalindrome(head) { if (!head || !head.next) return true; // Step 1: Find middle using slow and fast pointers let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } // Step 2: Reverse second half let prev = null, curr = slow; while (curr) { let next = curr.next; curr.next = prev; prev = curr; curr = next; } // Step 3: Compare both halves let left = head, right = prev; while (right) { if (left.data !== right.data) return false; left = left.next; right = right.next; } return true; } ``` ⏱ Time and Space Complexity * Time Complexity: O(n) * One traversal to find the middle * One traversal to reverse * One traversal to compare Space Complexity: O(1) * Reversal and comparison are done in-place 🔁 Alternate Approach 💡 Approach: Copy to Array Copy list values to an array and check if it's a palindrome. Time: O(n) Space: O(n) ``` function isListPalindromeArray(head) { const vals = []; while (head) { vals.push(head.data); head = head.next; } for (let i = 0, j = vals.length - 1; i < j; i++, j--) { if (vals[i] !== vals[j]) return false; } return true; } ``` ✅ This is easier to implement, but less optimal in space.

Answer 6

🔹 Hint 1: Use Two Pointers Use two pointers: fast and slow. Initially, move fast ahead by n steps. 🔹 Hint 2: Move Both Until Fast Reaches End Then move both fast and slow one step at a time until fast.next is null. 🔹 Hint 3: Delete the Node At this point, slow is right before the node to be removed. Update its next pointer to skip that node. 🔹 Hint 4: Handle Edge Case What if the node to remove is the head? For example, when n == length of the list. ✅ JavaScript Solution ``` class ListNode { constructor(data) { this.data = data; this.next = null; } } function removeNthFromEnd(head, n) { // Create a dummy node to simplify edge cases like deleting the head let dummy = new ListNode(0); dummy.next = head; let fast = dummy; let slow = dummy; // Step 1: Move fast ahead by n + 1 steps for (let i = 0; i <= n; i++) { fast = fast.next; } // Step 2: Move fast to the end, maintaining the gap while (fast !== null) { fast = fast.next; slow = slow.next; } // Step 3: Delete the nth node from the end slow.next = slow.next.next; return dummy.next; } ``` 🔁 Alternate Approach (Using Array) * Traverse the list and store all nodes in an array. * Find the node at index length - n and remove it. ``` function removeNthFromEndArray(head, n) { const nodes = []; let curr = head; while (curr) { nodes.push(curr); curr = curr.next; } const indexToRemove = nodes.length - n; if (indexToRemove === 0) { return head.next; } const prev = nodes[indexToRemove - 1]; prev.next = prev.next.next; return head; } ``` Time: O(n) Space: O(n) (due to array)

Answer 7

🔹 Hint 1: What’s the brute-force approach? Count frequencies using a HashMap or object. But that requires O(n) extra space — which breaks the constraint. 🔹 Hint 2: How to use array indices to track frequencies? Since all elements are between 0 and n-1, you can use the array itself to store frequency information. 🔹 Hint 3: How to encode frequency in the array without losing original values? Add n (array size) to the value at index = element's value for each occurrence. 🔹 Hint 4: After processing, how do you retrieve the frequencies? The frequency of i is Math.floor(arr[i] / n). 🔹 Hint 5: How to identify max frequency and corresponding element? Track max frequency and index while traversing. ✅ JavaScript Solution ``` function maxRepeating(arr) { const n = arr.length; // Step 1: Encode frequency information in the array itself for (let i = 0; i < n; i++) { const index = arr[i] % n; // Original value (in case arr[i] was modified) arr[index] += n; } // Step 2: Find the max frequency element let maxFreq = 0; let maxElement = 0; for (let i = 0; i < n; i++) { const freq = Math.floor(arr[i] / n); if (freq > maxFreq) { maxFreq = freq; maxElement = i; } } // (Optional) Restore original array values if needed for (let i = 0; i < n; i++) { arr[i] = arr[i] % n; } return maxElement; } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) (Two passes over the array) Space Complexity: O(1) (In-place frequency encoding, no extra data structures) 🔁 Alternate Approaches 1. HashMap / Object Frequency Count Easy to implement Time O(n), Space O(n) Violates O(1) space constraint 2. Sorting + Counting Sort array and count repetitions in a single pass. Time O(n log n), Space O(1) or O(n) depending on sorting. Not optimal for this problem.

Answer 8

🔹 Hint 1: What does a cycle in a linked list mean? It means some node’s next points back to a previously visited node. 🔹 Hint 2: How to detect revisiting nodes? Keep track of visited nodes using a data structure (like a Set). 🔹 Hint 3: What data structure can store visited nodes efficiently? Use a JavaScript Set to store nodes you’ve seen. 🔹 Hint 4: How to iterate and detect cycle? Traverse the list: * For each node, check if it is already in the Set. * If yes, cycle detected! Return true. * If no, add the node to the Set and move on. * If you reach the end (null), no cycle → return false. 🔹 Hint 5: What if the list is empty? Return false immediately (no nodes, no cycle). ✅ JavaScript Solution ``` function hasCycle(head) { if (!head) return false; const visitedNodes = new Set(); let current = head; while (current !== null) { if (visitedNodes.has(current)) { return true; // Cycle detected } visitedNodes.add(current); current = current.next; } return false; // No cycle found } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) — each node visited once. Space Complexity: O(n) — storing visited nodes in a Set. 🔁 Alternate Approaches 1. Floyd’s Cycle Detection (Tortoise and Hare) Uses two pointers moving at different speeds. Detects cycle in O(n) time and O(1) space. More optimal but slightly trickier to understand. ``` function hasCycle(head) { if (!head || !head.next) return false; let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; // Move 1 step fast = fast.next.next; // Move 2 steps if (slow === fast) { return true; // Cycle detected } } return false; // Fast reached end, so no cycle } ``` 📈 Time & Space Complexity Time Complexity: O(n) Both pointers traverse the list only once (in worst case). Space Complexity: O(1) No extra space used!

Answer 9

🔹 Hint 1: What happens when k > arr.length? You can rotate by k % n, because rotating n times puts the array back to its original state. 🔹 Hint 2: Can we rotate by reversing parts of the array? Yes! This is a common trick: * Reverse the first k elements * Reverse the remaining n - k elements * Reverse the entire array 🔹 Hint 3: Why does the triple reverse work? It shuffles the segments into the desired order, without using extra memory — just swaps. 🔹 Hint 4: Handle edge cases What if k == 0, or k == arr.length? Those are no-op rotations. Use a guard condition. ✅ JavaScript Implementation ``` function rotateLeft(arr, k) { const n = arr.length; if (n === 0 || k % n === 0) return; // Nothing to rotate k = k % n; // Handle cases when k > n // Helper to reverse a subarray in place function reverse(start, end) { while (start < end) { [arr[start], arr[end]] = [arr[end], arr[start]]; start++; end--; } } // Step 1: Reverse first k elements reverse(0, k - 1); // Step 2: Reverse the rest reverse(k, n - 1); // Step 3: Reverse entire array reverse(0, n - 1); } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) Every element is touched at most 3 times. Space Complexity: O(1) All operations are in-place.

Answer 10

🔹 Hint 1: Understand how counterclockwise rotation looks If you take a 3x3 matrix and rotate it counterclockwise, rows become columns (in reverse). Example: Before: ``` 1 2 3 4 5 6 7 8 9 ``` After counterclockwise rotation: ``` 3 6 9 2 5 8 1 4 7 ``` 🔹 Hint 2: Can we break this into steps? Yes! You can break the rotation into two simpler transformations: 1. Transpose the matrix 2. Reverse each column (vertical flip) 🔹 Hint 3: How do you transpose in-place? Swap matrix[i][j] with matrix[j][i] for all i < j. 🔹 Hint 4: How do you reverse columns in-place? For each column, swap top and bottom elements moving toward the center. ✅ JavaScript Solution ``` function rotateSquareImageCCW(matrix) { const n = matrix.length; // Step 1: Transpose the matrix for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Step 2: Reverse each column for (let col = 0; col < n; col++) { let top = 0; let bottom = n - 1; while (top < bottom) { [matrix[top][col], matrix[bottom][col]] = [matrix[bottom][col], matrix[top][col]]; top++; bottom--; } } } ``` ⏱️ Time and Space Complexity Time Complexity: O(n^2) Transposing and reversing both touch each element once. Space Complexity: O(1) Done in-place without extra memory.

Answer 11

🔹 Hint 1: What does the problem really ask? It wants the number of nodes from root to the target (including both). This is also known as the depth of the node + 1 (because we count nodes, not edges). 🔹 Hint 2: How do we find a node in a binary tree? You can use DFS (preorder traversal) or BFS to search the tree. 🔹 Hint 3: Use recursion and check subtrees If the node is not at the current root, try searching in the left and right subtrees recursively. 🔹 Hint 4: What should your recursive function return? The distance if the node is found, otherwise -1 or 0 to indicate "not found". ✅ JavaScript Solution ``` function pathLengthFromRoot(root, key) { if (root === null) return 0; // empty tree function dfs(node, depth) { if (node === null) return -1; if (node.val === key) return depth; // search in left and right subtrees let left = dfs(node.left, depth + 1); if (left !== -1) return left; return dfs(node.right, depth + 1); } return dfs(root, 1); // start at depth 1 (counting nodes, not edges) } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) You may visit every node in the worst case (especially if target is a leaf). Space Complexity: O(h) Where h is the height of the tree (due to recursion stack). 🔁 Alternate Approach (Iterative BFS) You could also solve this using Breadth-First Search (BFS) with a queue: * Track each node with its depth. * Stop when you find the key. ``` function pathLengthFromRoot(root, key) { if (!root) return 0; let queue = [{ node: root, depth: 1 }]; while (queue.length) { let { node, depth } = queue.shift(); if (node.val === key) return depth; if (node.left) queue.push({ node: node.left, depth: depth + 1 }); if (node.right) queue.push({ node: node.right, depth: depth + 1 }); } return 0; // fallback } ```

Answer 12

🔹 Hint 1: What does “kth smallest” mean in a BST? In a BST, in-order traversal (Left → Root → Right) visits nodes in sorted order. 🔹 Hint 2: Can we stop in-order traversal early? Yes! You don’t need to traverse the entire tree. Stop when you reach the kth node during the in-order process. 🔹 Hint 3: What data do we need to track? Keep a counter during traversal to know when you've reached the kth node. 🔹 Hint 4: Should we use recursion or iteration? Either works. Start with recursive in-order traversal for simplicity. ✅ JavaScript Solution ``` function kthSmallest(root, k) { let count = 0; let result = null; function inOrder(node) { if (!node || result !== null) return; inOrder(node.left); count++; if (count === k) { result = node.val; return; } inOrder(node.right); } inOrder(root); return result; } ``` ⏱️ Time & Space Complexity Time Complexity: O(h + k) * In the worst case, you might go down h levels (tree height) and visit k nodes. * Balanced BST → O(log n + k), Skewed BST → O(n) Space Complexity: O(h) * For recursion stack in worst case. 🔁 Alternate Approaches 1. Iterative In-Order Traversal (Using stack) Avoids recursion, may be preferred in environments with limited stack size. ``` function kthSmallest(root, k) { const stack = []; while (true) { while (root) { stack.push(root); root = root.left; } root = stack.pop(); k--; if (k === 0) return root.val; root = root.right; } } ``` Time Complexity: O(h + k) Space Complexity: O(h) 2. Augmented BST (With subtree size) – Advanced * Augment nodes with a count of nodes in left subtree. * Allows O(log n) selection. * Useful for repeated queries or large datasets.

Answer 13

🔹 Hint 1: What is a circular linked list? In a circular linked list, the last node points back to the head, not to null. So it "wraps around." 🔹 Hint 2: What does “insert at tail” mean? It means we insert the new node just before the head, and update the last node's next pointer to point to the new node, and the new node’s next should point to the head. 🔹 Hint 3: What if the list is empty? If the list is empty (head === null), your new node becomes the only node in the list, and its .next should point to itself. 🔹 Hint 4: How to find the last node? Traverse the list until you find a node where current.next === head. ✅ JavaScript Solution ``` class ListNode { constructor(val) { this.val = val; this.next = null; } } function insertAtTail(head, value) { const newNode = new ListNode(value); if (!head) { newNode.next = newNode; // Single node points to itself return newNode; } let current = head; while (current.next !== head) { current = current.next; } current.next = newNode; newNode.next = head; return head; } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) You may need to traverse the entire list to find the last node. Space Complexity: O(1) Constant space used (excluding the new node). 🔁 Alternate Approach (with Tail Pointer) If you maintained a tail pointer, inserting at the tail would be O(1) time! ``` function insertAtTailWithTailPointer(tail, value) { const newNode = new ListNode(value); if (!tail) { newNode.next = newNode; return newNode; // this is now the tail and head } newNode.next = tail.next; // newNode points to head tail.next = newNode; // old tail points to newNode return newNode; // return new tail } ```

Answer 14

🔹 Hint 1: Can you use two pointers? Yes! This is a classic two-pointer technique. 🔹 Hint 2: Move one pointer n steps ahead first. Keep two pointers, say first and second. Move first ahead by n nodes. 🔹 Hint 3: Then move both pointers together. Once first is n steps ahead, move both pointers one step at a time until first hits the end. 🔹 Hint 4: Where will the second pointer be? At the nth node from the end! ✅ JavaScript Solution ``` class ListNode { constructor(val) { this.val = val; this.next = null; } } function getNthFromEnd(head, n) { let first = head; let second = head; // Move first pointer n steps ahead for (let i = 0; i < n; i++) { if (first === null) return null; // in case n is invalid first = first.next; } // Move both pointers until first reaches the end while (first !== null) { first = first.next; second = second.next; } return second; } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) — traverse the list once. Space Complexity: O(1) — only constant memory used.

Answer 15

🔹 Hint 1: What traversal method visits nodes level-by-level? Use Breadth-First Search (BFS) — it explores all nodes at one level before going deeper. 🔹 Hint 2: What data structure helps with BFS? A queue is perfect for this — you enqueue the left and right children as you go. 🔹 Hint 3: Start from the root Add the root node to the queue. Then repeatedly dequeue, record its value, and enqueue its children. 🔹 Hint 4: Stop when the queue is empty That means you've visited all nodes. ✅ JavaScript Solution ``` class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } function levelOrderTraversal(root) { const result = []; if (!root) return result; const queue = [root]; while (queue.length > 0) { const current = queue.shift(); // dequeue result.push(current.val); if (current.left) queue.push(current.left); if (current.right) queue.push(current.right); } return result; } ``` ⏱️ Time and Space Complexity Time Complexity: O(n) — where n is the number of nodes. Space Complexity: O(n) — worst-case queue size when the tree is balanced and the bottom level is half the total nodes. ✨ Alternate Approaches Return Levels as Nested Arrays If asked to return values grouped by levels: e.g., [[1], [2,3], [4,5]] DFS with Depth Tracking Can simulate level order using recursive DFS by tracking the depth — but it's trickier and not space-optimal.

Answer 16

🔹 Hint 1: What makes BSTs special? In a BST: * Left subtree nodes have smaller values than the current node. * Right subtree nodes have larger values than the current node. 🔹 Hint 2: Where is the smallest element? The leftmost node in a BST is always the smallest. 🔹 Hint 3: What traversal should you do? Keep going left until you reach a node with no left child. 🔹 Hint 4: How do you implement it? You can use either recursion or iteration. Iteration is simpler here and avoids call stack usage. ✅ JavaScript Solution ``` class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } function findMinInBST(root) { if (!root) return null; let current = root; while (current.left !== null) { current = current.left; } return current; // returns the node itself } ``` ⏱️ Time and Space Complexity Time Complexity: Best case: O(1) (if root is min) Worst case: O(h) where h = height of tree ⇒ O(log n) in balanced BST, O(n) in skewed tree. Space Complexity: O(1) using iteration O(h) if using recursion (due to call stack) ✨ Alternate Approaches ✅ Recursive Version (less preferred due to call stack usage): ``` function findMinRecursive(root) { if (!root || !root.left) return root; return findMinRecursive(root.left); } ```

Answer 17

🔹 Hint 1: When do intervals overlap? Two intervals [a, b] and [c, d] overlap if c ≤ b. 🔹 Hint 2: Should you sort the intervals? Yes! Sort the intervals by their start time first. This makes merging easier because overlapping intervals will appear next to each other. 🔹 Hint 3: How to merge overlapping intervals? Start with the first interval. For each next interval: * If it overlaps with the current merged interval, extend the current interval. * If it doesn't, add the current to result and move to the next. 🔹 Hint 4: Track your merge result Use an array (or ArrayList) to keep track of merged intervals. ✅ JavaScript Solution ``` class Interval { constructor(start, end) { this.start = start; this.end = end; } } function mergeIntervals(intervals) { if (!intervals || intervals.length === 0) return []; // Step 1: Sort by start intervals.sort((a, b) => a.start - b.start); const merged = []; let current = intervals[0]; for (let i = 1; i < intervals.length; i++) { const next = intervals[i]; if (next.start <= current.end) { // Overlap: merge current.end = Math.max(current.end, next.end); } else { // No overlap: push current and move on merged.push(current); current = next; } } // Add the last interval merged.push(current); return merged; } ``` ⏱️ Time & Space Complexity Time Complexity: O(n log n) — for sorting the intervals. O(n) — to merge the intervals. Space Complexity: O(n) — for output array.

Answer 18

🔹 Hint 1: Can you use recursion? While recursion is common for tree problems, this question specifically asks for iteration. 🔹 Hint 2: How can we explore all nodes iteratively? Use a queue (FIFO) to do a Breadth-First Search (BFS). This ensures we visit every node. 🔹 Hint 3: What data structure can help? A queue can be used to store nodes level-by-level. Add the left and right children of each node as you process them. 🔹 Hint 4: What to do at each step? While traversing: * Dequeue a node. * Add its value to the total sum. * Enqueue its left and right children (if any). ✅ JavaScript Solution ``` class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } function sumOfTreeIterative(root) { if (!root) return 0; let sum = 0; const queue = [root]; while (queue.length > 0) { const current = queue.shift(); // Dequeue sum += current.val; if (current.left) { queue.push(current.left); } if (current.right) { queue.push(current.right); } } return sum; } ``` ⏱️ Time & Space Complexity Time Complexity: O(n) Every node is visited once. Space Complexity: O(n) In the worst case, all nodes are stored in the queue (e.g., complete binary tree). ✨ Alternate Approaches ✅ Recursive approach (for comparison): ``` function sumOfTreeRecursive(node) { if (!node) return 0; return node.val + sumOfTreeRecursive(node.left) + sumOfTreeRecursive(node.right); } ``` But the problem specifically asks for iterative approach.

Answer 19

🔹 Hint 1: Understand BST property In a BST, for any node: * All values in the left subtree are less than the node. * All values in the right subtree are greater than or equal to the node. 🔹 Hint 2: What are the base cases? If the root is null, then return a new node with the value — this becomes the root of the tree. 🔹 Hint 3: How to decide where to go? * If val < root.val, insert into the left subtree. * If val >= root.val, insert into the right subtree. 🔹 Hint 4: Recursive or Iterative? You can solve this using recursion or iteration. Start with recursion for simplicity. ✅ JavaScript Solution (Recursive Approach) ``` class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } function insertIntoBST(root, val) { if (root === null) { return new TreeNode(val); } if (val < root.val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; } ``` ⏱️ Time and Space Complexity Time Complexity: O(h) where h is the height of the tree. In the worst case (unbalanced tree), h = n. For balanced trees, h = log n. Space Complexity: Recursive: O(h) due to the call stack. Iterative (see below): O(1) if we ignore the stack overhead. 🔁 Alternate Iterative Version ``` function insertIntoBSTIterative(root, val) { const newNode = new TreeNode(val); if (!root) return newNode; let current = root; while (true) { if (val < current.val) { if (!current.left) { current.left = newNode; break; } current = current.left; } else { if (!current.right) { current.right = newNode; break; } current = current.right; } } return root; } ```

Answer 20

🔹 Hint 1: Understand Inorder Traversal Inorder traversal of a BST gives values in ascending order. Use this property to your advantage. 🔹 Hint 2: Use the Range to Prune Subtrees Because it’s a BST: * If current node value < a, only look in the right subtree. * If current node value > b, only look in the left subtree. * If node value is within [a, b], add it and explore both subtrees. 🔹 Hint 3: Build a Helper Function Use a recursive function that: * Traverses left/right based on range conditions. * Adds node values to the result list only if within range. ``` class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } function rangeInBST(root, a, b) { const result = []; function inorder(node) { if (!node) return; // Explore left subtree if needed if (node.val > a) { inorder(node.left); } // Add current node if in range if (node.val >= a && node.val <= b) { result.push(node.val); } // Explore right subtree if needed if (node.val < b) { inorder(node.right); } } inorder(root); return result; } ``` ⏱ Time and Space Complexity Time Complexity: O(k + log n) average case, where k is the number of nodes in range. In worst case (unbalanced tree), this can be O(n). Space Complexity: O(h) for the recursive call stack, where h is height of the tree. O(k) for the result array. 🔁 Alternate Approach: Iterative Inorder (Optional) If recursion is not allowed (e.g., interview constraint), an iterative solution using a stack can be implemented. ``` function rangeInBST(root, a, b) { const stack = []; const result = []; let current = root; while (stack.length > 0 || current !== null) { // Go as left as possible while (current !== null) { stack.push(current); current = current.left; } current = stack.pop(); // Process current node only if it's in range if (current.val >= a && current.val <= b) { result.push(current.val); } // If value > b, no need to go right (values too big) if (current.val > b) { current = null; // skip right subtree } else { current = current.right; } } return result; } ```

Answer 21

🔹 Hint 1: Understand the Pattern We are allowed to buy and sell as often as needed, as long as it follows a buy-sell-buy-sell... pattern. 🔹 Hint 2: Track Upward Trends If today's price is less than tomorrow's, there's a profit to be made by: * buying today and * selling tomorrow. Repeat this for every such increase. 🔹 Hint 3: Greedy Works! You don’t need to track specific buy/sell points. Just add every price increase as potential profit. ✅ JavaScript Solution (Greedy) ``` function maxProfit(prices) { if (!prices || prices.length < 2) return 0; let profit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1]; // buy at i-1, sell at i } } return profit; } ``` 🕓 Time and Space Complexity Time Complexity: O(n) Space Complexity: O(1)

Answer 22

🔹 Hint 1: Understand the Input Format The tree is serialized in level-order traversal: Each value is separated by a comma. "*" means the node is null. Example: "1,2,3,*,*,4,5" Visualized as: ``` 1 / \ 2 3 / \ 4 5 ``` 🔹 Hint 2: Use a Queue to Reconstruct This is the reverse of level-order traversal. Use a queue to: * Dequeue the current parent node, * Read the next two tokens for its left and right children. 🔹 Hint 3: Watch for Nulls When you see "*", skip creating a node. This ensures structure remains correct. ``` class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } } function decompressTree(dataString) { if (!dataString || dataString.length === 0) return null; const values = dataString.split(','); if (values[0] === '*') return null; const root = new TreeNode(parseInt(values[0])); const queue = [root]; let index = 1; while (queue.length > 0 && index < values.length) { const current = queue.shift(); // Process left child if (values[index] !== '*') { const leftNode = new TreeNode(parseInt(values[index])); current.left = leftNode; queue.push(leftNode); } index++; // Process right child if (index < values.length && values[index] !== '*') { const rightNode = new TreeNode(parseInt(values[index])); current.right = rightNode; queue.push(rightNode); } index++; } return root; } ``` 🕓 Time and Space Complexity Time Complexity: O(n) — where n is the number of nodes represented in the string. Space Complexity: O(n) — queue stores up to n/2 nodes in worst-case (last level). 🔁 Alternate Approaches While BFS (queue-based) is the cleanest for level-order decompression: * A recursive approach works for preorder/inorder-based serializations but is not suitable here. * You could validate the structure first using a heap-like index pattern but that’s more complex and unnecessary.

Answer 23

🔹 Hint 1: What Are You Counting? You're counting how many different paths can be taken to reach the bottom-right cell from the top-left. Allowed moves: * Right ➡️ * Down ⬇️ 🔹 Hint 2: Use Recursion First You can think recursively: * At cell (i, j), total paths = paths from right cell + paths from bottom cell. This leads to a recursive formula: `countPaths(i, j) = countPaths(i+1, j) + countPaths(i, j+1)` But this approach has exponential time without memoization. 🔹 Hint 3: Dynamic Programming (Tabulation) Use a 2D DP table where dp[i][j] represents number of ways to reach cell (i, j). Base Case: * Only 1 way to reach any cell in the first row or first column (all right or all down moves). Transition: `dp[i][j] = dp[i-1][j] + dp[i][j-1]` ✅ JavaScript Solution (Dynamic Programming) ``` function countPaths(m, n) { const dp = Array.from({ length: m }, () => Array(n).fill(1)); // Fill first row & column with 1 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // Sum of top and left } } return dp[m - 1][n - 1]; } ``` 🔄 Alternate Approach: Combinatorics (Most Optimal) Each path consists of exactly (m-1) downs and (n-1) rights → a total of (m+n-2) moves. So the number of such combinations is: `C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)` ``` function countPaths(m, n) { const factorial = (num) => { let res = 1; for (let i = 2; i <= num; i++) res *= i; return res; }; return factorial(m + n - 2) / (factorial(m - 1) * factorial(n - 1)); } ``` This is O(min(m, n)) time using iterative factorial. ⏱ Time and Space Complexity Dynamic Programming: Time: O(m * n) Space: O(m * n) (can be reduced to O(n) using a 1D array) Combinatorics: Time: O(min(m, n)) Space: O(1)

Lv.3 Flashcards

Lv.3 problems of Firecode.io (47 cards)