You can buy once and sell once. To maximize profit, buy at the lowest price and sell at the highest price that comes after the buy date.
Traverse the prices once, tracking the minimum price seen so far. At each step, compute the potential profit if selling today and update the global maximum profit.
Updating the minimum and maximum in a single pass avoids nested loops, reducing brute force O(n²) to O(n).
This runs in O(n) time and O(1) space.
function maxProfit(prices) {
let min = Infinity, profit = 0;
for (let p of prices) {
min = Math.min(min, p);
profit = Math.max(profit, p - min);
}
return profit;
}Single-pass min tracking: You never need to look backward — the minimum price so far combined with today's price gives the best possible profit for any sell date up to today.
For multiple transactions (unlimited buys/sells), greedy works: add up all positive differences between consecutive days. For at most k transactions, use DP with state dp[k][day].
Given vertical lines at positions 0..n-1 with given heights, find two lines that form a container holding the most water. Water height = min(left, right); width = distance between the two lines.
Use two pointers starting at the leftmost and rightmost positions. Calculate area = min(height[l], height[r]) * (r - l). Move the pointer with the shorter height inward.
Moving the shorter line gives the only chance of finding a higher container — moving the taller line can only decrease or maintain the width with the same or lower height.
This runs in O(n) time and O(1) space.
function maxArea(height) {
let l = 0, r = height.length - 1, max = 0;
while (l < r) {
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
height[l] < height[r] ? l++ : r--;
}
return max;
}Move shorter pointer: The area is always limited by the shorter line. Moving it inward is the only way to possibly find a line tall enough to increase the area despite decreasing width.
This two-pointer pattern applies whenever you are optimizing a function over pairs (i, j) where i and j can narrow inward based on a comparison result.
Rain water trapped at each position equals the shorter of the maximum heights to its left and right, minus the current bar's height.
The optimal two-pointer approach maintains lMax (max height seen from the left) and rMax (max height from the right). Process the side with the lower max first since that side's water is determined.
If height[l] <= height[r], the left side is the limiting factor; water at l is guaranteed to be lMax - height[l] if height[l] < lMax.
This runs in O(n) time and O(1) space — unlike the O(n) space precomputed left/right max arrays approach.
function trap(height) {
let l = 0, r = height.length - 1, lMax = 0, rMax = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
height[l] >= lMax ? lMax = height[l] : water += lMax - height[l];
l++;
} else {
height[r] >= rMax ? rMax = height[r] : water += rMax - height[r];
r--;
}
}
return water;
}Process lower side first: Processing the side with the smaller max guarantees we know the exact maximum boundary on that side — the other side is always at least as tall.
The O(n) space solution precomputes leftMax[i] and rightMax[i] arrays, which is easier to understand and verify, though less space-efficient.
Each element specifies the maximum number of positions you can jump forward from that index. Determine if you can reach the last index from the first.
Track the farthest position reachable at any point. If you ever reach a position beyond the farthest reachable (i.e., a "dead zone"), return false immediately.
If you can always reach or pass position i, the farthest updates to include positions reachable from i: farthest = max(farthest, i + nums[i]).
This runs in O(n) time and O(1) space.
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}Farthest reachable tracking: A single variable farthest replaces the need for a visited array — if i > farthest, the position is unreachable regardless of previous jumps.
Jump Game II extends this to count minimum jumps — use a greedy BFS where each "level" represents one jump and extend the level boundary when you cross the current end.
At each gas station you gain gas[i] and spend cost[i] to reach the next station. Find the starting station that allows completing the full circle, or return -1.
If total gas < total cost across all stations, the trip is impossible regardless of the starting point. Otherwise, a unique valid start exists.
Track running tank surplus. Whenever it goes negative, all starting points from the current "start" through the current station are invalid — reset start to i+1.
This runs in O(n) time and O(1) space with a single pass.
function canCompleteCircuit(gas, cost) {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
let diff = gas[i] - cost[i];
total += diff; tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}Greedy start reset: A negative tank means no starting point within the current segment can work — the segment deficit must be overcome by a later segment, so start moves forward.
The total gas check is the key insight: if you can accumulate a non-negative total surplus, the greedily-found start is guaranteed to be a valid solution.
Given meeting intervals, determine if one person can attend all of them without any overlap. If any two meetings overlap in time, it is impossible.
Sort intervals by start time. Check if any meeting starts before the previous one ends: if intervals[i][0] < intervals[i-1][1], there is a conflict.
For the variant "minimum meeting rooms needed", use a min-heap of end times: if the next meeting starts before the earliest-ending meeting, it needs a new room. Otherwise, reuse the room of the earliest-ending meeting.
Attendance check runs in O(n log n) for sorting; room count runs in O(n log n) with a heap.
function canAttendAll(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; i++)
if (intervals[i][0] < intervals[i-1][1]) return false;
return true;
}Sort and single scan: Sorting by start time makes overlaps immediately detectable — if the next start is before the previous end, a conflict exists.
The min-heap "rooms needed" variant is a classic interview problem: extract the min end time, and if the new meeting starts before it, no room is free — add a room and push both times.
Given a list of intervals, merge all overlapping or adjacent intervals and return a list of non-overlapping intervals covering the same range.
Sort intervals by start time. Maintain a result list. If the current interval's start <= the last added interval's end, they overlap — extend the last interval's end to the maximum of both ends.
If they do not overlap, append the current interval as a new non-overlapping entry.
This runs in O(n log n) for sorting and O(n) for the merge scan.
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let res = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let last = res[res.length - 1];
if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
else res.push(intervals[i]);
}
return res;
}Sort then scan: After sorting, only the immediately previous interval needs to be compared — a non-sorted list would require O(n²) comparisons to detect all overlaps.
Use Math.max(last[1], current[1]) for the end — not just current[1], since a smaller interval may be completely contained within the previous one.
Given tasks with a cooldown period n between identical tasks, find the minimum total time (CPU intervals) to complete all tasks in any order.
The bottleneck is the most frequent task. If it appears maxF times, you need at least (maxF - 1) * (n + 1) slots. Other tasks fill the idle slots. The answer is max of this frame and the total task count.
Sort tasks by frequency. The top count determines the number of "frames". Each frame has n+1 slots. Remaining idle slots after filling with other tasks add to the total.
This runs in O(n) time where n is the number of tasks (after sorting the 26 frequency buckets in O(1)).
function leastInterval(tasks, n) {
let freq = Array(26).fill(0);
for (let t of tasks) freq[t.charCodeAt(0) - 65]++;
freq.sort((a, b) => b - a);
let maxF = freq[0] - 1, idle = maxF * n;
for (let i = 1; i < 26 && freq[i] > 0; i++)
idle -= Math.min(maxF, freq[i]);
return Math.max(tasks.length, tasks.length + idle);
}Idle slot calculation: Start with maxF * n idle slots and subtract tasks that can fill them. Remaining idle slots add to total time since the CPU must wait during them.
If idle becomes negative after filling with other tasks, no idle time is needed — Math.max(tasks.length, tasks.length + idle) correctly returns just the task count in that case.
The sliding window maximum requires finding the maximum in each contiguous subarray of size k. The brute force O(nk) approach is too slow for large inputs.
Use a deque (double-ended queue) of indices. Maintain the deque as monotonically decreasing by values. Remove indices outside the current window from the front. Remove smaller values from the back when adding a new element.
The front of the deque is always the index of the maximum in the current window.
This runs in O(n) time since each index is added and removed from the deque at most once.
function maxSlidingWindow(nums, k) {
let deque = [], res = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && deque[0] < i - k + 1) deque.shift();
while (deque.length && nums[deque[deque.length-1]] < nums[i]) deque.pop();
deque.push(i);
if (i >= k - 1) res.push(nums[deque[0]]);
}
return res;
}Monotonic deque: Keeping values in decreasing order from front to back ensures the front is always the maximum. Smaller values behind the new element will never be the maximum while the new element is in the window.
Start collecting results only when i >= k-1 (first complete window). Earlier indices are "warming up" the deque with partially filled windows.
A rotated sorted array was originally sorted but then shifted at some pivot — for example [4,5,6,7,0,1,2] was originally [0,1,2,4,5,6,7].
Use binary search. Compare mid with the right boundary: if mid > right, the minimum is in the right half. Otherwise, it is in the left half (including mid).
This works because at least one half of the array is always normally sorted, and the minimum is always in the unsorted portion.
This runs in O(log n) time — far better than the O(n) linear scan.
function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = Math.floor((lo + hi) / 2);
nums[mid] > nums[hi] ? lo = mid + 1 : hi = mid;
}
return nums[lo];
}Compare to right boundary: Using nums[mid] vs nums[hi] (not nums[lo]) avoids the ambiguity when lo = mid — always reduces the search space by at least one element.
For the variant "find a target in a rotated sorted array", first determine which half is sorted, then check if the target falls in that sorted half to decide which side to search.
Balloons are represented as intervals [left, right]. An arrow at position x bursts all balloons where left ≤ x ≤ right. Find the minimum arrows needed to burst all balloons.
Sort by end coordinate. Fire the first arrow at the end of the first balloon. Skip all subsequent balloons whose start ≤ current arrow position. When a balloon starts after the arrow, fire a new arrow at that balloon's end.
This greedy approach fires as late as possible to maximize the number of balloons each arrow can pierce.
This runs in O(n log n) for sorting and O(n) for the scan.
function findMinArrowShots(points) {
if (!points.length) return 0;
points.sort((a, b) => a[1] - b[1]);
let arrows = 1, end = points[0][1];
for (let i = 1; i < points.length; i++) {
if (points[i][0] > end) { arrows++; end = points[i][1]; }
}
return arrows;
}Sort by end, fire at end: Sorting by end coordinate groups overlapping balloons optimally — the greedy choice of firing at the earliest end maximizes overlap with future balloons.
This is equivalent to the "minimum number of intervals to cover all intervals" problem — a classic interval scheduling greedy pattern.
Given a set of intervals, find the minimum number to remove so that the remaining intervals do not overlap. Equivalently, maximize the number of non-overlapping intervals you can keep.
Sort intervals by end time. Greedily keep intervals that end earliest (they leave maximum room for future intervals). Count how many intervals you skip — those are the removed ones.
This is identical to the Activity Selection Problem, a foundational greedy algorithm.
This runs in O(n log n) for sorting and O(n) for the greedy scan.
function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[1] - b[1]);
let count = 0, end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) count++;
else end = intervals[i][1];
}
return count;
}Sort by end, keep earliest finish: The activity selection greedy works because choosing the interval that ends earliest maximizes the remaining timeline for subsequent intervals.
The minimum removals equals total intervals minus the maximum non-overlapping count — you can also compute the latter directly and subtract from n.
Each element in the array specifies the maximum jump distance from that position. Find the minimum number of jumps to reach the last index.
Use a greedy BFS-like approach. Track the current boundary (farthest reach of the current jump) and the next boundary (farthest reachable from anywhere within the current jump). When you reach the current boundary, increment jumps and update it to the next boundary.
This is equivalent to level-order BFS where each "level" represents one jump reach.
This runs in O(n) time and O(1) space.
function jump(nums) {
let jumps = 0, currEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currEnd) { jumps++; currEnd = farthest; }
}
return jumps;
}Greedy level expansion: Each time you reach the current jump boundary, you must make another jump — the best choice is to jump to the farthest recorded position.
The loop ends at nums.length - 1, not nums.length, to avoid incrementing jumps unnecessarily after already reaching the last index.
Each child must get at least one candy. Children with a higher rating than their neighbor must get more candies than that neighbor. Find the minimum total candies needed.
Use two passes on the ratings array. Forward pass: give more candy than the left neighbor whenever the rating is higher. Backward pass: ensure right-to-left constraint is satisfied by taking the max of current candy and right+1.
Two passes are necessary because satisfying the left constraint can violate the right constraint and vice versa.
This runs in O(n) time and O(n) space for the candy array.
function candy(ratings) {
let n = ratings.length, candies = Array(n).fill(1);
for (let i = 1; i < n; i++)
if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
for (let i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);
return candies.reduce((a, b) => a + b, 0);
}Two-pass approach: The forward pass fixes left constraints and the backward pass fixes right constraints — taking max in the backward pass preserves already-satisfied left constraints.
A one-pass O(1) space solution exists using peak/valley analysis, but the two-pass approach is clearer and easier to implement correctly in interviews.
Given a string, partition it into as many parts as possible so that each letter appears in at most one part. Find the sizes of all such partitions.
Use a greedy approach: record the last occurrence of each character. For the current partition, track the farthest last occurrence of any character seen so far. When the current index reaches this farthest point, the partition ends there.
This ensures letters that appear later force the current partition to extend — a greedy max-reach strategy.
This runs in O(n) time and O(1) space (the last-occurrence map is always at most 26 entries).
function partitionLabels(s) {
let last = {};
for (let i = 0; i < s.length; i++) last[s[i]] = i;
let result = [], start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]);
if (i === end) { result.push(end - start + 1); start = i + 1; }
}
return result;
}Last occurrence boundary: As you scan, extending end to the farthest last-occurrence of any character guarantees no character in the current partition appears in a later one.
This is a single-scan greedy algorithm — no sorting needed, just two O(n) passes: one to build the last-occurrence map and one to determine partition boundaries.
Cars are driving toward a destination. Each car has a position and speed. Cars merge into a fleet when a faster car catches up to a slower one. Find the number of fleets that arrive.
Cars driving to the same destination are best analyzed in reverse order of position (closest to destination first). Calculate the time each car would take to arrive. A car merges into the fleet ahead if it arrives earlier than or at the same time.
Use a stack (or count variable). If the current car takes more time than the top of the stack, it forms a new fleet.
This runs in O(n log n) for sorting and O(n) for the stack scan.
function carFleet(target, position, speed) {
let n = position.length;
let cars = position.map((p, i) => [p, speed[i]]);
cars.sort((a, b) => b[0] - a[0]);
let stack = [], fleets = 0;
for (let [pos, spd] of cars) {
let time = (target - pos) / spd;
if (!stack.length || time > stack[stack.length-1]) { stack.push(time); fleets++; }
}
return fleets;
}Sort by position descending: Processing cars closest to the destination first determines which cars can catch up before reaching it vs which form their own fleet.
A car forms a new fleet only if its arrival time is strictly greater than the leading car's time — equal or less means it catches up and merges.
Given gas stations in a circle, each with available gas and associated cost, find the starting station (if one exists) that allows completing the full circle.
If the total gas is less than the total cost, no solution exists. Otherwise, a solution is guaranteed. Use a greedy approach: traverse stations tracking running surplus. When the surplus goes negative, the starting point must be after the current station.
The running surplus going negative means no starting point from the current segment works.
This runs in O(n) time and O(1) space.
function canCompleteCircuit(gas, cost) {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
let diff = gas[i] - cost[i];
total += diff; tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}Greedy start reset: When the tank goes negative, all starting points from the initial start to the current station are invalid — the next valid candidate must be i+1.
The total gas check guarantees that if total ≥ 0, the greedy start found is the unique valid answer — there is always exactly one or zero solutions.
To maximize the sum after flipping rows and columns, treat each row as a binary number and maximize the total binary value. This is a greedy problem — each decision is locally optimal.
First, flip any row whose first bit is 0 (making the most significant bit 1 maximizes value). Then for each column, flip it if more than half the values are 0 (maximizing the column's contribution).
Row flips take priority because the most significant bit contributes more than all other bits combined.
This runs in O(m × n) time and O(1) extra space.
function matrixScore(grid) {
let m = grid.length, n = grid[0].length;
for (let i = 0; i < m; i++)
if (grid[i][0] === 0) for (let j = 0; j < n; j++) grid[i][j] ^= 1;
let score = 0;
for (let j = 0; j < n; j++) {
let ones = grid.reduce((sum, row) => sum + row[j], 0);
score += Math.max(ones, m - ones) * (1 << (n - 1 - j));
}
return score;
}Greedily maximize each column: After fixing row-0 to all 1s, decide per column whether more 1s or 0s contribute more value — single-column flips are independent decisions.
The value of column j is 2^(n-1-j); multiplying by max(ones, m-ones) gives the maximum column contribution regardless of whether you flip it.
Given arrival and departure times of trains, find the minimum number of platforms required so no train has to wait. This is an interval scheduling resource problem.
Sort arrivals and departures separately. Use two pointers. When the next arrival is before the next departure, a new platform is needed. When an arrival is after a departure, a platform is freed.
Track the current platforms in use and update the maximum seen at any point.
This runs in O(n log n) for sorting and O(n) for the two-pointer scan.
function findPlatforms(arrivals, departures) {
arrivals.sort((a, b) => a - b);
departures.sort((a, b) => a - b);
let platforms = 0, maxPlatforms = 0, i = 0, j = 0;
while (i < arrivals.length) {
if (arrivals[i] <= departures[j]) { platforms++; i++; }
else { platforms--; j++; }
maxPlatforms = Math.max(maxPlatforms, platforms);
}
return maxPlatforms;
}Merge-sorted two-pointer: Sorting arrivals and departures independently and processing them together in time order simulates events as they happen at the station.
This problem is equivalent to "maximum number of overlapping intervals at any point in time" — a classic interval problem with real-world scheduling applications.
In the Jump Game variant (minimum jumps), you need the minimum number of jumps to reach the last position. The greedy BFS approach works in O(n) without DP.
Think of positions reachable from position i as the "frontier" of jump j. Extend the frontier greedily to the maximum reachable position. Each frontier extension counts as one more jump.
The key invariant: when you cross the current jump boundary, you must commit to a jump and the new boundary is the farthest position you have found.
This runs in O(n) time and O(1) space.
function minJumps(nums) {
let jumps = 0, currEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (farthest >= nums.length - 1) return jumps + 1;
if (i === currEnd) { jumps++; currEnd = farthest; }
}
return jumps;
}Early termination: If the farthest reachable position already covers the last index, return immediately without processing remaining positions.
If currEnd is never updated beyond a certain point, it means the last index is unreachable — handle this by checking if jumps stay 0 with nums.length > 1 as a reachability guard.
Each child has a greed factor (minimum cookie size they need to be content). Each cookie has a size. Find the maximum number of children you can content using the available cookies.
Sort both arrays. Use two pointers. Try to assign the smallest available cookie that satisfies the greediest unsatisfied child — assigning a larger cookie than necessary would waste it.
Actually, greedily assign the smallest sufficient cookie to the child with the smallest greed factor — sort both and match from smallest to smallest.
This runs in O(n log n + m log m) for sorting and O(n + m) for the two-pointer scan.
function findContentChildren(greed, cookies) {
greed.sort((a, b) => a - b);
cookies.sort((a, b) => a - b);
let child = 0, cookie = 0;
while (child < greed.length && cookie < cookies.length) {
if (cookies[cookie] >= greed[child]) child++;
cookie++;
}
return child;
}Two-pointer on sorted arrays: Matching smallest greed to smallest sufficient cookie is optimal — a smaller cookie can satisfy a less greedy child, leaving larger cookies for greedier children.
This is a canonical greedy matching problem: whenever the greedy choice (smallest sufficient) is locally optimal in sorted order, the globally optimal solution is achieved.