Classic Practice Problems

Outer Loop - Number of Passes: Bubble sort needs multiple passes through the array. After each complete pass, the largest unsorted element "bubbles up" to its final position at the end. So after pass 1, the largest element is in place. After pass 2, the second largest is in place, and so on. We need at most (n-1) passes because once (n-1) elements are sorted, the last one is automatically correct.

Inner Loop - Compare and Swap: The inner loop compares adjacent elements and swaps them if they're in wrong order. Notice the boundary is n - i - 1 because after i passes, the last i elements are already sorted and don't need checking. The swapped flag tracks if we made any swaps this pass - if not, the array is already sorted and we can stop early!

Early Termination Optimization: If a complete pass makes no swaps, the array is already sorted! This optimization makes bubble sort O(n) for already-sorted arrays instead of O(n²). While bubble sort is not efficient for large datasets, it's educational and works well for small or nearly-sorted arrays. Time: O(n²) worst/average, O(n) best. Space: O(1) - sorts in place.

Setting Up the Merge: The merge function combines two sorted halves into one sorted array. We're given: left (start of first half), mid (end of first half), and right (end of second half). First, we copy both halves into temporary vectors. This is necessary because we'll be overwriting the original positions as we merge.

The Merge Process: Now comes the clever part! Since both halves are already sorted, we just need to pick the smaller element from the front of each half. We use three pointers: i for leftArr, j for rightArr, and k for where to place in the original array. We compare leftArr[i] with rightArr[j], pick the smaller one, put it at arr[k], and advance the corresponding pointer. Using <= makes merge sort "stable" (equal elements keep their relative order).

Copy Remaining Elements: When one array is exhausted, the other might still have elements left. Since they're already sorted, we just copy them directly. Only ONE of these while loops will actually run (the one with remaining elements). For example, if we've used all of leftArr, we copy whatever's left in rightArr.

Divide and Conquer: This is the heart of merge sort! The base case handles arrays of 0 or 1 elements (already sorted). Otherwise, we find the middle, recursively sort the left half, recursively sort the right half, then merge them. The recursion naturally divides the problem into smaller subproblems. Time: O(n log n) always - we do log n levels of merging, each level processes n elements. Space: O(n) for temporary arrays.

Partition Setup: The partition function is the heart of quicksort. We choose the last element as our pivot (though other choices work too). The variable i tracks the boundary between elements smaller than pivot and elements larger than pivot. Everything from low to i (inclusive) will be smaller than pivot; everything from i+1 to j-1 will be larger.

Partitioning Logic: We scan through the array with j. When we find an element smaller than pivot (arr[j] < pivot), we increment i (extending the "small elements" region) and swap arr[i] with arr[j]. This moves the small element into the correct region. Elements >= pivot stay in place initially because j keeps moving past them.

Placing the Pivot: After the loop, elements 0..i are less than pivot, and elements i+1..high-1 are >= pivot. The pivot itself is still at high. We swap it to position i+1, which is its correct final sorted position! We return this position so quickSort knows where to split for the next recursive calls.

Quick Sort Main Logic: If there's more than one element (low < high), we partition the array and get the pivot's final position. Then we recursively sort everything to the left of the pivot and everything to the right. The pivot is already in its correct spot, so we don't include it. Time: O(n log n) average, O(n²) worst. Space: O(log n) for recursion stack. Quick sort is often faster in practice than merge sort due to better cache performance.

Factorial - Classic Recursion: Factorial is the "Hello World" of recursion. To calculate 5!, we need 5 × 4!. To get 4!, we need 4 × 3!, and so on. The BASE CASE stops the recursion: when n <= 1, we return 1 (since 0! = 1! = 1). Without a base case, recursion would continue forever! Each call waits for the smaller call to complete, then multiplies. So factorial(5) → 5 × factorial(4) → 5 × 4 × factorial(3) → ... → 5 × 4 × 3 × 2 × 1 = 120.

Fibonacci - Two Recursive Calls: Fibonacci shows recursion with TWO recursive calls: F(n) = F(n-1) + F(n-2). The sequence goes 0, 1, 1, 2, 3, 5, 8, 13... Each number is the sum of the two before it. We need TWO base cases: F(0) = 0 and F(1) = 1. Warning: This naive implementation is O(2^n) because it recalculates the same values many times! We'll see how Dynamic Programming fixes this.

Permutations - Base Case: To generate all permutations of [1,2,3], we fix one element at a time. start indicates which position we're currently deciding. When start equals the array size, we've made all decisions and have a complete permutation to save. This is our base case - a valid solution has been found!

The Backtracking Pattern - Choose, Explore, Unchoose: This is the classic backtracking template! For position start, we try placing each remaining element (indices start to end). The pattern is: (1) CHOOSE: swap to place element i at position start. (2) EXPLORE: recursively fill remaining positions. (3) UNCHOOSE: swap back to restore original state (BACKTRACK). This last step is crucial - it "undoes" our choice so we can try the next option!

Subsets - Include or Exclude: Generating subsets uses the same backtracking pattern. For each element, we can include it or not. We add the current state (which could be empty, partial, or complete) to results. Then we try including each remaining element: push it to current, explore further, then pop it (backtrack). For [1,2,3], this generates: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] - all 2³ = 8 subsets!

N-Queens - Checking Valid Positions: The N-Queens problem places N queens on an N×N chessboard so no two attack each other. Queens attack horizontally, vertically, and diagonally. Since we place one queen per row (moving down), we only check upward for conflicts: the column above, upper-left diagonal, and upper-right diagonal. If any direction has a queen, this position isn't safe.

N-Queens Backtracking: We place queens row by row. If we've placed queens in all N rows, we found a solution! For each row, we try placing a queen in each column. If the position is safe, we place the queen ('Q'), recurse to the next row, then BACKTRACK by removing the queen ('.'). This explores ALL valid placements. For N=4, there are 2 solutions; for N=8, there are 92!

Memoized Fibonacci - From O(2^n) to O(n): Remember our naive recursive Fibonacci was O(2^n)? With memoization, we cache each F(n) value after computing it. When we need F(n) again, we look it up in O(1) instead of recomputing. Since there are only n unique subproblems and each is computed once, we achieve O(n) time! The hash map memo stores previously computed values.

Bottom-Up Fibonacci: Instead of starting at F(n) and recursing down, we start at F(0), F(1) and build UP! We create a table (vector) to store results. We know F(0)=0 and F(1)=1. For each subsequent i, we compute F(i) = F(i-1) + F(i-2) using values already in the table. No recursion needed! Time: O(n), Space: O(n) for the array.

Space Optimization - O(1) Space: We only ever use the last two values to compute the next one. So instead of storing all n+1 values, we just keep prev2 (F(i-2)) and prev1 (F(i-1)). After computing the current value, we "shift": prev2 becomes the old prev1, and prev1 becomes current. Time: O(n), Space: O(1). This pattern applies to many DP problems!

Climbing Stairs - Hidden Fibonacci: To reach step n, you can come from step n-1 (take 1 step) OR from step n-2 (take 2 steps). So ways(n) = ways(n-1) + ways(n-2). Sound familiar? It's Fibonacci! Base cases: 1 way to reach step 1, 2 ways to reach step 2 (1+1 or 2). We use the same space-optimized approach. For n=4: 1→1→1→1, 1→1→2, 1→2→1, 2→1→1, 2→2 = 5 ways.

Coin Change - Problem Setup: Given coin denominations (e.g., [1, 2, 5]) and an amount, find the MINIMUM number of coins needed. We create a DP array where dp[i] represents the minimum coins to make amount i. Initialize with INT_MAX (infinity) meaning "impossible". The base case dp[0] = 0 because we need 0 coins to make amount 0.

Building the Solution: For each amount from 1 to target, we try each coin. If we can use this coin (coin <= i) and the remaining amount (i - coin) is achievable (not INT_MAX), then dp[i] = min(dp[i], dp[i-coin] + 1). The "+1" counts the current coin. Example: coins=[1,2,5], amount=11 → dp[11]=3 (5+5+1). If we can't make the amount, return -1. Time: O(amount × coins), Space: O(amount).

LIS - Problem Setup: Find the length of the longest strictly increasing subsequence. For [10,9,2,5,3,7,101,18], the answer is 4 ([2,3,7,101] or [2,5,7,101]). Note: subsequence doesn't have to be contiguous! dp[i] represents the LIS length ending at index i. Initialize all to 1 because every single element is a valid subsequence of length 1.

Building the LIS: For each position i, we check all previous positions j. If nums[j] < nums[i] (we can extend the subsequence), then dp[i] = max(dp[i], dp[j] + 1). We're asking: "what's the longest subsequence ending at j that I can extend?" We track the maximum across all positions. Time: O(n²). Note: There's an O(n log n) solution using binary search, but this O(n²) version is easier to understand!

0/1 Knapsack - The Classic DP Problem: You have a knapsack with limited capacity. Each item has a weight and value. Pick items to maximize value without exceeding capacity. Each item can only be used once (0/1). We use a 2D DP table: dp[i][w] = maximum value achievable using the first i items with capacity w. Initialize with zeros (0 items or 0 capacity = 0 value).

The Decision at Each Step: For each item i and capacity w, we have two choices: (1) DON'T take item i → value is same as using i-1 items with same capacity. (2) TAKE item i (if it fits) → value = value with remaining capacity + item's value. We pick the maximum. The final answer is dp[n][capacity]. Time: O(n × capacity), Space: O(n × capacity). This can be optimized to O(capacity) space by processing in reverse order!

Setup: We include the vector library and create a function that returns a pair of indices. The function takes a sorted array and a target sum as input. We initialize two pointers: left starts at the beginning (index 0) and right starts at the end of the array. This is the classic two-pointer technique for sorted arrays.

Main Loop: We continue the loop as long as left pointer is less than right pointer. Inside the loop, we calculate the sum of elements at both pointer positions. This sum will help us decide which pointer to move next. If pointers ever meet or cross, we've checked all possible pairs.

Decision Logic: If sum equals target, we found our answer and return both indices as a pair. If sum is too small, we move the left pointer right to get a larger number (array is sorted!). If sum is too large, we move the right pointer left to get a smaller number. This works because moving left pointer right increases the sum, and moving right pointer left decreases it.

No Solution Found: If the loop ends without finding a valid pair, we return {-1, -1}. This is a common convention to signal "not found" when returning indices. The caller should check for this special value. This solution runs in O(n) time since each element is visited at most once, and uses O(1) extra space.

Setup: We include string for string operations and cctype for character functions like isalnum and tolower. The function returns true if the string is a valid palindrome, false otherwise. We use two pointers: left starts at index 0 and right starts at the last character. A palindrome reads the same forwards and backwards (like "racecar" or "A man a plan a canal Panama").

Skip Invalid Characters: The outer while loop runs as long as left hasn't crossed right. The first inner while skips any non-alphanumeric characters (spaces, punctuation) from the left side. The second inner while does the same from the right side. std::isalnum() returns true only for letters (a-z, A-Z) and digits (0-9). This way, "A man, a plan" is treated as "AmanaplanacanalPanama".

Compare and Move: We use std::tolower() to convert both characters to lowercase before comparing. This makes the comparison case-insensitive, so 'A' equals 'a'. If characters don't match, we immediately return false - it's not a palindrome. If they match, we move both pointers inward (left++ and right--) and continue checking. If the loop completes without finding mismatches, we return true - it IS a palindrome! Time: O(n) | Space: O(1)

Setup: This function removes duplicate elements from a sorted array in-place (without using extra memory). First, we handle the edge case: if the array is empty, return 0 (no elements). We use the "two-pointer" technique with a slow pointer called writePos. writePos starts at 1 because the first element (index 0) is always unique. This pointer marks where we should write the next unique element we find.

Main Loop: The fast pointer readPos scans through every element starting from index 1. For each element, we compare it with the last unique value we found (at writePos - 1). If they're different, we've found a new unique element! We copy it to the writePos position. Then we increment writePos to prepare for the next unique element. If they're the same (duplicate), we simply skip it and move to the next element.

Return Result: We return writePos which tells us how many unique elements exist. After the function runs, the first writePos elements contain all unique values in order. The remaining elements in the array are still there but can be ignored. For example: [1,1,2,2,3] becomes [1,2,3,2,3] and we return 3 (first 3 elements are unique). Time: O(n) - one pass through array. Space: O(1) - no extra memory used.

Problem Setup: We need to find two vertical lines that form a container holding maximum water. Think of an array like [1,8,6,2,5,4,8,3,7] where each number is the height of a wall. We use two pointers starting at both ends - left at the beginning and right at the end. This gives us the maximum possible width initially. The variable maxWater will store our best answer found so far.

Calculate Water Area: Inside the while loop, we calculate how much water the current container can hold. The width is the distance between the two pointers (right - left). The height is the SHORTER of the two walls because water will spill over the shorter one - that's why we use std::min(). The area is simply width × height. We compare this with our current best using std::max() and update if we found a bigger container.

Greedy Decision - Move Shorter Wall: This is the clever part! We always move the pointer pointing to the shorter wall inward. Why? Because the water level is limited by the shorter wall. If we move the taller wall inward, we only reduce the width without any chance of increasing height - guaranteed worse result. But if we move the shorter wall, we might find a taller wall that could increase our water capacity enough to compensate for the reduced width. Time: O(n) - single pass. Space: O(1) - only three variables.

Problem Setup: We want to find the maximum sum of any k consecutive elements in an array. For example, with [2,1,5,1,3,2] and k=3, we check all possible "windows" of 3 elements. First we include the headers and handle an edge case - if the array has fewer than k elements, we can't form a valid window so we return -1.

Build First Window: Before we start sliding, we need to calculate the sum of our first window (first k elements). This loop adds up elements from index 0 to k-1. For nums=[2,1,5,1,3,2] with k=3, this gives us 2+1+5=8. We store this as our initial maxSum because so far it's the only window we've seen.

Slide the Window: Instead of recalculating the entire sum for each position (which would take O(k) time each), we "slide" by adding one new element and removing one old element - this takes only O(1) time! For each position, we add nums[i] (the new element entering the window) and subtract nums[i-k] (the element leaving). We keep track of the maximum sum seen. Example: window [2,1,5] → add 1, remove 2 → [1,5,1]. Time: O(n) - single pass. Space: O(1) - constant extra space.

Problem Setup: We need to find the longest substring where no character repeats. For "abcabcbb", the answer is 3 ("abc"). We use a hash map charIndex to remember where we last saw each character. Variable maxLen stores our best answer so far, and left marks the start of our current window. The window will grow and shrink as we find unique and duplicate characters.

Handle Duplicates: We expand our window by moving right through the string. For each character, we check two things: (1) Have we seen this character before? (2) Is that previous occurrence inside our current window (charIndex[c] >= left)? If both are true, we found a duplicate! We fix this by moving left to one position after the previous occurrence of this character. This "shrinks" our window to remove the duplicate.

Update and Track Maximum: After handling any duplicate, we update the character's position in our map to its current index. Then we calculate the current window size using right - left + 1 (the +1 is because both ends are inclusive). We keep track of the maximum we've seen. When the loop finishes, maxLen contains our answer. Time: O(n) - we visit each character once. Space: O(min(m,n)) - m is charset size.

Problem Setup - Count What We Need: This is a harder problem! Given string s="ADOBECODEBANC" and t="ABC", we need to find the smallest window in s that contains all characters from t (answer: "BANC"). First, we count how many of each character we need from t using the required map. Then we track two counts: requiredCount is how many distinct characters we need, and formedCount is how many we've satisfied so far.

Window Variables: The window map tracks character counts in our current window. left is the start of our window. We use minLen = INT_MAX as a placeholder for "infinity" - any valid window will be smaller. minStart remembers where our best answer starts so we can extract it later.

Expand Window: We expand by moving right and adding characters to our window. For each character, we increment its count in window. Then we check: is this character needed (in required)? And did we just reach exactly the required count? If yes, we've satisfied one more character requirement, so increment formedCount.

Contract While Valid: Once formedCount == requiredCount, we have a valid window! Now we try to shrink it from the left to find the minimum. First, we check if this window is smaller than our best and save it. Then we remove the leftmost character - if this drops its count below what's required, we decrement formedCount (window becomes invalid) and stop shrinking.

Return Result: If minLen is still INT_MAX, we never found a valid window, so return empty string. Otherwise, extract the minimum window using substr(minStart, minLen). For s="ADOBECODEBANC" and t="ABC", the answer is "BANC" - the smallest window containing A, B, and C. Time: O(n+m) - visit each char at most twice. Space: O(m) - for the hash maps.

Problem Setup - Using a Deque: We need to find the maximum element in every window of size k. For [1,3,-1,-3,5,3,6,7] with k=3, answer is [3,3,5,5,6,7]. A naive approach would scan each window for max (O(n*k)). Instead, we use a deque (double-ended queue) that can add/remove from both ends. The key insight: we store indices of "candidates" that could potentially be the maximum in some future window.

Remove Outdated Elements: As we process each element, first we check if the element at the front of the deque has "expired" - meaning its index is no longer within our current window of size k. If the front index is <= i-k, it's too old (outside our window), so we remove it with pop_front(). This keeps our deque containing only indices from the current window.

Maintain Decreasing Order: Here's the clever part! We remove all indices from the back whose values are smaller than the current element. Why? Because if a smaller element came before a larger element, the smaller one can NEVER be the maximum for any window that includes the larger element. After this cleanup, we add the current index. The deque now maintains a decreasing order of values!

Record the Maximum: Once we've processed k elements (i >= k-1), we have a complete window. Since our deque maintains decreasing order, the front always holds the index of the maximum element in the current window! We simply add nums[dq.front()] to our result. This technique is called "Monotonic Deque" - the deque maintains a specific order (here, decreasing values). Time: O(n) - each element enters/exits deque once. Space: O(k) - deque holds at most k elements.

Setting Up the Class: We include the <vector> header to use dynamic arrays. The class is named PrefixSum because it will store cumulative sums. Inside the private section, we declare prefix as a vector of long long. We use long long instead of int because sums can grow very large and overflow regular integers. This vector will hold our running totals - each position stores the sum of all elements before it.

Constructor Setup: The constructor takes the original array as input (passed by reference to avoid copying). We store the array's size in n for convenience. Notice we resize prefix to n + 1, one larger than the original array! This extra slot at the beginning (index 0) will always be 0, representing "the sum of zero elements." All slots are initialized to 0 using the second argument to resize().

Building Running Totals: This loop is the heart of prefix sums - it builds our cumulative totals. Each prefix[i + 1] equals the previous prefix sum plus the current array element. For example, if arr = [1, 2, 3, 4, 5], we get prefix = [0, 1, 3, 6, 10, 15]. Notice how prefix[3] = 6 is the sum of elements at indices 0, 1, 2 (which is 1+2+3). This one-time O(n) work lets us answer any range sum query instantly!

Range Sum Query: This is where the magic happens - getting any range sum in O(1) time! The formula prefix[right + 1] - prefix[left] works because of how prefix sums are structured. prefix[right + 1] contains the sum from index 0 to right (inclusive). prefix[left] contains the sum from index 0 to left - 1 (everything before our range). Subtracting removes the part we don't want, leaving exactly the sum from left to right!

Sum of First K Elements: This helper function is even simpler - just return prefix[k] directly! Remember, prefix[k] stores the sum of elements from index 0 to k-1, which is exactly k elements. For example, sumFirst(3) returns prefix[3], the sum of elements at indices 0, 1, and 2. This is a common query in many problems: "What's the total of the first k items?" Both query methods run in O(1) constant time, no matter how big the array is!

Walkthrough Example: Let's trace through with arr = [1, 2, 3, 4, 5] to see it in action. The prefix array becomes [0, 1, 3, 6, 10, 15] where each value is a running total. To find the sum from index 1 to 3 (elements 2, 3, 4), we compute rangeSum(1, 3). This returns prefix[4] - prefix[1] = 10 - 1 = 9, which is indeed 2+3+4! Without prefix sums, we'd need to loop through and add 2+3+4 every single time we query.

Initial Setup: We need two headers: <vector> for the array and <unordered_map> for fast lookups. The prefixCount map tracks how many times we've seen each prefix sum value. We initialize prefixCount[0] = 1 which is crucial - it represents "before the array starts." Why is this important? If the running sum itself equals k, we need to count that subarray starting from index 0! Without this initialization, we'd miss subarrays that start at the very beginning of the array.

Building Running Sum: We use currentSum to track our running total as we scan through the array. The count variable will store our final answer - the number of subarrays that sum to k. We use a range-based for loop to visit each number in the array. On each iteration, we add the current number to our running sum. Think of currentSum as answering: "What's the sum of all elements from index 0 to here?"

The Key Insight: This is the clever part! We check if (currentSum - k) exists in our map. Why? If the prefix sum at some earlier index was (currentSum - k), then the subarray from there to here sums to exactly k! For example, if currentSum=10 and k=7, we look for prefix sums of 3. If we saw sum=3 twice before, that's 2 valid subarrays. This transforms a nested loop problem (O(n²)) into a single-pass solution (O(n))! We add the count of matching prefix sums because each one represents a valid subarray ending at our current position.

Record and Return: After checking, we record the current prefix sum by incrementing its count in the map. This is crucial: we record AFTER checking to avoid counting subarrays that end where they start (length 0). The order matters - check first, then record. This ensures we only find subarrays that end at the current index. After processing all elements, count holds the total number of subarrays summing to k. Time complexity is O(n) with O(n) space for the hash map - much better than the O(n²) brute force!

Walkthrough Example: Let's trace through nums = [1, 1, 1] with k = 2. We start with prefixCount = {0: 1}. As we scan: sum becomes 1, then 2, then 3. When sum=2, we need (2-2)=0. We saw sum=0 once, so count=1 (subarray [1,1] from index 0-1). When sum=3, we need (3-2)=1. We saw sum=1 once, so count=2 (subarray [1,1] from index 1-2). The two valid subarrays are [1,1] at indices 0-1 and [1,1] at indices 1-2. Both sum to 2!

Function Setup: The goal is to return an array where each element is the product of ALL other elements except itself. We take the input array by reference (const) to avoid copying and ensure we don't modify it. We store the size in n and create result initialized with all 1s. Why 1s? Because multiplying by 1 doesn't change anything - it's the "identity" for multiplication. We'll use result cleverly to store intermediate values, saving extra memory!

Left-to-Right Pass: We scan from left to right, building "prefix products" (products of all elements to the left). prefix starts at 1 (empty product). For each position, we first store prefix in result, THEN multiply. After this pass with nums = [1, 2, 3, 4], we get result = [1, 1, 2, 6]. Notice: result[2] = 2 is the product of everything LEFT of index 2 (which is 1×2=2). We're halfway there - each position now holds the product of all elements before it!

Right-to-Left Pass: Now we scan backwards, building "suffix products" (products of all elements to the right). suffix starts at 1. For each position, we MULTIPLY result[i] by suffix, then update suffix. The magic: result[i] already holds the left product, so multiplying by the right product gives us the full answer! After this pass: result = [24, 12, 8, 6]. For index 1: left product (1) × right product (12) = 12. This two-pass technique avoids using division - important when the array might contain zeros!

Return Result: We return the completed result array where each result[i] = product of all other elements. Time complexity is O(n) - we make exactly two passes through the array. Space complexity is O(1) extra (not counting the output) - we only use two integer variables! This is more efficient than the naive O(n²) approach of computing each product separately. No division is needed, so this solution works even when the array contains zeros.

Complete Walkthrough: With nums = [1, 2, 3, 4], let's verify the final answers. result[0] = 24: product of 2×3×4 = 24 (everything except index 0). ✓ result[1] = 12: product of 1×3×4 = 12 (everything except index 1). ✓ result[2] = 8: product of 1×2×4 = 8 (everything except index 2). ✓ result[3] = 6: product of 1×2×3 = 6 (everything except index 3). ✓

Setup and Key Insight: We need to find the longest subarray with equal numbers of 0s and 1s. We include <algorithm> for the std::max function we'll use later. The sumIndex map stores the FIRST index where each running sum occurred. sumIndex[0] = -1 is crucial - it means "a sum of 0 exists before the array starts." This handles cases where a valid subarray starts at index 0 (like [0, 1] which has equal 0s and 1s).

The Transformation Trick: Here's the clever idea - we treat each 0 as -1 and each 1 as +1. Why? Because if we have equal counts of 0s and 1s, the sum will be zero! (e.g., two 0s (-2) and two 1s (+2) = 0) maxLen will store our answer - the longest valid subarray found so far. sum is our running total using the transformed values (-1 for 0, +1 for 1). This transformation converts "count equal elements" into "find zero-sum subarray" - a prefix sum problem!

Finding Valid Subarrays: If we've seen this sum before, the subarray between those positions has sum 0! Why? If sum[i] == sum[j], then elements from j+1 to i must sum to 0 (they "cancel out"). A sum of 0 means equal 0s and 1s! We calculate the length as i - sumIndex[sum]. We only record the FIRST occurrence of each sum because we want the LONGEST subarray. If a sum appears at index 2 and again at index 8, the subarray from 3 to 8 has length 6.

Return the Result: After scanning the entire array, maxLen holds the length of the longest valid subarray. Time complexity is O(n) - we visit each element exactly once. Space complexity is O(n) in the worst case for the hash map (when all running sums are unique). This is much better than the O(n²) brute force that checks every possible subarray! The key insight: transforming 0→-1 lets us use prefix sums to find "balanced" subarrays.

Detailed Walkthrough: Let's trace through nums = [0, 1, 0] step by step. We transform values: 0→-1, 1→+1, 0→-1. Running sums become: -1 (after idx 0), 0 (after idx 1), -1 (after idx 2). At index 1, sum=0 matches our initial sumIndex[0]=-1, so length = 1-(-1) = 2. This is [0,1]. At index 2, sum=-1 matches sumIndex[-1]=0, so length = 2-0 = 2. This is [1,0] at indices 1-2. Both subarrays have length 2, with equal counts of 0s and 1s. Answer: 2.

Class Definition: This class extends prefix sums from 1D arrays to 2D matrices (grids). We include <vector> because we'll use a 2D vector to store our prefix sums. The private member prefix is a "vector of vectors" - essentially a 2D grid. Each cell prefix[i][j] will store the sum of all elements in the rectangle from (0,0) to (i-1,j-1). This preprocessing lets us answer "What's the sum of this rectangle?" in O(1) time!

Constructor Setup: The constructor takes the original matrix and builds our prefix sum grid. First, we check if the matrix is empty to avoid errors. Then we get dimensions: m rows and n columns. Just like 1D prefix sums, we add padding! Our prefix grid is (m+1) × (n+1) in size. The extra row and column of zeros at the top and left make our formulas simpler. assign creates the 2D vector with all zeros - this handles our padding automatically.

Building with Inclusion-Exclusion: This nested loop fills in our 2D prefix sums using a clever formula. For each cell, we add: (1) the current matrix value, (2) the sum above, (3) the sum to the left. But wait - we've now counted the top-left region twice! So we subtract prefix[i-1][j-1]. Think of it like Venn diagrams: when you add two overlapping circles, you subtract the overlap once. After this O(m×n) preprocessing, every prefix[i][j] holds the sum of the rectangle from (0,0) to (i-1,j-1).

Query in O(1) Time: This is where our preprocessing pays off - instant rectangle sums! We use inclusion-exclusion in reverse: start with the full rectangle to bottom-right corner. Then subtract the region ABOVE our target rectangle (prefix[row1][col2+1]). Then subtract the region to the LEFT of our target (prefix[row2+1][col1]). But now we've subtracted the top-left corner twice, so we add it back (prefix[row1][col1]).

Visual Understanding: Imagine a grid where you want the sum of a small rectangle in the middle. prefix[row2+1][col2+1] gives you everything from (0,0) to (row2,col2) - that's too much! Subtracting prefix[row1][col2+1] removes all rows above your target rectangle. Subtracting prefix[row2+1][col1] removes all columns to the left of your target. Adding prefix[row1][col1] fixes the double-subtraction of the top-left corner. Done in O(1)!

The O(n log n) Investment: Sorting costs O(n log n) time, but it's often the best investment you can make! Once data is sorted, magical things happen: equal elements cluster together (making duplicates easy to find), ranges become contiguous (simplifying interval problems), and binary search becomes possible (enabling O(log n) lookups). Many O(n²) brute-force solutions become elegant O(n log n) algorithms just by sorting first!

Sort-First Strategy: Many problems become trivial after sorting. Duplicates cluster together, smallest/largest elements move to ends, and relationships between adjacent elements reveal patterns. The O(n log n) sorting cost is often negligible compared to the algorithmic benefits. Best for: finding duplicates, merging intervals, scheduling problems, finding closest pairs, median finding, and greedy algorithms.

Setting Up the Function: We include <vector> to store our intervals (each interval is a pair of numbers like [start, end]) and <algorithm> for the sorting function. Our function takes a reference to a vector of intervals - using a reference (&) means we work with the original data instead of making a copy, which saves memory. The first thing we check is if the input is empty - if someone gives us no intervals, we simply return an empty result. This is called an "edge case" - a special situation we handle right away to avoid errors later.

The Key Insight - Sort First: This single line is the magic that makes the entire problem easy! When we sort intervals, they automatically get arranged by their start times (the first number). For example, [[8,10],[1,3],[2,6]] becomes [[1,3],[2,6],[8,10]]. Why does this help? Because after sorting, any intervals that could possibly overlap will be sitting right next to each other! Without sorting, we'd have to compare every interval with every other interval (very slow). With sorting, we just look at neighbors (very fast).

Starting Our Result Collection: We create a new vector called "merged" to store our final answer. Think of it as an empty basket where we'll put our combined intervals. We immediately add the first interval (intervals[0]) to our basket. Why? Because we need something to compare against! As we go through the remaining intervals, we'll check if each one overlaps with the last interval in our basket. The first interval becomes our starting point.

Walking Through Each Interval: We start our loop at i=1 (not 0) because we already added the first interval to our result. For each interval, we get a reference to the last interval in our merged result using merged.back(). The "auto&" means "figure out the type automatically and give me a reference, not a copy." Using a reference is important here because if we need to extend this interval (when there's an overlap), we want to modify it directly in our result vector.

Detecting and Handling Overlaps: Here's the overlap detection: intervals[i][0] is the start of current interval, last[1] is the end of the previous interval. If the current starts before (or exactly when) the previous ends, they overlap! Example: if last is [1,6] and current is [4,8], then 4 ≤ 6, so they overlap. We merge them by extending the end: take the maximum of both end times. So [1,6] and [4,8] become [1,8]. We use max() because the current interval might end earlier than the last one (like [4,5] would be completely inside [1,6]).

No Overlap - Keep Separate: If the current interval's start is greater than the last interval's end, there's a gap between them - no overlap! Example: if last is [1,3] and current is [8,10], then 8 > 3, so they don't touch. In this case, we simply add the current interval as a new entry in our merged result. It will become the new "last" interval for future comparisons. This is why sorting was so important - we only need to compare with the immediately previous interval!

Returning the Merged Intervals: After processing all intervals, our "merged" vector contains the final answer with all overlapping intervals combined. The time complexity is O(n log n) because of sorting, plus O(n) for the single pass through intervals - so overall O(n log n). The space complexity is O(n) for storing the result. This is very efficient compared to the naive O(n²) approach of comparing every pair!

Step-by-Step Example: Let's trace through: Start with [1,3] in result. Next, [2,6] - does 2 ≤ 3? Yes! Overlap! Merge to [1, max(3,6)] = [1,6]. Next, [8,10] - does 8 ≤ 6? No! Add as separate. Next, [15,18] - does 15 ≤ 10? No! Add as separate. Final answer: [[1,6],[8,10],[15,18]]. Notice how we reduced 4 intervals to 3 by merging the overlapping ones. This algorithm is commonly used in calendar applications for scheduling!

Setting Up - Why We Need a Priority Queue: We include three headers: <vector> for storing intervals, <algorithm> for sorting, and <queue> for the priority queue (also called a "heap"). The priority queue is key to this solution - it will help us track which rooms become free and when. Think of it like a smart list that always tells us which room will finish its meeting first. If there are no meetings, we need zero rooms - that's our edge case.

Processing Meetings in Order: We sort meetings by their start time so we can process them chronologically - just like how meetings would actually occur during a day! If meeting A starts at 9am and meeting B starts at 10am, we want to assign room(s) for A first. This way, when we get to B, we already know if any room from earlier meetings might be free. Without sorting, we'd have no logical order to work with.

The Secret Weapon - Min-Heap: This line creates a special data structure called a min-heap. The "std::greater<int>" part makes it so the smallest number is always on top (normally C++ heaps put the largest on top). Each number in this heap represents when a room becomes free (the end time of its current meeting). When we need a room, we check the top - if that room will be free by the time our new meeting starts, we can reuse it!

Booking the First Room: We start by giving the first meeting a room. We push its end time (intervals[0][1]) into our heap. Think of this as saying "Room 1 is occupied until time X." For example, if the first meeting is [0, 30] (from time 0 to time 30), we push 30. Now our heap knows "there's one room in use, and it becomes free at time 30." The heap size (currently 1) represents rooms currently in use.

Can We Reuse a Room?: For each new meeting, we check: does this meeting start after (or exactly when) the earliest-ending room becomes free? rooms.top() gives us the earliest end time. If our meeting starts at time 15 and rooms.top() is 10, then yes - that room is free by the time we need it! We "pop" (remove) that end time from the heap because that room is no longer occupied by its old meeting - it's about to get a new one.

Booking the Room: Whether we reused a room or not, we push the current meeting's end time into the heap. If we popped (reused a room), the heap size stays the same - we removed one old meeting and added one new meeting. If we didn't pop (no room was free), the heap size grows by 1 - we needed a brand new room! This elegantly tracks how many rooms are in use at any point.

The Answer is the Heap Size: After processing all meetings, the heap size tells us the maximum number of rooms that were ever needed simultaneously. This is exactly our answer! The heap grew whenever we couldn't reuse a room (meetings overlapped) and stayed the same when we could reuse. Time complexity is O(n log n) for sorting plus O(n log n) for n heap operations, giving O(n log n) overall. Space is O(n) for the heap.

Walking Through the Example: Meeting [0,30] gets Room 1 (heap: {30}). Meeting [5,10] arrives - can we reuse? Check heap.top() = 30. Does 5 ≥ 30? No! Room 1 is still busy. We need Room 2 (heap: {10, 30}). Meeting [15,20] arrives - heap.top() = 10. Does 15 ≥ 10? Yes! Room 2 is free. Pop 10, push 20 (heap: {20, 30}). Final heap size = 2, so we need 2 rooms. Notice the first meeting [0,30] runs the whole time - it's blocking Room 1 throughout!

Understanding the Problem: We need to find the minimum number of intervals to remove. Think of it like this: you have a calendar full of events, some overlapping, and you want to cancel as few as possible while eliminating all conflicts. Our function returns a count (integer) of how many need to be removed. If we have 0 or 1 interval, there can't be any overlap, so we return 0 (remove nothing). This edge case saves us from accessing invalid array indices later.

The Greedy Trick - Sort by END Time!: This is the key insight that makes this problem solvable! Unlike previous problems where we sorted by start time, here we sort by END time (a[1] < b[1]). Why? Because if we keep intervals that finish earliest, we leave maximum room for future intervals! Imagine two events: one from 9am-5pm and another from 9am-11am. Keeping the shorter one (ends at 11am) leaves more day for other events. This is called a "greedy" approach - make the locally optimal choice at each step.

Setting Up Our Counters: We need two things: "count" to track how many intervals we remove, and "prevEnd" to remember when the last kept interval ends. We start count at 0 (haven't removed anything yet) and initialize prevEnd with the end time of the first interval (intervals[0][1]). Since we sorted by end time, the first interval ends earliest - it's the best choice to keep, so we "keep" it by recording its end time.

Detecting Overlaps: For each interval starting from the second one, we check: does it start before the previous interval ends? If intervals[i][0] (current start) < prevEnd, they overlap! Example: if prevEnd is 5 and current starts at 3, they overlap (3 < 5). When there's an overlap, which do we remove? The current one! Why? Because we sorted by end time, the current one ends later than the previous. Removing the later-ending one leaves more room. We increment count but DON'T update prevEnd.

No Overlap - Keep This Interval: If the current interval starts at or after prevEnd (current.start ≥ prevEnd), there's no overlap - we can keep both! Example: if prevEnd is 5 and current starts at 7, no conflict (7 ≥ 5). We keep this interval by updating prevEnd to the current interval's end time. Now future intervals will be compared against this new endpoint. Notice we don't increment count - we're not removing anything.

The Answer - Minimum Removals: After scanning all intervals, "count" holds exactly how many we needed to remove to eliminate all overlaps. The greedy approach guarantees this is the minimum! Time complexity is O(n log n) for sorting plus O(n) for the scan = O(n log n) overall. Space is O(1) extra (we only use a couple variables). This is also known as the "Activity Selection Problem" in algorithms.

Why This Greedy Strategy Works: Imagine you're booking a room for events. If you have two conflicting events - one ending at 2pm and one at 5pm - which do you keep? The one ending at 2pm! From 2pm onwards, you can fit more events. By always keeping the earlier-ending interval when there's a conflict, you mathematically maximize how many intervals can coexist. This greedy choice at each step leads to the globally optimal solution - a beautiful example of greedy algorithms!

Understanding the Challenge: We need three headers: <vector> for our input array, <string> because we'll work with strings (easier than manipulating large numbers), and <algorithm> for custom sorting. The function returns a string because the result could be HUGE - imagine arranging [999999999, 999999998, ...]. Such a number wouldn't fit in any integer type! By working with strings, we avoid overflow issues entirely.

Converting to Strings: First, we convert every integer to its string form using std::to_string(). So [3, 30, 34, 5, 9] becomes ["3", "30", "34", "5", "9"]. Why strings? Because we need to compare combinations like "330" vs "303" to decide if "3" or "30" should come first. With integers, such comparisons would be complicated. With strings, we can simply concatenate (join) and compare. The "for (int n : nums)" is a range-based for loop - it visits each number in nums one by one.

The Clever Comparison Trick: This is the heart of the solution! We use a custom comparator that asks: "If I put 'a' before 'b', is that better than putting 'b' before 'a'?" We check by concatenating: a+b vs b+a. Example: for "3" and "30", we compare "330" vs "303". Since "330" > "303", we want "3" to come before "30". The comparator returns true when a should come first. String comparison works perfectly here because comparing "330" > "303" character by character gives the right answer!

Edge Case - All Zeros: What if the input is [0, 0, 0]? After sorting, we'd get ["0", "0", "0"]. If we just concatenate, we get "000" - but that's not right! The number zero should just be "0". So we check: after sorting, if the first (largest) element is "0", then ALL elements must be "0" (because 0 can only beat other 0s in our comparison). In this case, we return just "0". This prevents outputs like "0000".

Assembling the Final Answer: Now that our strings are sorted in the optimal order, we simply concatenate them all together. We start with an empty "result" string and keep appending each string from our sorted vector using the += operator. The "const auto&" means we're reading each string without copying it (const = won't modify, auto = figure out the type, & = reference). After this loop, "result" contains our answer!

Returning the Largest Number: We return the concatenated result string. The time complexity is O(n log n) for sorting, where each comparison takes O(k) time (k = average string length), so overall O(n * k * log n). Space is O(n * k) for storing the string copies. This problem beautifully demonstrates how custom comparators can solve problems that seem impossible with standard sorting!

Walking Through the Example: Let's trace [3, 30, 34, 5, 9]. When comparing "3" vs "30": "330" > "303" ✓ so "3" comes first. When comparing "5" vs "34": "534" > "345" ✓ so "5" comes first. Comparing "9" vs everything: "9X" > "X9" for any single digit, so "9" is first overall. Final order: ["9", "5", "34", "3", "30"]. Concatenate: "9" + "5" + "34" + "3" + "30" = "9534330". Notice how 9 comes first (largest single digit), then 5, then 34 beats 3 because "343" > "334"!

Key Takeaway - Custom Comparators: Many sorting problems require defining your own comparison logic. In C++, use lambda functions with std::sort like: [](const auto& a, const auto& b) { return /* your comparison */; }. The comparator returns true if the first argument should come before the second. This is incredibly powerful - you can sort by any criteria you need, whether it's end time, string concatenation results, or any custom logic!

What is a Hash Map? Think of a hash map like a magical dictionary where you can instantly look up any word. In C++, we use std::unordered_map to store pairs of information: a "key" (what you're looking for) and a "value" (the data attached to that key). For counting problems, the key is typically the item you want to count, and the value is how many times you've seen it. The "magic" is that finding, adding, or removing items takes the same amount of time regardless of how much data you have - this is called O(1) or "constant time" performance.

Common Operations: The most useful hash map operations are: map[key]++ to count occurrences (adds 1 to the value, creates it if it doesn't exist), map.count(key) to check if a key exists (returns 1 if yes, 0 if no), and map.find(key) to get an iterator to the element. You can loop through all key-value pairs using a range-based for loop: for (auto& [key, value] : map). These operations form the foundation of virtually every frequency counting problem you'll encounter.

Including the Right Tools: We need two header files here. The <vector> header gives us access to dynamic arrays that can grow and shrink as needed - our input will be a vector of integers. The <unordered_map> header provides the hash map data structure we'll use for lightning-fast lookups. Think of includes like importing tools into your workshop - without the right tools, you can't build anything. Always include only what you need to keep your code clean and compilation fast.

Function Setup and Hash Map Declaration: Our function takes a vector of numbers (nums) and a target sum we're trying to reach. It returns a vector containing the two indices whose values add up to the target. We use const and & to pass by reference without copying (efficient!) while promising not to modify the input. The numIndex hash map will store each number as a key and its position (index) as the value. This lets us instantly answer: "Have I seen this number before, and where was it?"

Loop and Complement Calculation: We walk through each number in the array one by one using a standard for loop. The variable i is our current position (0, 1, 2, ...). Here's the clever trick: instead of checking every possible pair, we calculate what number we NEED. If target is 9 and current number is 2, we need 7. That's our "complement." The formula complement = target - nums[i] tells us exactly what partner we're looking for. If that partner exists somewhere we've already looked, we've found our answer! This transforms a slow O(n²) double-loop into a fast O(n) single pass.

The Magic Lookup: This is where the hash map shines! numIndex.count(complement) instantly checks if we've seen the complement before - no looping required, just O(1) constant time. If count returns 1 (true), we found it! We immediately return both indices: numIndex[complement] gives us where the complement was stored, and i is our current position. The curly braces {...} create a vector on the fly with these two values. Notice we check BEFORE adding the current number - this prevents using the same element twice (important edge case!).

Store and Continue: If we didn't find our complement, we store the current number and its index in our map: numIndex[nums[i]] = i. This makes it available for future iterations to find. The key is the actual number value, the value is its index position. For example, if nums[0] = 2, we store {2: 0}. If the loop completes without finding a pair, we return an empty vector {} to indicate no solution exists. This "look before you store" pattern is fundamental - it ensures we build up our knowledge base as we go.

Walkthrough Example: Let's trace through step by step. We want two numbers that add to 9. At i=0, nums[0]=2, so we need 9-2=7. Is 7 in our map? No (map is empty). Store {2: 0}. At i=1, nums[1]=7, so we need 9-7=2. Is 2 in our map? Yes! It's at index 0. Return [0, 1]. We found that nums[0] + nums[1] = 2 + 7 = 9, which equals our target. Notice how we only needed to look at 2 elements instead of checking all possible pairs. That's the power of hash maps!

Required Headers: This problem needs more tools. <vector> for dynamic arrays, <string> for text handling, <unordered_map> for our hash map. The new one is <algorithm> which gives us the std::sort function - we'll use it to sort characters in a string. Anagrams are words with the same letters rearranged: "eat", "tea", and "ate" are all anagrams of each other. Our strategy: if we sort each word's letters, all anagrams become identical! "eat" → "aet", "tea" → "aet", "ate" → "aet".

Complex Return Type and Map Setup: The return type looks scary but let's break it down: vector<vector<string>> means "a list of lists of strings" - each inner list contains words that are anagrams of each other. Our hash map groups maps a sorted string (the "key") to a vector of original strings (all the anagrams with that sorted form). For example, the key "aet" would map to the vector ["eat", "tea", "ate"]. This map structure automatically groups all anagrams together as we process them!

Creating the Canonical Key: We loop through each string in the input. For each string, we create a copy called key (we don't want to modify the original!). Then std::sort(key.begin(), key.end()) sorts the characters alphabetically. The word "tea" becomes "aet" after sorting. This sorted version is called the "canonical form" - a standard representation that all anagrams share. It's like giving everyone in a family the same last name: different first names (original words), same identifier (sorted form).

Adding to Groups: This single line does a lot! groups[key] accesses (or creates) the vector for this sorted key. Then .push_back(s) adds the original string to that vector. If the key doesn't exist yet, C++ automatically creates an empty vector for it. This is super convenient! So when we process "eat" (key="aet"), "tea" (key="aet"), and "tan" (key="ant"), we get: {"aet": ["eat", "tea"], "ant": ["tan"]}. Each anagram naturally joins its family group without any extra logic needed.

Extracting Results: Now we need to convert our map into the required return format (just the grouped vectors, not the keys). The syntax auto& [key, anagrams] is called "structured binding" - it unpacks each map entry into its key and value parts automatically. We use std::move(anagrams) to transfer ownership of the vector instead of copying it - this is a performance optimization. The result is a vector of vectors, where each inner vector contains words that are anagrams of each other.

Complete Example Trace: Let's walk through: "eat" sorts to "aet", "tea" also becomes "aet", "tan" becomes "ant", "ate" → "aet", "nat" → "ant", "bat" → "abt". The map builds up: {"aet": ["eat"]}, then {"aet": ["eat", "tea"]}, then {"aet": ["eat", "tea"], "ant": ["tan"]}, and so on. Final groups: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] - three groups of anagrams! Time complexity is O(n × k × log k) where n is the number of strings and k is the maximum string length (sorting each string takes k log k).

Simple Includes: This problem only needs strings and our trusty hash map. The goal is to find the first character in a string that appears exactly once. For example, in "leetcode", the letter 'l' appears once and is at index 0, while 'e' appears three times so it doesn't count. We'll use a classic two-pass approach: first count all characters, then find the first with count = 1. This is one of the cleanest examples of frequency counting in action.

Function and Frequency Map: Our function takes a string and returns an integer (the index of the first unique character, or -1 if none exists). The freq map will count how many times each character appears. The key is a char, the value is an int count. For "hello", we'll build: {'h': 1, 'e': 1, 'l': 2, 'o': 1}. This map becomes our "character census" - we know exactly how popular each letter is.

Pass 1 - Count Everything: This loop walks through every character in the string. The range-based for loop for (char c : s) gives us each character one at a time. The expression freq[c]++ is the counting idiom: it accesses the count for character c and increments it by 1. If c wasn't in the map, C++ creates it with value 0, then adds 1. After this loop, our map contains the complete frequency table for all characters. This is O(n) time - we look at each character exactly once.

Pass 2 - Find the First Unique: Now we walk through the string again, this time by index (we need to return the position, not just the character). For each character s[i], we check freq[s[i]] == 1 - does this character appear exactly once? The FIRST character we find with frequency 1 is our answer, so we immediately return its index i. We must traverse in original order to find the FIRST unique character, not just ANY unique character.

No Unique Found: If we finish the second loop without finding any character with frequency 1, every character repeats at least twice. We return -1 as a signal that no unique character exists. This is a common convention in C++ for "not found" results. For example, "aabb" would return -1 since both 'a' and 'b' appear twice. The total time complexity is O(n) + O(n) = O(n), and space is O(1) if we consider the alphabet size fixed (only 26 lowercase letters at most).

Walkthrough: In "leetcode": l appears 1 time, e appears 3 times (at positions 1, 2, 6), t once, c once, o once, d once. In the second pass, we check index 0 (character 'l') - its frequency is 1, so we return 0 immediately. Even though t, c, o, and d are also unique, 'l' comes first so it wins. This two-pass pattern (count first, then query) is extremely common in frequency problems.

Headers for Counting + Selection: This problem combines frequency counting with selecting the "top k" most frequent items. We need vectors, our hash map, and a new tool: <queue>. The queue header gives us priority_queue - a special container that always keeps its "best" element at the top. We'll use it as a "min-heap" to efficiently track the k most frequent elements without sorting everything. Think of it like keeping track of the top 10 scores in a game - you only need to remember 10 values, not all scores ever.

Phase 1 - Count Frequencies: Just like before, we first count how many times each number appears. The freq map stores number → count. For input [1,1,1,2,2,3], we get: {1: 3, 2: 2, 3: 1}. The number 1 appears 3 times, 2 appears twice, 3 appears once. This O(n) pass gives us complete frequency information. Now the question becomes: given these frequencies, how do we efficiently find the k numbers with the highest counts?

Custom Comparator for Min-Heap: A priority_queue in C++ is a max-heap by default (largest on top). We want a min-heap (smallest on top) so we can easily remove the least frequent element. The cmp is a lambda function (inline function) that compares two pairs. Each pair is (frequency, number). By returning a.first > b.first, we flip the default comparison - now smaller frequencies bubble to the top. Why min-heap? We'll keep exactly k elements. When a new element is better than our worst (the min), we swap them. The min-heap makes finding the worst element instant!

Creating the Priority Queue: This line looks complex but breaks down simply. We're creating a priority_queue that stores pairs (frequency, number). The three template arguments are: (1) what we store (pairs), (2) underlying container (vector of pairs), (3) our custom comparator type. decltype(cmp) gets the type of our lambda, and we pass cmp to the constructor. Now pq is a min-heap where the pair with the smallest frequency is always accessible at the top via pq.top().

Phase 2 - Fill the Heap: We iterate through all unique numbers and their counts. For each, we push (count, num) onto our heap. Here's the clever part: if the heap grows beyond k elements, we immediately pop the smallest (least frequent). This keeps exactly k elements. After processing all numbers, the heap contains the k most frequent because we always discarded the weakest candidate. This is O(n log k) - better than sorting everything O(n log n) when k is small!

Phase 3 - Extract Results: Now we empty the heap to build our result. pq.top().second gets the number (not the frequency) from the top pair. We pop each element after reading it. The result vector will contain all k most frequent numbers. Note: the order might be from least to most frequent (since it's a min-heap), but the problem often doesn't require a specific order. Total complexity: O(n) for counting + O(n log k) for heap operations = O(n log k). Space: O(n) for the frequency map.

Example Walkthrough: We want the 2 most frequent numbers from [1,1,1,2,2,3]. Frequencies: 1 appears 3 times, 2 appears 2 times, 3 appears 1 time. Processing: push (3,1), heap size 1 ≤ 2, keep. Push (2,2), size 2 ≤ 2, keep. Push (1,3), size 3 > 2, pop smallest (1,3). Heap now has (2,2) and (3,1) - the two most frequent! Number 3 (frequency 1) was kicked out. Result contains 2 and 1 - the numbers that appeared most often in the original array.

Headers - Introducing unordered_set: This problem uses unordered_set instead of unordered_map. A set is like a map that only has keys, no values - perfect for checking if numbers exist. We want to find the longest sequence of consecutive integers. For [100, 4, 200, 1, 3, 2], the sequence 1-2-3-4 has length 4. The naive approach would be to sort the array O(n log n), but we can do better with a hash set achieving O(n)! The algorithm header gives us std::max for comparing lengths.

Building the Set: The constructor numSet(nums.begin(), nums.end()) creates a set containing all numbers from the input vector in one line. Using a set automatically removes duplicates and gives us O(1) lookup. For [100, 4, 200, 1, 3, 2], the set contains {1, 2, 3, 4, 100, 200}. maxLen tracks the longest consecutive sequence we've found so far. The key insight: we need to check "does number X exist?" many times - hash set makes this instant.

The Brilliant Optimization: Here's the key trick that makes this O(n). We only START counting from numbers that are the BEGINNING of a sequence. How do we know if a number starts a sequence? If num - 1 is NOT in the set, then nothing comes before this number - it's a starting point! For example, with {1, 2, 3, 4, 100, 200}: 1 is a start (0 not in set), but 2, 3, 4 are not starts (their predecessors exist). Without this check, we'd count the sequence 1-2-3-4 four times. With it, we count it once starting from 1.

Counting the Sequence: Once we've identified a sequence start, we count how long it goes. currentNum tracks where we are, currentLen counts how many consecutive numbers we've seen. The while loop keeps going as long as the next number exists: "Is currentNum + 1 in the set?" If yes, move forward and increment the length. For starting at 1: check 2 (exists, len=2), check 3 (exists, len=3), check 4 (exists, len=4), check 5 (doesn't exist, stop). Each number is visited at most once in these inner loops across all iterations - this is the key to O(n) performance.

Track the Maximum: After counting each sequence that starts at a valid beginning point, we update maxLen if this sequence is longer than our previous best. std::max(a, b) returns the larger of two values - a concise way to update a running maximum. After processing all numbers, maxLen holds the length of the longest consecutive sequence. Time complexity is O(n) despite the nested loop because each element is processed at most twice (once in outer loop, once in while loop).

Complete Example: Let's trace the algorithm. Set = {100, 4, 200, 1, 3, 2}. Check each number: is it a sequence start? 100: is 99 in set? No → start! Count: 100. Is 101 there? No. Length = 1. 4: is 3 in set? Yes → skip (not a start). 200: is 199 in set? No → start! Count: 200. Is 201 there? No. Length = 1. 1: is 0 in set? No → start! Count: 1→2→3→4. Is 5 there? No. Length = 4. Maximum length found = 4. The sequence [1, 2, 3, 4] is the longest consecutive sequence, even though the numbers were scattered in the original input.

When to Use Hash Maps vs Arrays: For small, known ranges (like ASCII characters 0-127), use arrays - they're faster and cache-friendly. For large or sparse ranges (like arbitrary integers), or when key types aren't integers, use unordered_map. If you need ordered iteration (smallest to largest keys), use map instead - it's tree-based with O(log n) operations. The right data structure choice can make your code both cleaner and faster!