Explore · Flashcard deck
39 cards · 11 topics · by Quizcard team · 0 hearts · Updated 2026-11-03
Shared from Quizcard. Flip through the cards below, or copy the deck to edit and study it in your own account — free.
Space flips · arrows move · Esc exits
Problem signal: array is SORTED, find a pair that sums to a target
Answer: Two Pointers — one pointer at start, one at end, move inward based on comparison to target
O(n) time, O(1) space. Only works directly on sorted (or sortable) data.
In the sorted pair-sum problem, how do the two pointers move?
Answer: If sum < target, move left pointer right (increase sum); if sum > target, move right pointer left (decrease sum); if sum == target, pair found
Problem signal: reverse an array or string in place
Answer: Two pointers starting at both ends, swap elements and move inward until pointers meet
O(n) time, O(1) space
Problem signal: remove duplicates from a sorted array in place
Answer: Two pointers — a slow pointer marks the last confirmed unique position, a fast pointer scans ahead for new unique values
O(n) time, O(1) space
Problem signal: find all triplets summing to zero (3Sum)
Answer: Sort the array, fix one element, then use two pointers on the remaining subarray to find pairs summing to -fixed
O(n^2) time overall, O(log n) extra space for sorting
Problem signal: find the maximum sum of a contiguous subarray of fixed size k
Answer: Fixed-size Sliding Window — maintain a running sum, add the entering element, subtract the one leaving the window
O(n) time, O(1) space. Example: arr=[2,1,5,1,3,2], k=3 → window sums 8,7,9,6 → max=9.
Mechanically, how do you slide a fixed-size window of size k one step forward?
Answer: Add arr[right] to the running total, subtract arr[right-k] from it, then increment both the left and right pointers
Problem signal: find all anagrams of pattern p within string s
Answer: Fixed-size sliding window of length len(p) combined with a character frequency map compared at each position
O(n) time, O(26) or O(k) space for the alphabet/character set
Problem signal: smallest contiguous subarray with sum >= a target value
Answer: Variable-size Sliding Window — expand the right pointer to grow the sum, then shrink from the left while the condition still holds
O(n) time, O(1) space since each pointer moves forward at most n times total
Problem signal: longest substring without repeating characters
Answer: Variable sliding window with a hash set/map tracking last-seen index; shrink the window from the left when a duplicate is found
O(n) time, O(min(n, charset size)) space
Problem signal: longest substring with at most K distinct characters
Answer: Variable sliding window with a frequency hash map; shrink from the left while the number of distinct characters exceeds K
O(n) time, O(K) space
What distinguishes a fixed sliding window from a variable sliding window?
Answer: A fixed window always has the same size k as it slides; a variable window expands and shrinks dynamically based on a condition (sum, distinct count, etc.)
What is the general time/space complexity of sliding window techniques?
Answer: O(n) time — each pointer traverses the array at most once (amortized) — and O(1) to O(k) space depending on what's tracked
Problem signal: answer many range-sum queries on a static array efficiently
Answer: Prefix Sum array — precompute cumulative sums once so any range sum(i,j) = prefix[j] - prefix[i-1]
O(n) preprocessing, O(1) per query, O(n) extra space
What is the formula for building a prefix sum array?
Answer: prefix[i] = prefix[i-1] + arr[i], with prefix[-1] = 0; then sum(i,j) = prefix[j] - prefix[i-1]
prefix[i] stores the cumulative sum of arr[0..i]. Example: arr=[1,2,3,4] → prefix=[1,3,6,10]; sum(1,3)=prefix[3]-prefix[0]=10-1=9.
Problem signal: find a subarray (possibly with negative numbers) that sums to exactly k
Answer: Prefix sum combined with a hash map storing counts of prefix sums seen so far; check if (currentSum - k) exists in the map
O(n) time, O(n) space; works even with negative numbers unlike a pure sliding window
Problem signal: repeated range-sum queries on a 2D matrix
Answer: 2D prefix sum (integral image) — precompute cumulative sums over rows and columns for O(1) rectangle-sum queries
O(m*n) preprocessing, O(1) per query
Problem signal: find two numbers in an unsorted array that sum to k
Answer: Hash set/map — for each element, check if (k - element) was already seen; then add the current element
O(n) time, O(n) space; avoids the O(n^2) nested-loop brute force
Problem signal: group a list of strings into sets of anagrams
Answer: Hash map keyed by the sorted string (or a character-frequency signature), mapping to a list of original strings
O(n·k log k) time where k = max string length (or O(n·k) using frequency-count keys), O(n·k) space
Problem signal: find the first non-repeating character in a string
Answer: One pass with a hash map to count frequencies, then a second pass to find the first character with count 1
O(n) time, O(1) space for a bounded alphabet
Problem signal: check whether two strings are anagrams of each other
Answer: Compare frequency counts (hash map/array of size 26) in O(n) time, or sort both strings and compare in O(n log n) time
Problem signal: detect whether a linked list contains a cycle
Answer: Fast and Slow Pointers (Floyd's cycle detection) — slow moves 1 step, fast moves 2 steps; if they meet, a cycle exists
O(n) time, O(1) space
Problem signal: find the starting node of a cycle in a linked list
Answer: After fast and slow meet, reset one pointer to the head and advance both one step at a time; they meet again at the cycle's start
O(n) time, O(1) space
Problem signal: find the middle node of a linked list in a single pass
Answer: Fast and slow pointers — fast moves two steps for every one step of slow; when fast reaches the end, slow is at the middle
O(n) time, O(1) space
Problem signal: find the maximum sum of a contiguous subarray
Answer: Kadane's Algorithm — track the best sum ending at the current index, resetting to the current element when the running sum becomes negative
O(n) time, O(1) space. Example: [-2,1,-3,4,-1,2,1,-5,4] → max subarray sum = 6, from [4,-1,2,1].
What is the core recurrence in Kadane's algorithm?
Answer: max_ending_here = max(arr[i], max_ending_here + arr[i]); max_so_far = max(max_so_far, max_ending_here)
At each index you decide whether to extend the previous subarray or start a new one at the current element.
How is Kadane's algorithm adapted for maximum PRODUCT subarray?
Answer: Track both a running maximum and a running minimum ending at the current index, since multiplying two negatives can flip a minimum into the new maximum
O(n) time, O(1) space
Problem signal: merge all overlapping intervals in a list
Answer: Sort intervals by start time, then iterate and merge the current interval into the previous one whenever current.start <= previous.end
O(n log n) time (dominated by the sort), O(n) space
Problem signal: insert a new interval into an already sorted, non-overlapping list of intervals
Answer: Single linear scan: copy intervals ending before the new one starts, merge all overlapping intervals into the new one, then copy the rest
O(n) time, O(n) space
When do two intervals [a,b] and [c,d] overlap?
Answer: They overlap if a <= d and c <= b
Problem signal: array holds numbers from 1..n (or 0..n-1); find the missing or duplicate number
Answer: Cyclic Sort — place each value v at its correct index (index v-1), then scan for the index where the value doesn't match
O(n) time, O(1) space; works because each number maps to exactly one correct slot
Problem signal: find the first missing positive integer in an unsorted array
Answer: Use cyclic sort to place numbers 1..n at their correct indices, then scan for the first index i where arr[i] != i+1
O(n) time, O(1) space
Problem signal: find a target value in a sorted array
Answer: Standard Binary Search — compare the middle element to the target and discard the half that cannot contain it, repeating until found
O(log n) time, O(1) space
Problem signal: find the leftmost (or rightmost) occurrence of a target in a sorted array with duplicates
Answer: Modified binary search — on a match, don't stop; keep searching the left half (for leftmost) or right half (for rightmost)
O(log n) time
Problem signal: search for a target in a rotated sorted array
Answer: Modified binary search — determine which half (left or right of mid) is sorted, then check if the target lies within that half's value range
O(log n) time, O(1) space
Problem signal: find the minimum element or a peak in a rotated/bitonic array
Answer: Binary search that compares the middle element to its neighbors (or to the array's boundary value) to decide which half to discard
O(log n) time
Problem signal: find the next greater element for every element in an array
Answer: Monotonic (decreasing) Stack — pop elements smaller than the current one, since the current element is their 'next greater'; then push the current element
O(n) time overall because each element is pushed and popped at most once (amortized), O(n) space
Problem signal: largest rectangle area in a histogram
Answer: Monotonic (increasing) Stack of indices — pop when the current bar is shorter than the stack top, computing area using the popped bar's height and the current index as the right boundary
O(n) time, O(n) space
What invariant does a monotonic stack maintain, and why pop before pushing?
Answer: The stack elements stay in strictly increasing or strictly decreasing order; any element that would violate this is popped first, and that pop event itself usually answers a query (e.g. 'next greater/smaller')
Make your own deck like this
Upload a PDF, Word doc, or slides and Quizcard writes the cards for you, or build them by hand. Free to start, no credit card required.