Competitive Programming

Explore starting as a building block to solve larger problems through sorting tweaks, and introduce the horse race problem as a prelude to dynamic programming.

Learn to sort in C++ with custom comparator functions, defining order for any class; implement a comparator that returns true when the first item should precede the second.

Overload the less-than operator for a C++ struct via a friend function to enable object comparisons and sorting, while noting its limitations and the option to use a separate comparator.

Master merge sort, a recursive, comparison-based algorithm that splits input into halves and merges two sorted lists, noting its auxiliary space needs and logarithmic running time for competitive programming.

Explore in-place quicksort with a randomized pivot and partitioning. Sort the list by splitting it into smaller and larger halves, with no auxiliary lists, on average O(n log n).

Sort a DNA strand by grouping identical nucleotides together, focusing on a four-letter alphabet (a, c, g, t) and exploring counting sort and bucket sort as fast solutions.

Count sort leverages a fixed number of outcomes per position by counting occurrences and rewriting the input in order, achieving linear time for long DNA strings.

Sort children by height into five buckets and within each bucket separate football from other activities, using bucket sort to achieve linear-time organization.

Learn a bucket sort approach to the football problem by binning players into five height buckets, then post-processing each bucket to separate footballers from non-footballers.

Explore how binary search halves a sorted list using a middle element to locate a target, while handling open-interval bounds, safe mid calculation to avoid overflow, and insertion point.

In competitive programming, learn how quickselect quickly finds the k-th smallest element in linear time on average by partitioning around a pivot and recursing on a single half.

Explore the two-pointer technique by using start and end pointers to find two numbers that sum to a target, with linear-time iteration and practical examples.

Master the two pointer technique with Floyd's cycle-finding to detect circular versus linear linked lists using fast and slow pointers. Apply the method to interview problems and related graph contexts.

Explore bracket matching with a stack in c++ using standard template library. The lesson shows a boolean valid function that pushes openings, pops on matches, and returns false on mismatches.

Explore queues in competitive programming, including normal queues (first in, first out), front and back operations, and priority queues built on binary heaps, with their time complexities.

Learn how c++ unordered_map and unordered_set provide constant-time insert, delete, and lookup by hashing keys to values or presence, with reserve to pre-allocate space.

Explore how C++ unordered maps and sets work and how to use insert, find, erase, size, and clear, plus reserve and power of two buckets to optimize competitive programming.

Learn how ordered maps and sets in c++ store key-value pairs and keep keys sorted, enabling in-order iteration and insertions, deletions, and lookups in logarithmic time compared to hash tables.

Explore coordinated compression using dictionaries to map brackets to integers, enabling fast bracket matching and string handling by translating data to numeric labels for efficient programs.

Coordinate compression maps a large input range to a small set of indices to save memory, using a forward map from seen values to 0..k-1 and optionally a backward map.

Explore how to use a custom comparator to drive STL data structures such as set, map, and priority queue, ordering multiples of three first, then non-multiples, with counts.

Explore how hash functions map large inputs to small integers and enable fast lookups in C++ unordered maps and sets, with equal probability and the sliding window technique.

Discover how C++ handles hash collisions by placing elements with the same hash value in the same bucket and maintaining constant time lookups through bucket bounds and rehashing.

Explore the Rabin-Karp case study to learn pattern search with a hash function and sliding window, returning the starting positions of all occurrences.

Explore the Rabin-Karp algorithm's polynomial rolling hash using two primes and modulo arithmetic to compute and slide hashes. Avoid overflow and prepare for rehashing with a sliding window.

Explore the Rabin-Karp sliding window rehashing technique, updating the hash as the window slides across the text in linear time without rehashing the entire window.

Explore the sliding window technique to compute the maximum subarray sum of length k. Slide the window, remove the leftmost value, add the new one, and update the maximum.

Explore greedy algorithms and greedy strategies in competitive programming that select locally optimal choices at each step. Learn their speed, limitations, and how to prove correctness for certain problems.

Explore the greedy coin change method, using euros as a case study to minimize coins. Learn when greedy is optimal, when it fails, and how to implement the algorithm efficiently.

Examine the coin change problem, contrasting valid change sequences with optimal ones, and explore strategies for greedy algorithms under contest time and memory constraints.

Explore the timetable problem with a greedy approach that sorts subjects by end time and selects non-overlapping classes to maximize total subjects taken.

Apply a greedy algorithm to the interval covering problem, selecting the minimum number of segments to cover a ruler from zero to full length using sorted starts and farthest reach.

Sort the inputs to unlock greedy solutions; many greedy problems become easier after sorting, then attack the problem with a tailored approach using buckets or interval covering.

Explore complete search as a method to solve problems by trying all possibilities, including permutations and subsets, with pruning to cut unhelpful paths and guarantee a solution.

Explore backtracking as a core complete search technique that traverses decision trees by exploring branches and backtracking from dead ends until all possibilities or a solution is found.

this video demonstrates using backtracking to generate all permutations of a list of numbers, using a permutation list and a selected vector to explore prefixes and print lexical permutations.

Explore generating all subsets of a list with backtracking by recursively exploring exclude and include branches, starting at index zero, printing the empty subset first and backtracking after each choice.

Explore pruning in backtracking via a card game problem, where early cuts occur when a card's last letter must match the next card's first, improving efficiency.

Explore iterative complete search by using nested loops to try every four-digit combination from zero to nine, calling open safe function that returns true when correct, with breaks and pruning.

Explore the divide and conquer paradigm by splitting problems, solving subproblems, and merging results. Review key algorithms like merge sort, quicksort, and binary search and how they follow this pattern.

Master the binary search the answer method to find a secret number by narrowing an inclusive interval with a check function, minimizing guesses and avoiding repeats.

Apply binary search over a continuous interval, splitting the interval in half until the range is within epsilon to approximate the square root of x, noting floating point limits.

Explore dynamic programming through the top-down approach to computing Fibonacci numbers, using memoization and a lookup table to avoid redundant calls.

Explore bottom-up dynamic programming for the Fibonacci problem, initializing base cases and iteratively filling a table to achieve linear time, and compare with top-down approaches.

Learn to recognize dynamic programming problems and apply a three-step method: define states, identify base cases, and derive transitions to build recurrences; practice diverse DP problems.

Explore maximum one-dimensional range sum with a bottom-up dynamic programming approach that tracks the maximum sum ending at each index, using zero for empty sequences, achieving linear time and memory.

Explore space optimization for bottom-up dynamic programming by reducing memory to two previous values or a single current value, maintaining correctness across inputs.

Explore a dynamic programming approach to the coin change problem, using a top-down recursive function with memoization and a DP table to minimize coins.

The lecture demonstrates a dynamic programming approach to the coin change problem, using a dp table to minimize coins for amount eight with coins five, three, and one.

Backtrack through the dynamic programming table to reconstruct the optimal coin change solution, using the DP table and a backtrack function to pick the last coin and rebuild the combination.

Master the prefix sums technique to preprocess an array, creating a prefix array that enables fast range sum queries between indices i and j on zero-indexed data.

Revisit the horses problem to explore a strategy function that maximizes betting multipliers across up to ten races, using race history to optimize decisions.

Explore how the time subtraction function converts two characters into integers from a hh:mm string, subtracts 30 minutes, borrows an hour when needed, and pads with zeros.

Explore core graph terminology, including nodes, edges, directed and undirected graphs, cycles, and directed cyclic graphs, with clear definitions and example visuals.

Explore three common graph representations in C++: adjacency lists, adjacency matrices, and edge lists, and learn how their storage affects traversal, edge checks, and suitability for sparse vs dense graphs.

Master depth-first search through a depth-wise graph traversal that visits unvisited neighbors, marks nodes, and backtracks. Explore how it reveals connected components in undirected graphs.

Explore breadth-first search on graphs using a queue to visit nodes by layers, track visited nodes, and compute distances from a start node in undirected graphs and their connected components.

Learn to find the farthest node from a root using breadth-first search by tracking the last node visited. Explore distance layers via a queue and apply this to tree diameters.

Apply dfs to compute the total number of potatoes in a graph by summing node values while marking visited to avoid double counting, demonstrated from node zero through its neighbors.

Discover and label connected components in a graph as maximal groups of mutually reachable nodes. Use a discovery process to assign component ids and count the components, here three.

Apply breadth-first search to find the nearest exit in a labyrinth graph, using an adjacency list, a queue, and visited tracking to explore by distance.

Discover how to apply multi-source BFS to a labyrinth problem with multiple drop points, using a shared queue and visited checks to find the earliest exit in competitive programming.