Competititve Programming & Coding Interviews - Python

Implement the index of substring problem in Python by brute forcing each start position, then optimize to constant extra space by checking characters without slicing.

Learn to compute the longest common prefix for multiple strings by extending the two-string LCP solution, and analyze time and space complexity with big O notation in Python.

Determine whether a string can be formed by repeating a substring by testing prefix lengths that divide the string and validating repetition counts, with O(n^2) time and constant space.

Count triangles by selecting three distinct indices i<j<k and applying the triangle inequality, forming valid triplets with an O(n^3) brute-force approach and constant space.

Explore the maximum sum subarray problem using a brute force approach with two nested loops and indices i and j, computing subarray sums to identify the greatest sum.

Explain solving the maximum sum subarray by moving from brute-force with nested loops to O(n^2) by maintaining a running current sum, avoiding slicing and resetting when the left index changes.

Compute the sum of subarray maximums with a brute-force approach using two nested loops over i and j and a max_value function, achieving O(n^3) time.

Improve the sum of subarray maximums by replacing repeated maximum calculations with a running current maximum inside two nested loops, achieving O(n^2) time and O(1) extra space.

Explore recursive methods to sum an array, analyze base cases, recursion steps, and recurrence relations with slicing in Python, and compare time and space complexities with an iterative approach.

Implement a recursive reverse string function in Python, using a recurrence relation and base case to reverse a string by slicing the last character and concatenating.

Learn to generate a degree-n print pattern with recursion, building from the pattern of n-1 by appending n, and compare naive exponential time to a linear-time approach that stores subpattern.

Demonstrate finding the first occurrence of a value in an array via a recursive approach that preserves indices, contrasts with iterative solutions, and analyzes time and space complexity.

Flatten a multidimensional array into a one-dimensional list using a recursive approach in Python, handling nested lists and integers while analyzing time and space complexity.

Generate subsets using a backtracking approach in Python, exploring take or skip decisions, mapping subsets to binary choices, and analyzing space and time complexity (two to the power of n).

Generate all permutations of nums using backtracking, highlighting factorial growth and exponential time. Copy complete permutations to avoid aliasing, and optimize with sets tracking used or available numbers.

Generate all well-formed parentheses for n using backtracking in Python, pruning invalid prefixes and tracking open parentheses to produce valid sequences of length 2n.

Generate valley permutations of 1..n by backtracking a decreasing prefix then an increasing suffix, using pruning and subset reasoning to achieve 2^n possibilities instead of n!

Explore a word search puzzle on a grid using backtracking and pruning to find a word by moving through adjacent cells without repeats, with efficient neighbor-aware optimization.

Learn the next greater element using a stack to track indices, achieving O(n) time with amortized analysis, and store indices to reduce space.

Reverse substrings inside matching parentheses from the innermost outward using a stack. On closing brackets, reverse the top substring and build the final string.

Decode string demonstrates decoding an encoded string with brackets and numbers using a stack to produce repeated substrings, linking to valid parentheses and stack-based patterns.

Learn to optimize the sum of subarray maximums from quadratic to linear time by counting subarrays where each element is the maximum, using left and right greater indices with stacks.

Greedy removal of k digits using a monotonic stack to produce the smallest possible number, traversing digits left to right. The algorithm runs in linear time and uses linear space.

Merge two sorted arrays using a two-pointer approach to produce a sorted result in linear time, with a final time complexity of O(n+m) and space complexity O(n+m) for the output.

Learn to compute the dot product of two sparse vectors by intersecting their nonzero indices with a two-pointer approach, summing products and achieving O(n+m) time, constant space.

Learn to count triangle triplets in an array with an O(n^2) two-pointer approach: sort the array, fix i and j, and move k to count valid third sides efficiently.

Sort the array into a sorted array where harmonious subsequences become subarrays, then test all subarrays where max minus min equals one to find the longest, in O(n^2) time.

Optimize the longest harmonious subsequence from O(n^2) to O(n) by sorting, pruning left endpoints, and breaking on too-large differences. An amortized approach relies on an initial O(n log n) sort.

Explore counting submatrices full of ones in a binary matrix, starting from brute force with all four coordinates to an optimized two-row method using a full-column array and subarray counting.

Explore finding a subarray with a given sum in non-negative arrays using a sliding window approach with two pointers, tracking the current sum and the start and end indices.

Count palindromic substrings in a string by examining all start and end indices, explain the brute-force O(n^3) approach, and discuss optimizing toward O(n^2) in the next solution.

Explore efficient detection of palindromic substrings by expanding around middle characters using two pointers, handling odd and even lengths to achieve O(n^2) time and O(1) space.

Master the maximum sum of three non-overlapping subarrays by moving from brute-force six-index search to an optimized O(n^3) approach using the middle subarray, Kadane's algorithm, and prefix-suffix sums.

Learn to maximize the sum of three non overlapping subarrays in O(n^2) time by precomputing left and right max sums and applying Kadane's algorithm.

Explore an O(n) solution for the maximum sum of three non-overlapping subarrays by precomputing left and right max sums, using partial sums and Kadane's algorithm.

Determine if a path exists from source to destination in a bidirectional graph using depth-first search. Build an adjacency list, maintain a visited set, and implement a recursive DFS.

Learn to compute minimum distances to every vertex from the source in a directed graph using breadth-first search, with an adjacency list, queue, and min dist array.

Explore shortest paths in directed graphs with red and blue edges using a color-aware breadth-first search. Implement a two-dimensional distance array to enforce alternating colors and efficiently compute results.

Learn how Dijkstra's algorithm computes the shortest paths from a source to all vertices in a weighted graph using a min-heap priority queue and adjacency lists.

Count islands in a grid of ones and zeros by starting at unvisited land cells and exploring all connected neighbors with a visited matrix to mark each island.

Apply a depth-first search on a binary grid to count islands by exploring connected land cells, marking visited cells to avoid repeats, with a fill algorithm.

Explore the word ladder problem by transforming the begin word into the end word through valid dictionary words, using BFS on an undirected graph of one-letter transformations.

Explore a word ladder method that finds next words faster than O(n·l) by fixing a position, replacing with alphabet letters, and verifying membership with BFS.

Analyze a hash table approach that inserts words as string keys, checks membership, and generates next words for a word ladder, with complexity n l^2 sigma, where sigma equals 26.

Explore ladder solved with a bfs using an intermediate word with an asterisk, and learn amortized analysis of time complexity beyond l times sigma bound while storing words for iteration.

Build a hash table transformations where each intermediate word maps to words differing by one letter, then run a breadth-first search over a word graph to solve the word ladder.

Assess if a ransom note can be formed from magazine letters by counting a to z frequencies with two hash tables and comparing them.

Explains the isomorphic strings problem by mapping characters from S to T using two hash maps, preserving order and preventing multiple source characters mapping to the same target.

Learn to solve group anagrams efficiently with a hashmap keyed by the sorted string, mapping to original words, and improve time and space complexity over sorting-based approaches.

Learn to count distinct values in linear time using a hash set to track seen elements, achieving O(n) time and O(n) space with practical language examples.

Learn to solve the four-number sum problem to a target by moving from brute-force quadruplets to an efficient O(n^2) solution using a hashmap of pair sums.

Find a subarray with a given sum by starting with brute force and optimizing with prefix sums and a dictionary in Python. Handle edge cases and articulate your thinking clearly.

Maximize total units on the truck by greedily loading boxes with the most units per box, sorting box types by units and filling the truck until capacity is reached.

Learn a greedy two-pointer method to maximize content children by sorting greed factors and cookie sizes, always assigning the smallest possible cookie to the least demanding child.

Learn a greedy solution to maximize total profit by assigning each worker the most profitable job they can finish, with sorted jobs and a two-pointer optimization that explains complexity.

Explore a brute-force approach to selecting the maximum non-overlapping subset of intervals. Clarify overlap checks using interval intersections and aim to start the algorithm with a single constraint.

Sort intervals by their right endpoints and iteratively decide if each interval belongs to the answer by comparing its left endpoint to the current forbidden range, yielding non-overlapping sets.

Apply a greedy approach to non overlapping intervals by sorting by right endpoints and selecting when the left >= last right; this runs in O(n log n) time.

Explore the meeting rooms problem and determine the minimum number of rooms needed for overlapping meeting intervals. Compare the frequency-array greedy approach with its time and memory constraints.

Apply sweep line using events of start and end times, sort by time and type, then track the maximum number of concurrent meetings to determine the minimum rooms required.