Amazon Interview Prep: Data Structures & Algorithms

Explore the maximum subarray sum problem and master Kadane's algorithm, which computes the largest contiguous subarray sum in O(n) time with O(1) space, handling negative numbers.

Explore how to solve the maximum product subarray problem by computing prefix and suffix products, ignoring zeros, using a two-pass approach that runs in O(n).

Detect and locate the start of a cycle in a linked list with the hare and tortoise two-pointer method, using constant memory and returning null when no cycle exists.

Learn how to find the intersection point of two linked lists of different lengths using a two-pointer method, achieving O(m+n) time and O(1) space while preserving the original list structure.

Design a min stack that supports push, pop, top, and get min in constant time by using two stacks: A for all elements and B for current minima.

Determine the minimum parentheses needed to balance a string by tracking extra opening and closing brackets in a single pass. Implement the O(n) solution to add the necessary brackets.

Group the given strings by anagrams using a hash table keyed by the sorted characters; gather all anagrams into lists and return a list of these groups.

Find the longest consecutive sequence in an unsorted integer array by using a set to start only at numbers without a predecessor and extend through consecutive values.

Maintain a min-heap of size k to keep the k largest elements; push when a value exceeds the heap top and pop the smallest, yielding kth largest at the end.

Find the kth smallest element in a binary search tree by performing an inorder traversal, counting visited nodes, and stopping when the count reaches k.

Solve the jump game by tracking the maximum reachable index while scanning the nums array from index 0. Return true if maximum reachable reaches the last index; otherwise return false.

Solve the house robber problem by using dynamic programming with a memoized 2d dp table to maximize non-adjacent house values, illustrated with examples and a recursive approach.

Explore House robber II, a circular variation where you cannot rob adjacent houses. The lecture demonstrates solving with two DP passes, excluding the first or the last.

Explore the coin change problem by using dynamic programming with memoization to find the fewest coins needed to reach a given amount, illustrating greedy fails.

Master the longest increasing subsequence problem with a bottom-up dynamic programming approach, defining subsequences, computing dp values ending at each index, and achieving O(n^2) time complexity.

Explore solving the 0-1 matrix problem by computing the distance to the nearest zero for every cell in a binary matrix using a multi-source BFS from all zeros.

Model prerequisites as a directed graph and an adjacency list, then apply a depth-first search to detect cycles and determine if all courses can be completed.

Color the starting pixel and flood fill all connected pixels in four directions: top, bottom, left, and right, using DFS (or BFS), with Java, Python, JavaScript, and C++ implementations.

Use Dijkstra's algorithm to compute the minimum time for a signal to reach all nodes in a weighted directed graph built from travel times, returning the farthest distance or -1.

Explore the combination sum backtracking problem: given candidates and a target, find all combinations that sum to the target, using numbers any number of times.

Explore the product of arrays except self problem and how to solve it in O(n) time without division. Build left and right product arrays to compute the final output efficiently.

Explore rotating an array to the right by k using an in-place O(n) time, O(1) space method. Apply the three-step reverse trick—whole array, first k, remaining elements—with modulo optimization.

Learn to sort an array of zeros, ones, and twos in place using a two-pointer approach that moves zeros left and twos right, leaving ones in the middle.

Learn the duplicate number problem in an array of n+1 integers from 1 to n, solved by binary search on the value range with constant space.

Master the three sum problem by sorting the array and using a two-pointer approach to find unique triplets that sum to zero, reusing the two-sum logic while avoiding duplicates.

Learn to search in a rotated sorted array using a modified binary search, identify whether mid lies in the rotated or original region, and return the target index or -1.

Apply the two-pointer approach to the two sum II problem on a sorted, non-decreasing array, returning the unique one-indexed pair that sums to the target with constant extra space.

explore binary search to maximize the minimum distance between balls placed in sorted basket positions, using a greedy feasibility check to decide distance.

Master binary tree level order traversal with a queue-based BFS approach to produce a list of lists by level, starting at the root and enlisting left and right children.

Explore the longest common subsequence problem for two strings, learn a dynamic programming approach with memoization, base cases, and a recurrence to compute the LCS length efficiently.

Explore the longest substring without repeating characters using a two-pointer sliding window and a hash map to track counts. Expand when unique, shrink on duplicates, and assess linear time.

Explore dynamic programming to decide if an array can be partitioned into two equal subsets by forming a target sum of half the total using memoized choices.

Explore the target sum problem by counting ways to assign plus or minus to array elements to reach a target using a top-down dynamic programming approach with memoization.

Identify land cells in an m by n grid that cannot reach the boundary. Use a boundary-based DFS from edge lands to mark reachable cells, then count the remaining lands.

Explore the surrounded regions problem on an n by n matrix of x's and zeros, and learn to identify and flip captured zero regions using boundary-based depth-first search.

Master backtracking to generate all subsets of a unique-element array, building the power set without duplicates, and understand the exponential time complexity of two to the n.

Explore the longest palindromic substring using a bottom-up dynamic programming approach. Build a 2d boolean table to track palindromes by length, with Java and JavaScript implementations.

Decode ways teaches counting interpretations of a digit string mapped to letters 1–26 using dynamic programming. Use dp[i] = dp[i-1] + dp[i-2] for valid two-digit combos, with zero handling.

Implement an in-place solution to set entire rows and columns to zero when a cell is zero, using the first row and column as markers for a constant-space approach.

Master spiral matrix traversal by implementing a robust algorithm that outputs matrix elements in spiral order, handling rectangular matrices with boundary-aware top, bottom, left, and right pointers.

Explore a recursion-based approach to validate a binary search tree by tracking lower and upper bounds for each node, including null bounds and edge cases.

Explore an efficient Sudoku validator that uses row, column, and 3x3 grid sets to ensure no repeated digits, even on partially filled boards.

Solve the trapping rain water problem by computing left and right maximum heights, use the minimum of both for each bar, and sum the trapped water.

learn how to solve the sliding window maximum problem by maintaining a deque of candidate indices to track the maximum in each window of size k, achieving linear time.

Learn how to maintain the median of a data stream using two heaps, a max heap and a min heap, with add num and find median operations for online queries.

Sort the given intervals by start times, merge overlapping intervals into a single range, and output non-overlapping intervals using a Java solution with a comparator and an answer list.

Learn to merge intervals in javascript by sorting by start times, merging overlapping intervals into non-overlapping ranges, and building the final answer with min start and max end.

Sort intervals by start times, tie-break with end times, then merge overlapping intervals into non-overlapping ranges; the C++ solution runs in O(n log n) time.

Merge overlapping intervals by sorting by start times and merging with the last interval in the result. Implement a Python solution producing non-overlapping intervals in O(n log n) time.

Master the two sum problem with a hash table that stores seen numbers and their indices to find the complement for the target, returning two distinct indices without reusing elements.

Learn the two sum problem using a hash table to find two numbers that add to a target in an array of integers, with indices returned and complexity considerations.

Learn the two sum problem solved with a hash table in c++, returning the indices of two numbers that add to the target using a complement lookup.

Solve the two sum problem with a hash table in Python to return the indices of two numbers that add to the target, in O(n) time and O(n) space.

Master binary search to find the first and last positions of a target in a sorted ascending array using two searches, achieving O(log n) time with leftmost and rightmost indices.

Learn how to find the first and last positions of a target in a sorted array using two modified binary searches, achieving logarithmic time.

Learn to find the first and last positions of a target in a sorted array using two binary searches in Python, achieving an O(log n) time complexity.

Explore how to find the lowest common ancestor in a binary search tree by comparing two nodes and traversing toward the left or right subtree, with a concise Java implementation.

Learn to find the lowest common ancestor of two nodes in a binary search tree using JavaScript. From the root, go left or right until the common ancestor appears.

Master finding the lowest common ancestor in a binary search tree by traversing from the root, guiding left when both targets are smaller, right when larger, and returning the ancestor.

Find the lowest common ancestor in a binary search tree by comparing p and q to the current node and traversing left or right. The Python implementation returns the LCA.

Apply divide and conquer to compute x raised to n, handling double x and negative n, using recursion in Java with O(log n) steps and base case n=0.

Learn to count palindromic substrings with a dynamic programming approach in Java. Build a dp[i][j] table to identify palindromes and count them in O(n^2) time and space.

Rotate a given n x n matrix by 90 degrees in place using a two-step approach: transpose the matrix, then reverse each row, implemented in Java without extra space.