Part 1: Arrays & Mathematics (Programs 1–4)
1. Find GCD of Array
• Goal: Find the greatest common divisor (largest number that divides all elements
without remainder) shared by all numbers in an array.
• Logic: It uses the Euclidean Algorithm. The property used is $GCD(a, b, c) =
GCD(GCD(a, b), c)$.
• Step-by-Step:
1. Take the first number as the initial resultGCD.
2. Iterate through the rest of the array, updating resultGCD by calculating the
GCD of itself and the current number (b becomes a % b until b is 0).
3. Exam Tip: If the GCD becomes 1 at any point (e.g., you encounter a prime
number like 7 or 13), the loop breaks immediately. The result is 1.
2. Block Swap Algorithm (Array Rotation)
• Goal: Rotate an array to the left by $d$ positions efficiently.
• Logic: Instead of shifting elements one by one (slow), it treats the array as two blocks
($A$ and $B$) and recursively swaps chunks of data until the rotation is achieved.
• Step-by-Step:
1. Identify Block A (first $d$ elements) and Block B (the rest).
2. Recursively swap parts of these blocks based on their sizes.
3. Exam Tip: If rotation amount $d$ is greater than array length $n$, the
effective rotation is calculated as $d = d \% n$.
3. Max Product Subarray
• Goal: Find the contiguous subarray that produces the largest product.
• Logic: This is tricky because multiplying two negative numbers creates a positive
number.
• Step-by-Step:
1. Iterate through the array keeping track of both maxProd and minProd.
2. Why min? Multiplying a very small negative number (e.g., -10) by another
negative number (e.g., -5) gives a huge positive number (50).
3. At each step, calculate the potential max by comparing three values: the
current number, current * maxProd, and current * minProd.
4. Maximum Sum of Hourglass in Matrix
• Goal: In a 2D grid, find the "hourglass" shape (3 on top, 1 in middle, 3 on bottom)
that sums to the highest number.
• Logic: Use nested loops to iterate through every possible center point of an
hourglass.
• Step-by-Step:
1. Slide over the matrix (stopping 2 rows/cols before the end).
2. Manually add the 7 specific cells:
▪ Top: (i,j), (i,j+1), (i,j+2)
▪ Middle: (i+1, j+1)
▪ Bottom: (i+2, j), (i+2, j+1), (i+2, j+2)
3. Update maxSum if the current sum is larger than the previous maximum.
Part 2: Linked Lists (Programs 5–16)
5. Reverse Linked List
• Goal: Flip the list pointers so the head becomes the tail and the tail becomes the
head.
• Logic: Iterate through the list and redirect the next pointer of the current node to
point to the previous node.
• Step-by-Step:
1. Use three pointers: prev (initially null), current (head), and next.
2. Inside the loop: Save [Link] (to not lose the list), change [Link] to
point to prev, move prev to current, and move current to the saved next.
3. Return prev as the new head.
6. Merge Two Sorted Lists
• Goal: Combine two already sorted lists into one long sorted list using the "Zipper"
technique.
• Logic: Compare heads of both lists, pick the smaller one, and move forward.
• Step-by-Step:
1. Create a dummy node to start the new list.
2. Compare [Link] and [Link]. Attach the smaller node to the tail of the new list.
3. Move the pointer of the chosen list forward.
4. Repeat until one list is empty, then attach the remainder of the other list.
7. Palindrome Linked List
• Goal: Check if the list reads the same forward and backward (e.g., 1 -> 2 -> 2 -> 1).
• Logic: Split the list in half, reverse the second half, and compare.
• Step-by-Step:
1. Find Middle: Use "Slow and Fast" pointers (Slow moves 1 step, Fast moves 2).
2. Reverse: Reverse the second half of the list.
3. Compare: Check the first half and the reversed second half node-by-node. If
all match, it's a palindrome.
8. Remove Linked List Elements
• Goal: Delete all nodes that contain a specific value val.
• Logic: Scan the list and skip over nodes matching the target value.
• Step-by-Step:
1. Use a dummy node pointing to the head (this handles the case where the
head itself needs deleting).
2. Iterate with current. If [Link] == val, skip that node ([Link] =
[Link]).
3. Otherwise, move current forward.
9. Rotate List
• Goal: Shift the linked list to the right by $k$ places.
• Logic: Turn the list into a circle, then cut it at the new tail.
• Step-by-Step:
1. Calculate the length of the list.
2. Connect the tail to the head to form a circle.
3. Find the new breaking point (the new tail) at index length - (k % length).
4. Set the new head to [Link] and break the circle ([Link] = null).
10. Odd Even Linked List
• Goal: Group all nodes at odd indices together followed by all nodes at even indices
(e.g., 1-3-5-2-4).
• Logic: Maintain separate chains for odd and even positions and merge them.
• Step-by-Step:
1. Use two pointers: odd and even (and keep a pointer to evenHead).
2. [Link] jumps to the next odd node ([Link]).
3. [Link] jumps to the next even node ([Link]).
4. Finally, connect the tail of the odd list to evenHead.
11. Swapping Nodes in a Linked List
• Goal: Swap the values of the $k$-th node from the beginning and the $k$-th node
from the end.
• Logic: Locate both nodes using pointers and swap their data.
• Step-by-Step:
1. Find the $k$-th node from the start (first) by moving a pointer $k$ steps.
2. Find the $k$-th node from the end (second) by starting a fast pointer at $k$
and moving both fast and second until fast hits the end.
3. Swap the data values of first and second.
12. Delete the Middle Node
• Goal: Remove the exact center node of the list.
• Logic: Use the Tortoise and Hare (Slow/Fast) method to locate the middle.
• Step-by-Step:
1. Fast moves 2 steps, Slow moves 1 step.
2. Keep track of the node prev immediately before Slow.
3. When Fast reaches the end, Slow is at the middle.
4. Update [Link] = [Link] to skip/delete the middle node.
13. Remove Nth Node from End of List
• Goal: Delete the node that is $N$ spots from the end of the list.
• Logic: Create a gap of $N$ nodes between two pointers, then slide them to the end.
• Step-by-Step:
1. Send a fast pointer $N$ steps ahead.
2. Start a slow pointer from the head.
3. Move both until fast reaches the end. slow will be exactly at the node before
the target.
4. Skip the target node ([Link] = [Link]).
14. Remove Duplicates from Sorted List II
• Goal: Delete all nodes that have duplicates (leaving only distinct numbers). Example:
1->2->2->3 becomes 1->3.
• Logic: Check ahead for duplicates and skip the entire sequence if found.
• Step-by-Step:
1. Use a dummy head.
2. Check if [Link] equals [Link].
3. If yes, loop until the value changes (skipping all duplicates).
4. Update [Link] to connect to the new non-duplicate value.
15. Partition List
• Goal: Move all nodes less than $x$ to the left, and all nodes greater/equal to $x$ to
the right, preserving original order.
• Logic: Distribute nodes into two separate lists and merge.
• Step-by-Step:
1. Create two dummy heads: before and after.
2. Iterate through the main list. If node < x, add to before; else, add to after.
3. Connect the tail of before to the head of after (and ensure the after tail points
to null).
16. Add Two Numbers
• Goal: Add two numbers represented by linked lists (digits stored in reverse order).
• Logic: Simulate elementary school addition with a carry.
• Step-by-Step:
1. Traverse both lists simultaneously.
2. Calculate sum = val1 + val2 + carry.
3. Create a new node with digit sum % 10.
4. Update carry = sum / 10.
Part 3: Stacks (Programs 17–27)
17. Min Stack
• Goal: A stack that can push, pop, and retrieve the minimum element in $O(1)$ time.
• Logic: Use two stacks to track data and minimums separately.
• Step-by-Step:
1. Main Stack: Stores all pushed data.
2. Min Stack: Stores the minimum value seen so far.
3. Push: If the new value is $\le$ top of Min Stack, push it to Min Stack as well.
4. Pop: If the popped value matches the top of Min Stack, pop from Min Stack
too.
18. Valid Parentheses
• Goal: Check if brackets ()[]{} are balanced and correctly nested.
• Logic: Last Opened must be First Closed (LIFO).
• Step-by-Step:
1. Push opening brackets (, [, { onto the stack.
2. When a closing bracket appears, pop the stack.
3. Check if the popped bracket matches the closing bracket type.
4. Validity: The string is valid only if the stack is empty at the end.
19. Evaluate Reverse Polish Notation (RPN)
• Goal: Calculate math written in Postfix notation like 2 1 + 3 * (which means (2+1)*3).
• Logic: Operands go on the stack; operators consume them.
• Step-by-Step:
1. Iterate through tokens.
2. Number: Push to stack.
3. *Operator (+, -, , /): Pop the top two numbers, perform the math, and push
the result back.
20. Valid Parenthesis String
• Goal: Check validity where * acts as (, ), or empty string.
• Logic: Track the range of possible open parenthesis counts.
• Step-by-Step:
1. Track minOpen (treat * as )) and maxOpen (treat * as ().
2. If we see (, increment both.
3. If we see ), decrement both.
4. If we see *, decrement min and increment max.
5. If max drops below zero, it's invalid. If min is 0 at the end, it's valid.
21. Minimum Remove to Make Valid Parentheses
• Goal: Remove the fewest characters possible to make the string valid.
• Logic: Identify unmatched parentheses and delete them.
• Step-by-Step:
1. Use a stack to track indices of open (.
2. If you see ) and the stack is empty, mark that ) for deletion immediately.
3. If the stack isn't empty, pop (match found).
4. After the loop, any ( remaining in the stack are unmatched; mark them for
deletion.
5. Rebuild the string skipping marked indices.
22. Longest Valid Parentheses
• Goal: Find the length of the longest valid contiguous substring of parentheses.
• Logic: Use a stack to store indices of boundaries.
• Step-by-Step:
1. Push -1 initially (as a base index).
2. When (, push the index.
3. When ), pop.
4. If stack is empty after pop, push current index (new base).
5. If not empty, length = current_index - [Link]().
23. Basic Calculator
• Goal: Evaluate an expression string containing +, -, (, ).
• Logic: Handle nested expressions using a stack for context (result so far and sign).
• Step-by-Step:
1. Keep a running result and sign (+1 or -1).
2. If (, push current result and sign to stack, then reset.
3. If ), calculate the result inside parentheses, multiply by the popped sign, and
add the popped result.
24. Validate Stack Sequences
• Goal: Determine if a given popped array is a possible output of a pushed array.
• Logic: Simulate the stack operations.
• Step-by-Step:
1. Iterate through the pushed array, pushing elements onto a real stack.
2. After every push, check if the top of the stack matches the current element in
popped.
3. While they match, pop from the stack and move the popped pointer.
4. If the stack is empty at the end, the sequence is valid.
25. Remove K Digits
• Goal: Remove $k$ digits from a number to form the smallest possible numerical
value.
• Logic: Use a Monotonic Stack to keep digits in increasing order (small digits at the
start).
• Step-by-Step:
1. Iterate through digits.
2. If the current digit is smaller than the stack top, pop the stack (remove the
larger previous digit) and decrement $k$.
3. This ensures the number starts with the smallest possible digits (e.g.,
replacing 4 with 1).
26. Implement Queue using Stacks
• Goal: Mimic FIFO (Queue) behavior using LIFO (Stack) structures.
• Logic: Use two stacks: Input for pushing and Output for popping.
• Step-by-Step:
1. Push: Always push to InputStack.
2. Pop/Peek: If OutputStack is empty, transfer everything from InputStack to
OutputStack. This reverses the order, putting the oldest element on top.
27. Implement Stack using Queues
• Goal: Mimic LIFO (Stack) behavior using FIFO (Queue) structures.
• Logic: Use a single queue and rotation.
• Step-by-Step:
1. Push(x): Add x to the queue.
2. Immediately rotate the queue: Dequeue and Enqueue the first size-1
elements.
3. This moves the new element x to the front, effectively making it the "top" of
the stack.
Part 4: Queues & Deques (Programs 28–32)
28 & 29. Design Circular Queue / Deque
• Goal: Implement a fixed-size ring buffer that reuses space.
• Logic: Use modulo arithmetic to wrap indices around.
• Step-by-Step:
1. Maintain an array and front, rear, size variables.
2. Enqueue: Insert at (front + size) % capacity. Increment size.
3. Dequeue: Increment front: front = (front + 1) % capacity. Decrement size.
4. For Deque (Double-Ended), InsertFront wraps backwards: (front - 1 +
capacity) % capacity.
30. Number of Recent Calls
• Goal: Count requests that happened in the last 3000ms.
• Logic: Use a sliding window implemented with a Queue.
• Step-by-Step:
1. When a ping comes at time $t$, add $t$ to the queue.
2. Check the front of the queue; remove (dequeue) any timestamps smaller
than $t - 3000$.
3. Return the current size of the queue.
31. Design Front Middle Back Queue
• Goal: A queue allowing push/pop operations at the front, back, OR middle.
• Logic: Use two Deques (Left and Right) and keep them balanced.
• Step-by-Step:
1. Ensure Left and Right differ in size by at most 1.
2. The "Middle" is the boundary between Left tail and Right head.
3. When pushing/popping middle, move elements between the tail of Left and
head of Right to maintain balance.
32. Reveal Cards in Increasing Order
• Goal: Reorder a deck so that revealing the top, putting the next to bottom, and
repeating results in a sorted sequence (1, 2, 3...).
• Logic: Simulate the process in reverse.
• Step-by-Step:
1. Sort the deck of cards.
2. Create a queue of indices [0, 1, 2... n].
3. Iterate through sorted cards: Place the smallest card at the index popped
from the queue.
4. Take the next index from the queue and move it to the back (simulating the
"put next to bottom" step).
Part 5: Heaps & Priority Queues (Programs 33–37)
33. Maximum Product After K Increments
• Goal: Distribute $k$ points (increments) among numbers in an array to maximize the
final product.
• Logic: Increasing the smallest number always yields the highest percentage gain.
• Step-by-Step:
1. Put all numbers into a Min-Heap.
2. Pop the smallest number, add 1, and push it back.
3. Repeat $k$ times.
4. Multiply all elements for the result.
34. Kth Largest Element in Array
• Goal: Find the $k$-th largest number in an unsorted array.
• Logic: Use sorting or a Heap to isolate the top values.
• Step-by-Step:
1. Approach 1 (Simple): Sort the array and pick index length - k.
2. Approach 2 (Heap): Maintain a Min-Heap of size $k$. Add numbers; if the
heap exceeds size $k$, remove the smallest. The root will eventually be the
$k$-th largest.
35. Find K Pairs with Smallest Sums
• Goal: Find $k$ pairs $(u, v)$ from two sorted arrays that have the smallest sums.
• Logic: Explore combinations efficiently using a Heap (similar to merging lists).
• Step-by-Step:
1. Use a Min-Heap to store {sum, index1, index2}.
2. Initially push pairs (nums1[i], nums2[0]) for all $i$.
3. When the smallest pair is popped, insert the next candidate from the second
array: (nums1[i], nums2[next_index]).
36. Sort Characters by Frequency
• Goal: Sort a string based on character counts (e.g., "tree" -> "eert").
• Logic: Count first, then sort by count.
• Step-by-Step:
1. Count frequency of every char using a Map.
2. Push characters into a Max-Heap ordered by frequency.
3. Pop from the heap and append the characters to the result string.
37. Find Subsequence of Length K With Largest Sum
• Goal: Pick $k$ numbers that sum to the maximum possible value, but preserve their
original relative order.
• Logic: Select based on value, then restore order based on index.
• Step-by-Step:
1. Store pairs of (value, original_index).
2. Sort pairs by value (descending) and pick the top $k$.
3. Sort those selected $k$ pairs by index (ascending) to restore the original
sequence.