Amazon top 30

Question 1

Given a string s, return the longest palindromic substring in s. Input: “babad”, “abb”, “a”

Answer 1

1. BRUTE:
   
   • Consider all the possible combinations of substrings: O(N²)
   • For every combination, check if it is a palindrome: O(N)
   • TC: O(N³)
2. Optimization 1:
   
   • Recursion? String and its reverse.
   • If same, go on.
   • If different, reset to zero and two options: keep one index same, move another.
   • TC: O(N²)
   • SC: O(N²) + O(N)
3. Optimization 2:
   
   • Expand out from the middle: middle out.
   • For every index, form a palindrome towards both sides. Check both even and odd-length palindromes.
   • TC: O(N²)
   • SC: O(N) or O(1)

Question 2

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Answer 2

1. Have a map to store pairs.
2. Use of stack. Why? To check the order.
3. Traverse the string:
   
   • If found an opening bracket (check in map), append it to the stack.
   • If found a closing bracket, check if stack top is of the same type.
   • If not, return False.
   • If yes, pop and check further.
4. At the end of the loop:
   
   • If the stack is empty, it means every opening bracket had an encountered closing bracket in order.
5. Dry-run:
   
   • Valid: (())
   • Invalid: (() → At the end, the stack is not empty.
   • Invalid: ))) → Return False if no stack exists.
6. TC: O(N)
7. SC: O(N), storing all open brackets.

Question 3

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Answer 3

1. Approach
   
   • Take two lists at a time and merge them into one.
   • TC: O(k) * O(N)
2. Optimization
   
   • Use merge sort (Divide and Conquer) to merge lists.
   • Iterate over number k in 2 steps, take two lists at a time and merge them.
   • After every merge, add the list to mergedLists, then store it in lists.
   • After the first iteration, lists will get halved, and so on.
   • TC: O(N log k)
   • SC: O(1) (If merging in place) or O(N) (If using extra space for merging)

Question 4

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Answer 4

1. Create sets for rows, columns, and each of the nine 3x3 squares.
2. Iterate rows to check for duplicates.
3. Iterate columns to check for duplicates.
4. Iterate the whole matrix and map each cell to one of the nine squares.
   
   • Representation of the nine squares (key) will be: (r // 3, c // 3) using integer division (floor).
   • Example keys: (0,0), (0,1), (0,2), (1,0), (1,1), etc.
   • Each key corresponds to a set to track values within that 3x3 grid.
5. Check for duplicates in rows, columns, and squares while iterating.
6. Time Complexity: O(9X9)
7. Space Complexity: O(9 + 9 + 9) = O(1) (Constant space usage for tracking 9 rows, 9 columns, and 9 squares).

Question 5

Binary Heap Time Complexities

Answer 5

Binary Heap (Min-Heap / Max-Heap)
Insert (Push): O(log n)
Delete (Pop): O(log n)
Get Min/Max: O(1)
Build Heap (Heapify): O(n)
Heap Sort: O(n log n)
Decrease Key: O(log n)
Merge Heaps: O(n)

Question 6

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Answer 6

Notes: Minimum Path Sum in a Grid
Input: A grid of numbers.
Constraints: Allowed moves are right and down only.
Output: Find the path with the minimum sum.
Approach
Explore all possible paths.
Use a decision tree where each node represents a cell.
Time & Space Complexity (Brute Force)
Time Complexity: O(2(M+N))O(2^{(M+N)}) due to exhaustive recursion.
Space Complexity: O(M+N)O(M+N) (recursion depth).
Optimization: Memoization (Dynamic Programming)
Store results of overlapping subproblems.
Time Complexity: O(M×N)O(M \times N).
Space Complexity: O(M×N)O(M \times N).

Question 7

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Answer 7

1. Intuition
   Pick numbers as we go down the recursion call.
   Rotate numbers at a level.
2. Pseudo Code
   Function to get permutation (visited set, temporary list):
   At base case: when visited set equals length of nums.
   Append it to answer and return.
   At every index, loop through the list of numbers to decide whether or not to take the number.
   If not visited, then take it:
   Once taken, call the recursive function.
   After the call, remove from the visited set and temporary number.
3. Time Complexity: O(N!)
   Space Complexity: O(N)

Question 8

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Answer 8

Store the first interval as the reference interval.
Start traversing from the 1st index.
Check the start and end of two intervals:
If the reference interval is on the left, add the reference interval to the result, update the reference, and move to the next iteration.
If the reference interval overlaps, merge the intervals to create a new reference and move to the next iteration.
If the reference interval is on the right, add the iterator interval to the result and move.
If the reference was towards the right throughout, add the reference interval to the result.
Return the result list of merged intervals.
Edge Case: If the list of intervals is empty, return an empty list.
Time Complexity: O(N)
Space Complexity: O(N)

Question 9

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Answer 9

OPTIMIZED:
Form a trie of words, Traverse the matrix, if the current cell letter matches a letter at root, Traverse the grid and trie simultaneously. be sure to unmark a cell so that it can be used in next ones.

2. 1. Traverse the matrix.
3. For every cell, start checking if the word is possible.
4. Utility function to check if the word is possible:
   3.1. Base case: if the index equals length of the word, return True
   3.2. If the current cell is out of bounds or does not match the character at the current index of the word, return False.
   3.3. Mark the cell as visited.
   3.4. Traverse the neighboring cells and recursively check:
   Get next cell using directions array
   If a neighbor returns True, return True immediately.
   If False, continue checking other neighbors.
   3.5. Unmark the cell as visited
   3.6. Return False by default
   If no valid path is found, return False.
5. Points to Remember:
   4.1. Base case (True): If the index reaches the length of the word, the word has been successfully formed.
   4.2. Base case (False): If row/column goes out of bounds, the letter does not match, or the cell has already been visited.
   4.3. Remember to remove the cell from the visited set, so that it is available for another path.
6. Overall Complexity:
   Time Complexity: O(MN4^L) (number of choices per step raised to the recursion depth).
   Space Complexity: O(L) (recursion stack depth is at most the length of the word).

Question 10

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Answer 10

1. Initialize limits: Start with [-∞, ∞] for the root.
2. Left subtree: Update right limit → [-∞, root-1].
3. Right subtree: Update left limit → [root+1, ∞].
4. Base case: If tree is None, return True.
5. Boundary check: If value is out of bounds, return False.
6. Recursive validation:
   Call function for the left subtree with updated limits.
   Call function for the right subtree with updated limits.
7. Time Complexity: O(N) (each node is visited once).
8. Space Complexity:
   O(N) (Worst case: skewed tree).
   O(log N) (Best case: balanced tree).
   Tree Levels Relation: 2^k - 1 = N, where k is the depth.

Question 11

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Answer 11

1. Input: Two tree roots.
2. Constraints:
   Very large node values.
   N ∈ [0, 100].
3. Output: Return True if both trees are identical, else False.
4. Base cases:
   If both trees are None, return True.
   If one tree is None but the other isn’t, return False.
   If root values differ, return False.
5. Recursive check:
   Compare left subtrees.
   Compare right subtrees.
   return right and left
6. Time Complexity: O(N) (visit each node once).
   Space Complexity:
   O(N) (Worst case: skewed tree).
   O(log N) (Best case: balanced tree).

Question 12

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Answer 12

TC: O(N), SC: O(N)
def checkSymmetry(tree1, tree2):
if not tree1 and not tree2:
                return True
            elif (tree1 and not tree2) or (tree2 and not tree1) or tree1.val!=tree2.val:
                return False
            
            left = checkSymmetry(tree1.left, tree2.right)
            right = checkSymmetry(tree1.right, tree2.left)
            return left and right

        if not root:
            return True
        return checkSymmetry(root.left, root.right)

~~~

```

Question 13

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Answer 13

# Level order traversal
        # queue.

        queue = deque()

        queue.append(root)
        res = []
        while(len(queue)>0):
            current_level = len(queue)
            level_nodes = []
            for i in range(current_level):
                curr = queue.popleft()
                if curr:
                    level_nodes.append(curr.val)
                    if curr.left:
                        queue.append(curr.left)
                    if curr.right:
                        queue.append(curr.right)
            if len(level_nodes)>0:
                res.append(level_nodes)
        return res

Question 14

Median of Two sorted arrays
TC: O(log(m+n))

Answer 14

1. Intuition: Find a cut in both arrays, such that, all elements (in both arrays) to the left are less than all elements on the right.
2. nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], i and j are the cuts.
3. i is cut in smaller array, then j = half-i
4. If the cut is not correct, readjust it
   4.1 if left1>right2:
   move i to left ; right = i-1
   4.2 if left2>right1:
   move i to right, left = i+1
5. Finding Median
   Total Length: Odd
   One more than right
   Answer: max(left1, left2)
   Total Length: Even
   Equal size
   Answer: (max(left1, left2) + min(right1, right2)) / 2

Question 15

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Answer 15

1. Problem
   Input: Grid of numbers
   Constraints: Can move right and down
   Output: Path with minimum sum of path
2. Approach:
   Explore all possibilities
   Decision tree: Each node will be a cell, can move right or down (left or up in reverse)
   Time & Space Complexity (Brute Force):
   TC: 2^{(M+N)}
   SC: O(M+N)
   Optimization: Memoization (DP):
   Store overlapping subproblems using DP
   TC: O(M×N)O(M \times N)
   SC: O(M×N)O(M \times N)

Question 16

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Answer 16

Given: Sorted Linked List
Output: Convert the above into Height Balanced BST
Approach:
Divide and Conquer
Middle element → Root
Left part → Left Subtree
Right part → Right Subtree
Steps:
Convert the list into an array of index-value pairs
Recursive function to form tree:
Current middle element → Root
Left part → [0 : index-1] → Left subtree
Right part → [index+1 : end] → Right subtree
If single element, form a node and return
Return root at the end
Time & Space Complexity:
TC: O(N)+O(N)
SC: O(N)+O(N)

Question 17

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Answer 17

1. Intuition:
2. Input: Perfect Binary Tree
   Info:
   Every parent has 2 children
   All leaves are on the same level
   Node: left, right, next
3. Task: Populate next pointer to its next node on the same level, otherwise None
4. Output: Return root of modified tree
5. Algorithm:
   Use Level Order Traversal with a Queue
   Traverse each level:
   Traverse each level using length of queue, currently
   Pop node from queue
   Keep track of previous node
   If previous exists, set previous.next = curr
   Push children into queue if they exist
   After loop, The last element on that level should point to None
   Return root at the end
6. Complexity:
   TC: O(N)
   SC: O(N)

Question 18

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Answer 18

1. Intuition
   Input: prices array, where price[i] represents the price on the ith day.
   Output: find the maximum profit that can be earned. If no profit is possible, return 0.
   Will there be negative values? No.
   Constraints: N can be up to 10510^5, and each price value can be up to 10410^4.
   You can only sell in the future after buying.
2. Brute Approach
   Consider all combinations of buy and sell.
   For each pair (i,j)(i, j) where j is in the future, calculate the profit and update the max profit if found.
   Time Complexity: O(N^2)
   Space Complexity: O(1)
3. Optimized Approach
   Find the maximum difference efficiently using two pointers.
   Start with two pointers, compute the difference, and update the right pointer.
   If a better buy opportunity is found where the right price is lower than the left price, update the left pointer to go to right position.

NOTE: One sided Index dependency problem, cumulative max/min problem.

Time Complexity: O(N)
Space Complexity: O(1)

Question 19

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Answer 19

1. Input: List of words (N), start word (m length) and end word. Find shortest sequence of words from start to end. Return 0 if not possible.
2. m is very less than N.
3. Algorithm: Convert the given list of words into Adjacency list. TC: O(N^2)
4. If K is very very Large. Don’t form the graph using double for-loop. Instead form it by generating all L patterns for every k words. O(k times L^2).
5. Finding adjacent will be L^2, because for every word generate all the patterns and check the patterns map for adjacent words.
6. Find shortest path from start word to end word using Djikstras shortest path algorithm. O(N^2).
7. TC: O(N^2), SC: O(N^2)

Question 20

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

Answer 20

1. Algorithm: Form the adjacency list
2. Start the shortest path from start node, using BFS, add the current node to the list and add to queue.
3. Once reached the end, add the combination to res, and so on.

Question 21

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Answer 21

findWords Function
Input: mxn board of characters, list of strings (words).
Output: List of words that are present in the board (can be formed by linking horizontal and vertical cells).
Constraint: Same letter may not be used more than once for that word.

BRUTE:
Algorithm
Traverse the word list
For every word, traverse the board and check if word can be formed or not, using DFS and simultaneous word character check.

Time & Space Complexity
k is length of words list.
TC: O(k * m * n * 4^L)
NOTE: K is extremely large
SC: O(m* n * k * 4^10)

OPTIMIZED: Trie + optimized DFS

Form a Trie of the words list
Traverse the board, check if any of the words can be formed or not, using DFS and trie traversal simultaneously.

TC: O(k * L + m * n * 4^L’)
TC: Trie formation + traversal and check

WHY Trie is optimized:

1. Prefix Sharing: The Trie allows shared prefixes among words to be explored once instead of redundantly for each word.
   EX: In Approach 1, if many words share prefixes (e.g., “apple”, “app”, “apply”), you’re still doing separate DFS searches for each of them — completely unaware they share the same starting structure.
   In Approach 2, the Trie stores shared prefixes once, so when you’re doing DFS from the board, you’re: Only visiting each character combination once per path, You don’t restart DFS from scratch for each word — you explore all possible prefixes in parallel through the Trie.
2. Reduced DFS Calls: Only one DFS per board cell, not per word, reducing total recursive calls.
3. No Repeated Work: If three words start with ‘ab’, and you start DFS from a cell with ‘a’ and its neighbor is ‘b’:
   Approach 1: You’d explore ‘a’ → ‘b’ three separate times (once per word).
   Approach 2: You explore ‘a’ → ‘b’ once, following the Trie — and discover all three words in one traversal.

Question 22

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Answer 22

1. Brute Approach: Sort the list as we add the number, Find the median value, based on odd/even length of the array.
2. Complexity: TC = O(NlogN), SC: O(N)
3. Optimized Approach: Two partitions (Two heaps). All element in small heap are LESS THAN all elements in large heap. At any time, small and large heaps count will only differ by at most 1.
4. The median would be either ODD count (min of large heap or max of small heap) or EVEN count (average of max of small and min of large heap)
5. Algorithm:
6. Add element to small heap
7. Check for consistency, all elements in small heap should be less than all elements in larger heap. If not, pop from small and insert it into larger heap.
8. If the count of both heaps differ by more than 1, restructure the heaps.
9. Restructuring function: If count of small heap is larger, then pop max and store it in large heap. If count of large heap is larger, then pop min and store it in small heap.
10. Find median: if small heap has more count then return max of small heap, if large heap has more count then return min of large heap. If equal, then return average of max of small heap and min of large heap.
11. IMPORTANT: While finding the median, do not pop the values, only peek or access them to calculate the median.

TC: O(LogN), SC: O(N)

Question 23

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Answer 23

Input: Array of numbers
Output: Longest increasing subsequence
Brute Force Approach
Get all the subsequences.
Check which ones are increasing, and then update the final result (longest length).
Time Complexity: O(2N⋅N)O(2^N \cdot N) (Correct)
Space Complexity: O(N)+O(2N)O(N) + O(2^N)
Optimization
While generating the subsequences, generate only the increasing ones. Otherwise, don’t.
Dynamic Programming (DP) Approach: Overlapping subproblems.
Time Complexity: O(N2)O(N^2) (Correct)
Space Complexity: O(N2)O(N^2) (Can be optimized to O(N)O(N) in some variations)

Question 24

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Answer 24

Input: A grid of islands (1) and water (0).
Output: Number of islands (groups of connected 1s covered by 0s).
Constraints: All edges are surrounded by water (0).
Algorithm
Initialize a visited grid.
Traverse the grid:
If a cell is not visited and contains 1, start forming an island using DFS.
Once DFS completes, increment the island count.
At the end of the loop, return the count of islands.
Time Complexity
O(m × n) → Every cell is visited only once.
Space Complexity
O(m × n) → In the worst case, all cells are visited and stored in the recursion stack (DFS) or queue (BFS).

Question 25

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Answer 25

1. Input: a, b → To take course a, you must first take course b (b -> a).
2. Output: Return True if you can finish all the courses.
3. Approach
   If there is no cycle in the Directed Acyclic Graph (DAG), then you can take all courses.
   Find if a cycle is present:
4. Generate the in-degree array.
   Append all zero in-degree nodes to the queue.
   Pop from the queue, reduce the in-degree of adjacent nodes.
   If in-degree becomes zero, add to the queue.
   At the end:
   If the queue is empty and the number of completed courses equals the total courses, return True.
   Otherwise, return False.

Why NOT Visited?: Because this is directed graph and you won’t visit same node again??
NO. Here we can skip it because, we have used indegree array, which indirectly acts as a visited array and only node which would not lead to an infinite loop are added to queue for processing.

We can safely avoid using visited set in Directed Acyclic (No cycle) graph.
5. Time Complexity
O(N) + O(V + E) (or O(N²) in a fully connected graph)
Space Complexity
O(N)

Question 26

According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.

Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything.

Answer 26

Input: A board of live (1) and dead (0) cells.
Conditions: Four possible state changes:
Live → Dead (fewer than 2 live neighbors).
Live → Live (2 or 3 live neighbors).
Live → Dead (more than 3 live neighbors).
Dead → Live (exactly 3 live neighbors).
Rules apply simultaneously → birth and death happen at the same time.
Output: No return value → update the board in-place.
Approach
Form a new empty board initialized to -1.
Traverse the board, check neighbors, and apply 4 rules to update the cell in the new board.
Copy all information from the old board to the new board.
Time and Spce Complexity
O(N²)
O(N²) → Used to store state changes
Optimization: In-Place Update
Instead of using a separate board, encode both old and new states in the same board:
3 → Live to Dead (fewer than 2 live neighbors).
4 → Live to Live (2 or 3 live neighbors).
5 → Live to Dead (more than 3 live neighbors).
6 → Dead to Live (exactly 3 live neighbors).
Check the original state before updating:
By default, store the new value while keeping track of the original state.
Final Pass: Traverse the board again and convert values:
3 → 0, 4 → 1, 5 → 0, 6 → 1.
Optimized Complexity
Time Complexity: O(N²) + O(N²) → O(N²)
Space Complexity: O(1)

Question 27

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Answer 27

Brute
Ocean, heights, 4 directions.
Output: List of coordinates from where water can flow to both oceans.
Traverse the grid of heights using BFS:
If it reaches the Pacific, add it to the Pacific Ocean set.
If it reaches the Atlantic, add it to the Atlantic Ocean set.
How?
Pacific: If it reaches the top row or left column.
Atlantic: If it reaches the bottom row or right column.
Time Complexity: O(N^2)∗O(N^2) = O(N^4)
Space Complexity: O(N^2)

Optimization:
Start at the edge row or column and mark the cells that are not visited and are reachable. that is add the cell to the Ocean set.

IMPORTANT: Visited/Ocean array won’t interfere with other coastal cell traversal because, the cell is marked as visited if it was possible to reach it with other path, the new traversal is opportunity to find a new path to reach the cell.

Do it for pacific and atlantic rows and columns, then find the coordinates that are present in both the sets.
Same set will be used for a row and column of an ocean.
Time Complexity: O(N^2).
Space Complexity: O(N^2).

Question 28

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Answer 28

Input: Root of a binary tree.
Output: Length of the longest path in the binary tree.
The longest path may not always pass through the root.
Approach:
Find the longest binary tree path.
While sending the value upwards, send the longest path from either subtree.
Recursive function (getBinaryPathLength):
Base case: If the node is None (leaf node), return 0.
Recursively traverse:
Go left.
Go right.
Compute the current maximum path:
curr = left + right + 1.
Update self.res with the maximum value.
Return the longest path upwards:
return 1 + max(left, right).
Final result:
getBinaryPathLength(root) is called.
The final result is self.res - 1 (to return the number of edges instead of nodes).

TC: O(N)
SC: O(N)

Question 29

Minesweeper

Answer 29

Minesweeper Board Update Notes

1. Board Representation
   Not revealed:
   ‘M’ → Mine
   ‘E’ → Empty cell (unrevealed)
   Revealed:
   ‘B’ → Blank (no adjacent mines)
   ‘1-8’ → Number of adjacent mines
   ‘X’ → Mine clicked (Game Over)
2. Click Rules
   If clicked on ‘M’ → Convert to ‘X’ (Game Over).
   If clicked on ‘E’:
   If adjacent mines exist, update with mine count (‘1-8’).
   If no adjacent mines, mark ‘B’ and recursively reveal adjacent cells.
3. Precompute Mine Information
   Create a mine_info grid to store the count of adjacent mines for each cell.
   Traverse the board and for each mine ‘M’, update its 8 neighbors.
4. Reveal Function (BFS)
   Uses a queue (BFS) to explore adjacent ‘E’ cells recursively.
   If a cell has no adjacent mines (mine_info[row][col] == 0), reveal its neighbors.
   If a cell has adjacent mines (mine_info[row][col] > 0), update it with the number.
5. Click Handling
   If mine (‘M’), set ‘X’ (Game Over).
   If empty (‘E’):
   If adjacent mines exist, update with mine count.
   If no adjacent mines, call reveal().
6. Helper Functions
   isValid(row, col): Checks if a cell is inside the board.
   reveal(row, col): Uses BFS to reveal blank areas.
   IMPORTANT: During BFS, use visited array, append the nr, nc to the visited array as soon as you add it to queue. WHY?? This will prevent duplicate addition of (nr, nc) before it is popped out and marked as visited.
7. Time Complexity
   O(N × M) (worst case, all cells revealed)
   O(N x M) space for mine_info and visited

This covers the main logic. Hope it helps with revision! 🚀

Question 30

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Answer 30

Numbers are distinct
Combination should be unique
Unlimited number of times
Output: list of unique combinations
Pick/Not Pick logic
Time Complexity (TC): O(2^N)
Space Complexity (SC): O(amount)
Optimization: Dynamic Programming to store overlapping subproblems
Time Complexity (TC): O(N * amount)
Space Complexity (SC): O(amount)

Question 31

Find prime numbers between a range, in SQRT(N) time

Answer 31

Sieve theorem to get Prime numbers
Mark 0 and 1 as prime
We have to iterate from 2 to max_limit (sqrt(right))
Find the multiples of iterator number, mark them as composite.
Finally Collect all the unmarked numbers as Primes

def getPrimes(left, right, primes):
            primes[0] = 0
						primes[1] = 0
            max_limit = int(math.sqrt(right))+1
         
            for i in range(2, max_limit):
                lower_limit = i*i
                for j in range(lower_limit, right+1, i):
                    primes[j] = 1
            res = []
            for i in range(left, right+1):
                if primes[i]==0:
                    res.append(i)
            return res

Question 32

LRU Cache

Answer 32

Doubly Linked List solution
LRU -> -> MRU
1. Initilize the LRU Cache class with capacity, dummy_head, dummy_tail and key_value_store (key: Node). Interlink dummy head and tail.
2. Create a Node class with key, value, next and prev attributes.
3. O(1) AddToEnd and DeleteNode helper functions needed.
3.1 DeleteNode method: Gets previous and next node. interlinks them, thus deleting the node. Delete the key:Node pair from key_value_store map.
3.2 AddNodeToEnd method: Add the node between dummy_tail and its prev node. Update two pointer of these. and add to two pointer of the new node. Add the node to key_value_store.
4. O(1) Get key function: Get the node from key_value_store. Delete it from LL. Add it end. return the node value.
5. O(1) Put key, value function: If key already exists: delete node from LL. Form a new node with key and value. Add it to the end of LL. If capacity overflow, remove dummy_head.next node.