1. Contains Duplicate II
Easy · LC 219
Given an integer array and an integer k, decide whether two equal values exist at indices at most k apart. Slide a window of the last k elements as a hash set: check membership before adding each element, and once the set exceeds size k evict the element that fell out of range. The rolling eviction bounds memory at O(min(n, k)) and keeps every check O(1), instead of comparing all pairs.
def contains_nearby_duplicate(nums: list[int], k: int) -> bool:
"""LC 219. Contains Duplicate II.
Keep a rolling set of the last k values: a membership hit before
insertion means two equal values sit at most k indices apart. Once
the set exceeds k entries, evict the value that fell out of range.
O(n) time, O(min(n, k)) space.
"""
last_k_values: set[int] = set()
for index, num in enumerate(nums):
if num in last_k_values:
return True
last_k_values.add(num)
if len(last_k_values) > k:
# nums[index - k] just slid out of range; evicting it caps the
# set at k entries so every future hit is a true near-duplicate.
last_k_values.remove(nums[index - k])
return False
// LC 219. Hash set of the last k values; membership check before insert
// finds a duplicate within range, eviction bounds memory at O(min(n, k)).
bool containsNearbyDuplicate(vector<int> nums, int k) {
unordered_set<int> window; // values at indices [i - k, i - 1]
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
if (i > k) window.erase(nums[i - k - 1]); // evict the value that fell out of range
if (!window.insert(nums[i]).second) return true;
}
return false;
}
/// LC 219. Rolling HashSet of the last k elements: evict the element that
/// fell out of range before each membership check, so memory stays
/// O(min(n, k)) and every check is O(1).
pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
let k = k as usize;
let mut window = HashSet::new();
for (i, &num) in nums.iter().enumerate() {
// nums[i - k - 1] is now more than k indices behind -- drop it.
if i > k {
window.remove(&nums[i - k - 1]);
}
if !window.insert(num) {
return true;
}
}
false
}
/** LC 219. Set of the last k values: check before adding, evict on overflow. */
export function containsNearbyDuplicate(nums: number[], k: number): boolean {
const window = new Set<number>();
for (let i = 0; i < nums.length; i++) {
if (window.has(nums[i])) return true;
window.add(nums[i]);
if (window.size > k) window.delete(nums[i - k]); // evict the value that fell out of range
}
return false;
}
// LC 219. Hash set of the last k values; membership check before insert
// finds a duplicate within range, eviction bounds memory at O(min(n, k)).
func containsNearbyDuplicate(nums []int, k int) bool {
window := map[int]struct{}{} // values at indices [i - k, i - 1]
for i, num := range nums {
if i > k {
delete(window, nums[i-k-1]) // evict the value that fell out of range
}
if _, seen := window[num]; seen {
return true
}
window[num] = struct{}{}
}
return false
}
// LC 219. Hash set of the last k values; a membership hit before insert is a
// duplicate within range, eviction bounds memory at O(min(n, k)).
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
var window = Set<Int>() // values at indices [i - k, i - 1]
for i in 0..<nums.count {
if i > k { window.remove(nums[i - k - 1]) } // evict the value that fell out of range
if !window.insert(nums[i]).inserted { return true }
}
return false
}
2. Best Time to Buy And Sell Stock
Easy · LC 121
Given daily stock prices, choose one day to buy and a later day to sell, returning the maximum profit or zero if no profit is possible. Sweep once, tracking the minimum price seen so far and the best difference between the current price and that minimum. The invariant is that for each day the running minimum is the optimal buy among all earlier days, so a single O(n) pass with two variables suffices.
def max_profit(prices: list[int]) -> int:
"""LC 121. Best Time to Buy and Sell Stock.
One pass tracking the minimum price seen so far: that running
minimum is the optimal buy among all earlier days, so the answer is
the best of price - min_price_so_far across the sweep. O(n) time,
O(1) space.
"""
min_price_so_far = prices[0]
best_profit = 0
for price in prices[1:]:
best_profit = max(best_profit, price - min_price_so_far)
min_price_so_far = min(min_price_so_far, price)
return best_profit
// LC 121. One pass: the running minimum is the optimal buy among all
// earlier days, so two variables replace the all-pairs comparison.
int maxProfit(vector<int> prices) {
int lowestSoFar = prices[0], bestProfit = 0;
for (int price : prices) {
bestProfit = max(bestProfit, price - lowestSoFar);
lowestSoFar = min(lowestSoFar, price);
}
return bestProfit;
}
/// LC 121. One pass with two variables: the running minimum is the optimal
/// buy among all earlier days, so today's best sell is price minus that.
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut min_price_so_far = i32::MAX;
let mut best_profit = 0;
for price in prices {
min_price_so_far = min_price_so_far.min(price);
best_profit = best_profit.max(price - min_price_so_far);
}
best_profit
}
/** LC 121. One pass: the running minimum is the optimal buy for each day. */
export function maxProfit(prices: number[]): number {
let minPriceSoFar = prices[0];
let bestProfit = 0;
for (let i = 1; i < prices.length; i++) {
bestProfit = Math.max(bestProfit, prices[i] - minPriceSoFar);
minPriceSoFar = Math.min(minPriceSoFar, prices[i]);
}
return bestProfit;
}
// LC 121. One pass: the running minimum is the optimal buy among all
// earlier days, so two variables replace the all-pairs comparison.
func maxProfit(prices []int) int {
lowestSoFar, bestProfit := prices[0], 0
for _, price := range prices {
if price-lowestSoFar > bestProfit {
bestProfit = price - lowestSoFar
}
if price < lowestSoFar {
lowestSoFar = price
}
}
return bestProfit
}
// LC 121. One pass: the running minimum is the optimal buy among all
// earlier days, so two variables replace the all-pairs comparison.
func maxProfit(_ prices: [Int]) -> Int {
var lowestSoFar = prices[0], bestProfit = 0
for price in prices {
bestProfit = max(bestProfit, price - lowestSoFar)
lowestSoFar = min(lowestSoFar, price)
}
return bestProfit
}
3. Longest Substring Without Repeating Characters
Medium · LC 3
Given a string, return the length of the longest substring with no repeated characters. Slide a window with a map from character to last seen index; when the current character was seen at or after the left edge, jump the left edge past that occurrence. The pitfall is moving the left edge backward; taking the maximum of its current position and the jump target keeps it monotonic and the pass O(n).
def length_of_longest_substring(s: str) -> int:
"""LC 3. Longest Substring Without Repeating Characters.
Slide a window with a char -> last seen index map. On a repeat, jump
the left edge just past the previous occurrence instead of creeping
it forward one step at a time. O(n) time, O(alphabet) space.
"""
last_seen: dict[str, int] = {}
window_start = 0
longest = 0
for window_end, char in enumerate(s):
if char in last_seen:
# max() keeps window_start monotonic: a repeat already LEFT of
# the window must not drag the edge backward.
window_start = max(window_start, last_seen[char] + 1)
last_seen[char] = window_end
longest = max(longest, window_end - window_start + 1)
return longest
// LC 3. Map each character to the index it was last seen at; on a repeat,
// jump the window start past that occurrence.
int lengthOfLongestSubstring(string s) {
vector<int> lastSeen(128, -1); // character -> last index it appeared at
int windowStart = 0, longest = 0;
for (int i = 0; i < static_cast<int>(s.size()); ++i) {
// max() keeps windowStart monotonic: a stale lastSeen entry left of
// the window must never drag the start backward (e.g. "abba").
windowStart = max(windowStart, lastSeen[static_cast<unsigned char>(s[i])] + 1);
longest = max(longest, i - windowStart + 1);
lastSeen[static_cast<unsigned char>(s[i])] = i;
}
return longest;
}
/// LC 3. Window with a last-seen-index table: on a repeat inside the window,
/// jump the left edge past the previous occurrence. Never move the left edge
/// backward -- a repeat behind window_start is already excluded.
pub fn length_of_longest_substring(s: String) -> i32 {
let bytes = s.as_bytes(); // constraints are ASCII, so bytes are chars
let mut last_seen = [usize::MAX; 128];
let mut window_start = 0;
let mut best = 0;
for (i, &b) in bytes.iter().enumerate() {
let prev = last_seen[b as usize];
// Only jump forward; jumping back would re-admit other repeats.
if prev != usize::MAX && prev >= window_start {
window_start = prev + 1;
}
last_seen[b as usize] = i;
best = best.max(i - window_start + 1);
}
best as i32
}
/** LC 3. Map char -> last index; jump the left edge past a repeat, never back. */
export function lengthOfLongestSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let windowStart = 0;
let best = 0;
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const ch = s[windowEnd];
// max() keeps windowStart monotone: a stale lastSeen entry to the left of
// the window must not drag it backward
windowStart = Math.max(windowStart, (lastSeen.get(ch) ?? -1) + 1);
lastSeen.set(ch, windowEnd);
best = Math.max(best, windowEnd - windowStart + 1);
}
return best;
}
// LC 3. Map each character to the index it was last seen at; on a repeat,
// jump the window start past that occurrence.
func lengthOfLongestSubstring(s string) int {
var lastSeen [128]int // character -> last index it appeared at
for i := range lastSeen {
lastSeen[i] = -1
}
windowStart, longest := 0, 0
for i := 0; i < len(s); i++ {
// the max keeps windowStart monotonic: a stale lastSeen entry left of
// the window must never drag the start backward (e.g. "abba").
if lastSeen[s[i]]+1 > windowStart {
windowStart = lastSeen[s[i]] + 1
}
if i-windowStart+1 > longest {
longest = i - windowStart + 1
}
lastSeen[s[i]] = i
}
return longest
}
// LC 3. Map each character to the index it was last seen at; on a repeat,
// jump the window start past that occurrence.
func lengthOfLongestSubstring(_ s: String) -> Int {
let chars = Array(s)
var lastSeen: [Character: Int] = [:] // character -> last index it appeared at
var windowStart = 0, longest = 0
for windowEnd in 0..<chars.count {
if let previous = lastSeen[chars[windowEnd]] {
// max() keeps windowStart monotonic: a stale entry left of the
// window must never drag the start backward (e.g. "abba").
windowStart = max(windowStart, previous + 1)
}
longest = max(longest, windowEnd - windowStart + 1)
lastSeen[chars[windowEnd]] = windowEnd
}
return longest
}
4. Longest Repeating Character Replacement
Medium · LC 424
Given an uppercase string and an integer k, return the longest substring length achievable by changing at most k characters so all match. Expand a window with per-letter counts, tracking maxFreq, the highest single-letter count in the window, and shrink from the left while window length minus maxFreq exceeds k. The subtle point is that maxFreq need not decrease when shrinking, since a stale value only blocks growth and the recorded best stays valid.
def character_replacement(s: str, k: int) -> int:
"""LC 424. Longest Repeating Character Replacement.
A window is fixable with k changes iff its length minus the count of
its most frequent letter is at most k. Expand right; when that
invariant breaks, slide the left edge by one. max_freq_in_window is
never recomputed downward on shrink -- a stale (too large) value
only blocks the window from growing, and the best length it
justified was already recorded. O(n) time, O(26) space.
"""
letter_counts: dict[str, int] = {}
window_start = 0
max_freq_in_window = 0
longest = 0
for window_end, letter in enumerate(s):
letter_counts[letter] = letter_counts.get(letter, 0) + 1
max_freq_in_window = max(max_freq_in_window, letter_counts[letter])
# Replacements needed == window length minus the dominant letter's
# count; more than k means the window must slide right.
if (window_end - window_start + 1) - max_freq_in_window > k:
letter_counts[s[window_start]] -= 1
window_start += 1
longest = max(longest, window_end - window_start + 1)
return longest
// LC 424. A window works when length - (count of its most common letter)
// <= k, i.e. everything else can be repainted within budget.
int characterReplacement(string s, int k) {
int letterCount[26] = {};
int windowStart = 0, maxFreqInWindow = 0, longest = 0;
for (int windowEnd = 0; windowEnd < static_cast<int>(s.size()); ++windowEnd) {
maxFreqInWindow = max(maxFreqInWindow, ++letterCount[s[windowEnd] - 'A']);
// maxFreqInWindow is never recomputed on shrink: a stale (too high)
// value only keeps the window at a length it already achieved, and
// the answer can only grow once a genuinely higher freq appears.
if (windowEnd - windowStart + 1 - maxFreqInWindow > k)
--letterCount[s[windowStart++] - 'A'];
longest = max(longest, windowEnd - windowStart + 1);
}
return longest;
}
/// LC 424. Window with per-letter counts: it is valid while
/// length - max_freq_in_window <= k (everything but the majority letter is
/// replaceable). The window never shrinks below the best length found.
pub fn character_replacement(s: String, k: i32) -> i32 {
let bytes = s.as_bytes();
let mut counts = [0i32; 26];
let mut max_freq_in_window = 0;
let mut window_start = 0;
let mut best = 0;
for window_end in 0..bytes.len() {
counts[(bytes[window_end] - b'A') as usize] += 1;
max_freq_in_window = max_freq_in_window.max(counts[(bytes[window_end] - b'A') as usize]);
// max_freq_in_window is never decreased on shrink: a stale (too-big)
// value only stops the window growing, and the recorded best from
// when it was accurate stays valid -- so one step of shrink suffices.
if (window_end - window_start + 1) as i32 - max_freq_in_window > k {
counts[(bytes[window_start] - b'A') as usize] -= 1;
window_start += 1;
}
best = best.max((window_end - window_start + 1) as i32);
}
best
}
/** LC 424. Valid window iff length - maxFreq <= k; maxFreq never decreases. */
export function characterReplacement(s: string, k: number): number {
const count = new Array<number>(26).fill(0);
const base = "A".charCodeAt(0);
// never decreased on shrink: a stale maxFreqInWindow only blocks growth, and
// the answer already recorded for the true max is still valid
let maxFreqInWindow = 0;
let windowStart = 0;
let best = 0;
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
maxFreqInWindow = Math.max(maxFreqInWindow, ++count[s.charCodeAt(windowEnd) - base]);
while (windowEnd - windowStart + 1 - maxFreqInWindow > k) {
// more than k characters would need replacing: shrink from the left
count[s.charCodeAt(windowStart) - base]--;
windowStart++;
}
best = Math.max(best, windowEnd - windowStart + 1);
}
return best;
}
// LC 424. A window works when length - (count of its most common letter)
// <= k, i.e. everything else can be repainted within budget.
func characterReplacement(s string, k int) int {
var letterCount [26]int
windowStart, maxFreqInWindow, longest := 0, 0, 0
for windowEnd := 0; windowEnd < len(s); windowEnd++ {
letterCount[s[windowEnd]-'A']++
if letterCount[s[windowEnd]-'A'] > maxFreqInWindow {
maxFreqInWindow = letterCount[s[windowEnd]-'A']
}
// maxFreqInWindow is never recomputed on shrink: a stale (too high)
// value only keeps the window at a length it already achieved, and
// the answer can only grow once a genuinely higher freq appears.
if windowEnd-windowStart+1-maxFreqInWindow > k {
letterCount[s[windowStart]-'A']--
windowStart++
}
if windowEnd-windowStart+1 > longest {
longest = windowEnd - windowStart + 1
}
}
return longest
}
// LC 424. A window works when length - (count of its most common letter)
// <= k, i.e. everything else can be repainted within budget.
func characterReplacement(_ s: String, _ k: Int) -> Int {
let chars = Array(s)
var letterCounts: [Character: Int] = [:]
var windowStart = 0, maxFreqInWindow = 0, longest = 0
for windowEnd in 0..<chars.count {
letterCounts[chars[windowEnd], default: 0] += 1
maxFreqInWindow = max(maxFreqInWindow, letterCounts[chars[windowEnd]]!)
// maxFreqInWindow is never recomputed on shrink: a stale (too high)
// value only keeps the window at a length it already achieved, and
// the answer can only grow once a genuinely higher freq appears.
if windowEnd - windowStart + 1 - maxFreqInWindow > k {
letterCounts[chars[windowStart]]! -= 1
windowStart += 1
}
longest = max(longest, windowEnd - windowStart + 1)
}
return longest
}
5. Permutation In String
Medium · LC 567
Given strings s1 and s2, decide whether s2 contains any permutation of s1 as a contiguous substring. Slide a fixed window of length len(s1) across s2, maintaining 26-letter counts for both strings and updating only the entering and leaving characters each step. Tracking a matches counter of how many of the 26 letters agree turns each window comparison into O(1), so the scan is O(n) rather than comparing full count arrays every step.
def check_inclusion(s1: str, s2: str) -> bool:
"""LC 567. Permutation in String.
Slide a fixed window of len(s1) across s2 holding 26-letter counts
for both strings, touching only the entering and leaving letters
each step. A scalar `matches` (how many of the 26 slots agree) makes
every window comparison O(1) instead of a 26-slot scan. O(n) time,
O(26) space.
"""
def letter_slot(letter: str) -> int:
return ord(letter) - ord("a")
if len(s1) > len(s2):
return False
needed_counts = [0] * 26
window_counts = [0] * 26
for letter_of_s1, letter_of_s2 in zip(s1, s2):
needed_counts[letter_slot(letter_of_s1)] += 1
window_counts[letter_slot(letter_of_s2)] += 1
matches = sum(
1 for slot in range(26) if needed_counts[slot] == window_counts[slot]
)
if matches == 26:
return True
for window_end in range(len(s1), len(s2)):
entering = letter_slot(s2[window_end])
leaving = letter_slot(s2[window_end - len(s1)])
# Each slide disturbs at most two slots; `matches` ticks only when a
# slot crosses into or out of exact agreement.
window_counts[entering] += 1
if window_counts[entering] == needed_counts[entering]:
matches += 1
elif window_counts[entering] == needed_counts[entering] + 1:
matches -= 1
window_counts[leaving] -= 1
if window_counts[leaving] == needed_counts[leaving]:
matches += 1
elif window_counts[leaving] == needed_counts[leaving] - 1:
matches -= 1
if matches == 26:
return True
return False
// LC 567. Fixed window of |s1| over s2 with 26-letter counts; a matches
// counter of agreeing letters makes each slide O(1) instead of O(26).
bool checkInclusion(string s1, string s2) {
int n1 = static_cast<int>(s1.size()), n2 = static_cast<int>(s2.size());
if (n1 > n2) return false;
int need[26] = {}, window[26] = {};
for (int i = 0; i < n1; ++i) {
++need[s1[i] - 'a'];
++window[s2[i] - 'a'];
}
int matches = 0;
for (int c = 0; c < 26; ++c) matches += (need[c] == window[c]);
for (int windowEnd = n1; windowEnd < n2; ++windowEnd) {
if (matches == 26) return true;
int entering = s2[windowEnd] - 'a';
if (++window[entering] == need[entering]) ++matches; // letter just came into agreement
else if (window[entering] == need[entering] + 1) --matches; // letter just overshot agreement
int leaving = s2[windowEnd - n1] - 'a';
if (--window[leaving] == need[leaving]) ++matches;
else if (window[leaving] == need[leaving] - 1) --matches;
}
return matches == 26;
}
/// LC 567. Fixed window of len(s1) over s2 with two 26-letter count arrays;
/// a matches counter of agreeing letters makes each slide O(1) instead of
/// re-comparing all 26 counts.
pub fn check_inclusion(s1: String, s2: String) -> bool {
if s1.len() > s2.len() {
return false;
}
let (pattern, haystack) = (s1.as_bytes(), s2.as_bytes());
let mut need_counts = [0i32; 26];
let mut window_counts = [0i32; 26];
for i in 0..pattern.len() {
need_counts[(pattern[i] - b'a') as usize] += 1;
window_counts[(haystack[i] - b'a') as usize] += 1;
}
let mut matches = (0..26).filter(|&i| need_counts[i] == window_counts[i]).count();
if matches == 26 {
return true;
}
for right in pattern.len()..haystack.len() {
let entering = (haystack[right] - b'a') as usize;
window_counts[entering] += 1;
if window_counts[entering] == need_counts[entering] {
matches += 1; // the entering letter just reached agreement
} else if window_counts[entering] == need_counts[entering] + 1 {
matches -= 1; // the entering letter just overshot an agreement
}
let leaving = (haystack[right - pattern.len()] - b'a') as usize;
window_counts[leaving] -= 1;
if window_counts[leaving] == need_counts[leaving] {
matches += 1;
} else if window_counts[leaving] == need_counts[leaving] - 1 {
matches -= 1;
}
if matches == 26 {
return true;
}
}
false
}
/** LC 567. Fixed window of |s1| with 26-counts; a matches counter makes each step O(1). */
export function checkInclusion(s1: string, s2: string): boolean {
if (s1.length > s2.length) return false;
const base = "a".charCodeAt(0);
const targetCount = new Array<number>(26).fill(0);
const windowCount = new Array<number>(26).fill(0);
for (let i = 0; i < s1.length; i++) {
targetCount[s1.charCodeAt(i) - base]++;
windowCount[s2.charCodeAt(i) - base]++;
}
let matches = 0;
for (let c = 0; c < 26; c++) {
if (windowCount[c] === targetCount[c]) matches++;
}
for (let windowEnd = s1.length; windowEnd < s2.length; windowEnd++) {
if (matches === 26) return true;
const entering = s2.charCodeAt(windowEnd) - base;
windowCount[entering]++;
if (windowCount[entering] === targetCount[entering]) matches++;
else if (windowCount[entering] === targetCount[entering] + 1) matches--; // just overshot
const leaving = s2.charCodeAt(windowEnd - s1.length) - base;
windowCount[leaving]--;
if (windowCount[leaving] === targetCount[leaving]) matches++;
else if (windowCount[leaving] === targetCount[leaving] - 1) matches--; // just undershot
}
return matches === 26;
}
// LC 567. Fixed window of |s1| over s2 with 26-letter counts; a matches
// counter of agreeing letters makes each slide O(1) instead of O(26).
func checkInclusion(s1 string, s2 string) bool {
n1, n2 := len(s1), len(s2)
if n1 > n2 {
return false
}
var need, window [26]int
for i := 0; i < n1; i++ {
need[s1[i]-'a']++
window[s2[i]-'a']++
}
matches := 0
for c := 0; c < 26; c++ {
if need[c] == window[c] {
matches++
}
}
for windowEnd := n1; windowEnd < n2; windowEnd++ {
if matches == 26 {
return true
}
entering := s2[windowEnd] - 'a'
window[entering]++
if window[entering] == need[entering] {
matches++ // letter just came into agreement
} else if window[entering] == need[entering]+1 {
matches-- // letter just overshot agreement
}
leaving := s2[windowEnd-n1] - 'a'
window[leaving]--
if window[leaving] == need[leaving] {
matches++
} else if window[leaving] == need[leaving]-1 {
matches--
}
}
return matches == 26
}
// LC 567. Fixed window of |s1| over s2 with 26-letter counts; a matches
// counter of agreeing letters makes each slide O(1) instead of O(26).
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
if s1.count > s2.count { return false }
let pattern = Array(s1), text = Array(s2)
func letterSlot(_ ch: Character) -> Int {
return Int(ch.asciiValue! - UInt8(ascii: "a"))
}
var needed = [Int](repeating: 0, count: 26)
var window = [Int](repeating: 0, count: 26)
for i in 0..<pattern.count {
needed[letterSlot(pattern[i])] += 1
window[letterSlot(text[i])] += 1
}
var matches = 0
for slot in 0..<26 where needed[slot] == window[slot] { matches += 1 }
for windowEnd in pattern.count..<text.count {
if matches == 26 { return true }
let entering = letterSlot(text[windowEnd])
window[entering] += 1
if window[entering] == needed[entering] { matches += 1 } // letter just came into agreement
else if window[entering] == needed[entering] + 1 { matches -= 1 } // letter just overshot agreement
let leaving = letterSlot(text[windowEnd - pattern.count])
window[leaving] -= 1
if window[leaving] == needed[leaving] { matches += 1 }
else if window[leaving] == needed[leaving] - 1 { matches -= 1 }
}
return matches == 26
}
6. Minimum Size Subarray Sum
Medium · LC 209
Given positive integers and a target, return the length of the shortest contiguous subarray whose sum reaches the target, or zero if none does. Expand the window rightward adding elements, and whenever the sum is at least the target, shrink from the left while that still holds, recording the smallest length. Positivity is the key assumption: sums grow with expansion, so both pointers move only forward and the pass is O(n).
def min_sub_array_len(target: int, nums: list[int]) -> int:
"""LC 209. Minimum Size Subarray Sum.
Grow the window rightward; whenever the sum reaches the target,
shrink from the left while it still holds, recording the shortest
length. Positivity is the load-bearing assumption: sums only grow on
expand and only fall on shrink, so both pointers move strictly
forward. O(n) time, O(1) space.
"""
window_sum = 0
window_start = 0
shortest = len(nums) + 1 # sentinel longer than any real window
for window_end, num in enumerate(nums):
window_sum += num
# Shrink greedily: every element is positive, so once the sum drops
# below target no further shrink can restore it.
while window_sum >= target:
shortest = min(shortest, window_end - window_start + 1)
window_sum -= nums[window_start]
window_start += 1
return 0 if shortest == len(nums) + 1 else shortest
// LC 209. All values are positive, so the sum only grows on expand and only
// shrinks on contract; both pointers move forward and the pass is O(n).
int minSubArrayLen(int target, vector<int> nums) {
int windowStart = 0, shortest = INT_MAX;
long long windowSum = 0;
for (int windowEnd = 0; windowEnd < static_cast<int>(nums.size()); ++windowEnd) {
windowSum += nums[windowEnd];
while (windowSum >= target) { // shrink while still valid; every stop is a candidate
shortest = min(shortest, windowEnd - windowStart + 1);
windowSum -= nums[windowStart++];
}
}
return shortest == INT_MAX ? 0 : shortest;
}
/// LC 209. Expand right, and whenever the sum reaches the target shrink from
/// the left while it still holds, recording the smallest length. Positivity
/// is what lets both pointers move only forward.
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
let mut window_sum = 0;
let mut window_start = 0;
let mut best = usize::MAX;
for window_end in 0..nums.len() {
window_sum += nums[window_end];
// All values are positive, so dropping the left element only lowers
// the sum -- keep shrinking while the target is still met.
while window_sum >= target {
best = best.min(window_end - window_start + 1);
window_sum -= nums[window_start];
window_start += 1;
}
}
if best == usize::MAX { 0 } else { best as i32 }
}
/** LC 209. Expand right; shrink left while the sum still reaches the target. */
export function minSubArrayLen(target: number, nums: number[]): number {
let windowSum = 0;
let windowStart = 0;
let best = Infinity;
for (let windowEnd = 0; windowEnd < nums.length; windowEnd++) {
windowSum += nums[windowEnd];
// positivity guarantees shrinking only decreases the sum, so both
// pointers move forward only and the pass is O(n)
while (windowSum >= target) {
best = Math.min(best, windowEnd - windowStart + 1);
windowSum -= nums[windowStart++];
}
}
return best === Infinity ? 0 : best;
}
// LC 209. All values are positive, so the sum only grows on expand and only
// shrinks on contract; both pointers move forward and the pass is O(n).
func minSubArrayLen(target int, nums []int) int {
windowStart, windowSum := 0, 0
shortest := len(nums) + 1 // sentinel longer than any real window
for windowEnd := 0; windowEnd < len(nums); windowEnd++ {
windowSum += nums[windowEnd]
for windowSum >= target { // shrink while still valid; every stop is a candidate
if windowEnd-windowStart+1 < shortest {
shortest = windowEnd - windowStart + 1
}
windowSum -= nums[windowStart]
windowStart++
}
}
if shortest == len(nums)+1 {
return 0
}
return shortest
}
// LC 209. All values are positive, so the sum only grows on expand and only
// shrinks on contract; both pointers move forward and the pass is O(n).
func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
var windowStart = 0, windowSum = 0, shortest = Int.max
for windowEnd in 0..<nums.count {
windowSum += nums[windowEnd]
while windowSum >= target { // shrink while still valid; every stop is a candidate
shortest = min(shortest, windowEnd - windowStart + 1)
windowSum -= nums[windowStart]
windowStart += 1
}
}
return shortest == Int.max ? 0 : shortest
}
7. Find K Closest Elements
Medium · LC 658
Given a sorted array, an integer k, and a value x, return the k elements closest to x in ascending order. Binary search the left edge of the size-k window over positions 0 to n-k, comparing x - arr[mid] with arr[mid+k] - x to decide which direction to move. Comparing raw differences instead of absolute distances is the trick, since it handles the tie-breaking toward smaller elements correctly and yields O(log(n-k) + k) overall.
def find_closest_elements(arr: list[int], k: int, x: int) -> list[int]:
"""LC 658. Find K Closest Elements.
Binary search the LEFT EDGE of the size-k answer window over
[0, n - k]: at each step compare x - arr[mid] against arr[mid+k] - x
to decide which way the window should move. Raw differences (not
absolute distances) bake in the tie-break toward smaller elements.
O(log(n - k) + k) time, O(1) space beyond the answer slice.
"""
edge_low, edge_high = 0, len(arr) - k
while edge_low < edge_high:
edge_mid = (edge_low + edge_high) // 2
# arr[edge_mid] is strictly farther from x than the first element
# past the window, so the window must shift right to include it.
if x - arr[edge_mid] > arr[edge_mid + k] - x:
edge_low = edge_mid + 1
else:
edge_high = edge_mid
return arr[edge_low : edge_low + k]
// LC 658. Binary search the left edge of the size-k window over [0, n - k];
// the window contents are already sorted, so just copy them out.
vector<int> findClosestElements(vector<int> arr, int k, int x) {
int lo = 0, hi = static_cast<int>(arr.size()) - k;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
// Raw differences, not abs(): when arr[mid] and arr[mid + k] tie in
// distance this prefers the left window, matching the smaller-element
// tie-break, and it stays correct when x lies outside the array.
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
return {arr.begin() + lo, arr.begin() + lo + k};
}
/// LC 658. Binary search the LEFT EDGE of the size-k window over 0..=n-k.
/// Compare raw signed gaps, not absolute distances: ties resolve toward the
/// smaller-valued window, matching the required tie-break. O(log(n-k) + k).
pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let k = k as usize;
let (mut lo, mut hi) = (0, arr.len() - k);
while lo < hi {
let mid = (lo + hi) / 2;
// arr[mid + k] is the first element NOT in the window starting at
// mid; if it sits strictly closer to x, the window must move right.
if x - arr[mid] > arr[mid + k] - x {
lo = mid + 1;
} else {
hi = mid;
}
}
arr[lo..lo + k].to_vec()
}
/** LC 658. Binary search the window's left edge over [0, n - k]. */
export function findClosestElements(arr: number[], k: number, x: number): number[] {
let lo = 0;
let hi = arr.length - k;
while (lo < hi) {
const mid = (lo + hi) >> 1;
// raw differences, not absolute values: ties break toward the smaller
// element, so only a strictly closer right neighbor moves the window right
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
return arr.slice(lo, lo + k);
}
// LC 658. Binary search the left edge of the size-k window over [0, n - k];
// the window contents are already sorted, so just copy them out.
func findClosestElements(arr []int, k int, x int) []int {
lo, hi := 0, len(arr)-k
for lo < hi {
mid := lo + (hi-lo)/2
// Raw differences, not abs(): when arr[mid] and arr[mid + k] tie in
// distance this prefers the left window, matching the smaller-element
// tie-break, and it stays correct when x lies outside the array.
if x-arr[mid] > arr[mid+k]-x {
lo = mid + 1
} else {
hi = mid
}
}
return append([]int(nil), arr[lo:lo+k]...)
}
// LC 658. Binary search the left edge of the size-k window over [0, n - k];
// the window contents are already sorted, so just copy them out.
func findClosestElements(_ arr: [Int], _ k: Int, _ x: Int) -> [Int] {
var lo = 0, hi = arr.count - k
while lo < hi {
let mid = lo + (hi - lo) / 2
// Raw differences, not abs(): when arr[mid] and arr[mid + k] tie in
// distance this prefers the left window, matching the smaller-element
// tie-break, and it stays correct when x lies outside the array.
if x - arr[mid] > arr[mid + k] - x { lo = mid + 1 } else { hi = mid }
}
return Array(arr[lo..<(lo + k)])
}
8. Minimum Window Substring
Hard · LC 76
Given strings s and t, return the smallest substring of s containing every character of t with multiplicity, or an empty string. Expand the right edge while tallying characters, and once the count of fully satisfied characters reaches the number required, shrink from the left and record the best window. Tracking have versus need as scalar counters keeps each step O(1), and shrinking eagerly whenever the window is valid is what guarantees minimality.
def min_window(s: str, t: str) -> str:
"""LC 76. Minimum Window Substring.
Expand the right edge while tallying chars. `need` is the number of
distinct chars t demands; `have` counts how many are currently fully
satisfied. The moment have == need, shrink eagerly from the left --
every shrink while still valid can only improve the answer -- and
record the best window seen. O(|s| + |t|) time, O(alphabet) space.
"""
if not t or len(t) > len(s):
return ""
required_counts: dict[str, int] = {}
for char in t:
required_counts[char] = required_counts.get(char, 0) + 1
window_counts: dict[str, int] = {}
need = len(required_counts)
have = 0
best_start, best_length = 0, len(s) + 1 # sentinel: no valid window yet
window_start = 0
for window_end, char in enumerate(s):
window_counts[char] = window_counts.get(char, 0) + 1
# Equality (not >=) makes `have` tick exactly once, at the moment
# this char's demand is first met.
if window_counts[char] == required_counts.get(char, -1):
have += 1
while have == need:
if window_end - window_start + 1 < best_length:
best_start = window_start
best_length = window_end - window_start + 1
leaving = s[window_start]
window_counts[leaving] -= 1
# Dropping below the requirement un-satisfies exactly one char,
# which ends the shrink loop on the next check.
if window_counts[leaving] < required_counts.get(leaving, -1):
have -= 1
window_start += 1
return "" if best_length == len(s) + 1 else s[best_start : best_start + best_length]
// LC 76. Expand right while tallying; once have == need (every distinct
// char of t satisfied with multiplicity), shrink left eagerly and record.
string minWindow(string s, string t) {
if (t.size() > s.size()) return "";
int required[128] = {};
int need = 0; // distinct characters of t that must be satisfied
for (char ch : t)
if (required[static_cast<unsigned char>(ch)]++ == 0) ++need;
int window[128] = {};
int have = 0, windowStart = 0, bestStart = 0, bestLen = INT_MAX;
for (int windowEnd = 0; windowEnd < static_cast<int>(s.size()); ++windowEnd) {
int entering = static_cast<unsigned char>(s[windowEnd]);
if (++window[entering] == required[entering]) ++have; // just reached the needed multiplicity
while (have == need) { // valid window: shrinking eagerly is what guarantees minimality
if (windowEnd - windowStart + 1 < bestLen) {
bestLen = windowEnd - windowStart + 1;
bestStart = windowStart;
}
int leaving = static_cast<unsigned char>(s[windowStart++]);
if (window[leaving]-- == required[leaving]) --have; // dropped below the needed multiplicity
}
}
return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}
/// LC 76. Expand right while tallying; once have == need (every required
/// character fully covered), shrink eagerly from the left and record each
/// valid window -- eager shrinking is what guarantees minimality.
pub fn min_window(s: String, t: String) -> String {
if t.len() > s.len() {
return String::new();
}
let haystack = s.as_bytes();
let mut need_counts = [0i32; 128];
for &b in t.as_bytes() {
need_counts[b as usize] += 1;
}
let need = need_counts.iter().filter(|&&c| c > 0).count();
let mut window_counts = [0i32; 128];
let mut have = 0;
let mut window_start = 0;
let mut best: Option<(usize, usize)> = None;
for window_end in 0..haystack.len() {
let entering = haystack[window_end] as usize;
window_counts[entering] += 1;
// Count a character only at the moment its requirement is exactly
// met; extra copies beyond need must not bump `have` again.
if window_counts[entering] == need_counts[entering] {
have += 1;
}
while have == need {
if best.map_or(true, |(bs, be)| window_end - window_start < be - bs) {
best = Some((window_start, window_end));
}
let leaving = haystack[window_start] as usize;
window_counts[leaving] -= 1;
if window_counts[leaving] < need_counts[leaving] {
have -= 1; // this drop broke validity, ending the shrink
}
window_start += 1;
}
}
best.map_or(String::new(), |(bs, be)| s[bs..=be].to_string())
}
/** LC 76. Expand right tallying chars; once have === need, shrink eagerly. */
export function minWindow(s: string, t: string): string {
if (t.length === 0 || t.length > s.length) return "";
const required = new Map<string, number>();
for (const ch of t) required.set(ch, (required.get(ch) ?? 0) + 1);
const windowCount = new Map<string, number>();
const need = required.size; // distinct characters that must be fully satisfied
let have = 0;
let windowStart = 0;
let bestStart = 0;
let bestLen = Infinity;
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const ch = s[windowEnd];
const newCount = (windowCount.get(ch) ?? 0) + 1;
windowCount.set(ch, newCount);
if (newCount === required.get(ch)) have++; // ch just became fully satisfied
// shrink eagerly while valid: minimality comes from never keeping a
// window one character longer than it has to be
while (have === need) {
if (windowEnd - windowStart + 1 < bestLen) {
bestLen = windowEnd - windowStart + 1;
bestStart = windowStart;
}
const out = s[windowStart];
const outCount = (windowCount.get(out) ?? 0) - 1;
windowCount.set(out, outCount);
if (outCount < (required.get(out) ?? 0)) have--; // out just dropped below its quota
windowStart++;
}
}
return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}
// LC 76. Expand right while tallying; once have == need (every distinct
// char of t satisfied with multiplicity), shrink left eagerly and record.
func minWindow(s string, t string) string {
if len(t) > len(s) {
return ""
}
var required [128]int
need := 0 // distinct characters of t that must be satisfied
for i := 0; i < len(t); i++ {
if required[t[i]] == 0 {
need++
}
required[t[i]]++
}
var window [128]int
have, windowStart, bestStart, bestLen := 0, 0, 0, len(s)+1
for windowEnd := 0; windowEnd < len(s); windowEnd++ {
entering := s[windowEnd]
window[entering]++
if window[entering] == required[entering] {
have++ // just reached the needed multiplicity
}
for have == need { // valid window: shrinking eagerly is what guarantees minimality
if windowEnd-windowStart+1 < bestLen {
bestLen = windowEnd - windowStart + 1
bestStart = windowStart
}
leaving := s[windowStart]
windowStart++
if window[leaving] == required[leaving] {
have-- // about to drop below the needed multiplicity
}
window[leaving]--
}
}
if bestLen == len(s)+1 {
return ""
}
return s[bestStart : bestStart+bestLen]
}
// LC 76. Expand right while tallying; once have == need (every distinct
// char of t satisfied with multiplicity), shrink left eagerly and record.
func minWindow(_ s: String, _ t: String) -> String {
if t.isEmpty || t.count > s.count { return "" }
let chars = Array(s)
var required: [Character: Int] = [:]
for ch in t { required[ch, default: 0] += 1 }
var window: [Character: Int] = [:]
let need = required.count // distinct characters of t that must be satisfied
var have = 0, windowStart = 0, bestStart = 0, bestLen = Int.max
for windowEnd in 0..<chars.count {
let entering = chars[windowEnd]
window[entering, default: 0] += 1
// Equality (not >=) makes have tick exactly once, at the moment
// this char's demand is first met.
if window[entering] == required[entering] { have += 1 }
while have == need { // valid window: shrinking eagerly is what guarantees minimality
if windowEnd - windowStart + 1 < bestLen {
bestLen = windowEnd - windowStart + 1
bestStart = windowStart
}
let leaving = chars[windowStart]
window[leaving]! -= 1
if let req = required[leaving], window[leaving]! < req { have -= 1 } // dropped below the needed multiplicity
windowStart += 1
}
}
return bestLen == Int.max ? "" : String(chars[bestStart..<(bestStart + bestLen)])
}
9. Sliding Window Maximum
Hard · LC 239
Given an integer array and a window size k, return the maximum of each contiguous window as it slides across. Maintain a deque of indices with strictly decreasing values: pop smaller values from the back before pushing each index, drop the front when it exits the window, and read the maximum at the front. Each index enters and leaves the deque at most once, so the pass is O(n) despite the nested-looking pops.
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""LC 239. Sliding Window Maximum.
Keep a deque of indices whose values run strictly decreasing from
front to back, so the front is always the current window's maximum.
Each index enters and leaves the deque at most once, so the pass is
O(n) despite the nested-looking pops. O(k) space.
"""
deque_of_maxima: deque = deque() # indices; values strictly decreasing
window_maxima: list[int] = []
for window_end, num in enumerate(nums):
# A back entry smaller than the newcomer is both older and smaller,
# so it can never be a window maximum again -- discard it. This is
# exactly what keeps the deque's values sorted descending.
while deque_of_maxima and nums[deque_of_maxima[-1]] <= num:
deque_of_maxima.pop()
deque_of_maxima.append(window_end)
if deque_of_maxima[0] <= window_end - k:
deque_of_maxima.popleft() # front index just slid out of the window
if window_end >= k - 1:
window_maxima.append(nums[deque_of_maxima[0]])
return window_maxima
// LC 239. Deque of indices whose values strictly decrease front to back;
// the front is always the current window's maximum.
vector<int> maxSlidingWindow(vector<int> nums, int k) {
deque<int> candidates; // invariant: nums[candidates] strictly decreasing
vector<int> maxima;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
// Anything <= the new value can never be a future maximum, so pop it.
while (!candidates.empty() && nums[candidates.back()] <= nums[i]) candidates.pop_back();
candidates.push_back(i);
if (candidates.front() <= i - k) candidates.pop_front(); // front slid out of the window
if (i >= k - 1) maxima.push_back(nums[candidates.front()]);
}
return maxima;
}
/// LC 239. Monotonic deque of INDICES whose values strictly decrease front
/// to back: the front is always the current window's maximum. Each index is
/// pushed and popped at most once, so the pass is O(n).
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let mut deque: VecDeque<usize> = VecDeque::new();
let mut ans = Vec::with_capacity(nums.len() + 1 - k);
for i in 0..nums.len() {
// A value with a newer, bigger-or-equal value behind it can never be
// a window maximum again -- pop it before pushing the newcomer.
while deque.back().map_or(false, |&j| nums[j] <= nums[i]) {
deque.pop_back();
}
deque.push_back(i);
// The front index expires once it trails the right edge by k.
if *deque.front().unwrap() + k <= i {
deque.pop_front();
}
if i + 1 >= k {
ans.push(nums[*deque.front().unwrap()]);
}
}
ans
}
/** LC 239. Deque of indices with decreasing values; front is the window max. */
export function maxSlidingWindow(nums: number[], k: number): number[] {
const deque: number[] = []; // indices; values strictly decrease front to back
let head = 0; // array + head index stands in for popleft
const ans = new Array<number>(nums.length - k + 1);
for (let i = 0; i < nums.length; i++) {
// a value <= nums[i] behind it can never be a window max again: pop it
while (deque.length > head && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
deque.push(i);
if (deque[head] <= i - k) head++; // front index slid out of the window
if (i >= k - 1) ans[i - k + 1] = nums[deque[head]];
}
return ans;
}
// LC 239. Deque of indices whose values strictly decrease front to back;
// the front is always the current window's maximum.
func maxSlidingWindow(nums []int, k int) []int {
candidates := []int{} // indices; invariant: nums[candidates] strictly decreasing
maxima := make([]int, 0, len(nums)-k+1)
for i, num := range nums {
// Anything <= the new value can never be a future maximum, so pop it.
for len(candidates) > 0 && nums[candidates[len(candidates)-1]] <= num {
candidates = candidates[:len(candidates)-1]
}
candidates = append(candidates, i)
if candidates[0] <= i-k {
candidates = candidates[1:] // front slid out of the window
}
if i >= k-1 {
maxima = append(maxima, nums[candidates[0]])
}
}
return maxima
}
// LC 239. Deque of indices whose values strictly decrease front to back;
// the front is always the current window's maximum. Each index enters and
// leaves at most once, so the pass is O(n) despite the nested-looking pops.
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var candidates: [Int] = [] // indices; values strictly decreasing front to back
var front = 0 // moving head index stands in for a deque's O(1) pop-front
var maxima: [Int] = []
for i in 0..<nums.count {
// Anything <= the new value can never be a future maximum, so pop it.
while candidates.count > front && nums[candidates.last!] <= nums[i] {
candidates.removeLast()
}
candidates.append(i)
if candidates[front] <= i - k { front += 1 } // front index slid out of the window
if i >= k - 1 { maxima.append(nums[candidates[front]]) }
}
return maxima
}