1. Reverse String
Easy · LC 344
Given a character array, reverse it in place using O(1) extra memory. Put one pointer at the first index and one at the last, swap the characters, and walk both inward until they meet or cross. The only detail is the loop condition: left < right handles both even and odd lengths, since the middle character of an odd-length array needs no swap.
def reverse_string(s: list[str]) -> None:
"""LC 344. Reverse String.
Two pointers from the ends, swapping inward until they meet.
Strict left < right handles odd and even lengths alike: the middle
character of an odd-length array needs no swap. O(n) time, O(1)
space, in place.
"""
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
// LC 344. Swap the ends and walk inward; left < right also covers odd lengths.
void reverseString(vector<char>& s) {
int left = 0, right = static_cast<int>(s.size()) - 1;
while (left < right) swap(s[left++], s[right--]); // the middle char of an odd length needs no swap
}
/// LC 344. Swap the ends and walk both pointers inward; left < right covers
/// even and odd lengths alike, since the middle char of an odd-length array
/// needs no swap.
pub fn reverse_string(s: &mut Vec<char>) {
if s.is_empty() {
return; // s.len() - 1 below would underflow usize
}
let (mut left, mut right) = (0, s.len() - 1);
while left < right {
s.swap(left, right);
left += 1;
right -= 1;
}
}
/** LC 344. Swap the ends inward; front < back also skips the odd middle char. */
export function reverseString(s: string[]): void {
let front = 0;
let back = s.length - 1;
while (front < back) {
[s[front], s[back]] = [s[back], s[front]];
front++;
back--;
}
}
// LC 344. Swap the ends and walk inward; left < right also covers odd lengths.
func reverseString(s []byte) {
left, right := 0, len(s)-1
for left < right {
s[left], s[right] = s[right], s[left] // the middle char of an odd length needs no swap
left++
right--
}
}
// LC 344. Swap the ends and walk inward; left < right also covers odd lengths.
func reverseString(_ s: inout [Character]) {
var left = 0, right = s.count - 1
while left < right {
s.swapAt(left, right) // the middle char of an odd length needs no swap
left += 1
right -= 1
}
}
2. Valid Palindrome
Easy · LC 125
Given a string containing mixed punctuation, spaces, and letters, decide whether it reads the same forward and backward when only alphanumeric characters are considered, case-insensitively. Use two pointers from the ends, advancing each past non-alphanumeric characters before comparing lowercased characters and stepping inward. The pitfall is bounds: the inner skip loops must also check left < right, or the pointers can run past each other on strings made entirely of punctuation.
def is_palindrome(s: str) -> bool:
"""LC 125. Valid Palindrome.
Two pointers from the ends, each skipping past non-alphanumeric
characters before comparing lowercased characters and stepping
inward. The pitfall is bounds: the inner skip loops must also check
left < right, or all-punctuation input overruns. O(n) time, O(1)
space.
"""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum(): # the inner guard: ",," alone must not overrun
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
// LC 125. Compare lowercased alphanumerics from both ends inward.
bool isPalindrome(string s) {
int left = 0, right = static_cast<int>(s.size()) - 1;
while (left < right) {
// skip loops re-check left < right so all-punctuation input cannot run the pointers past each other
while (left < right && !isalnum(static_cast<unsigned char>(s[left]))) ++left;
while (left < right && !isalnum(static_cast<unsigned char>(s[right]))) --right;
if (tolower(static_cast<unsigned char>(s[left])) != tolower(static_cast<unsigned char>(s[right]))) return false;
++left;
--right;
}
return true;
}
/// LC 125. Pointers from both ends skip non-alphanumerics before comparing
/// lowercased chars. The inner skip loops must keep checking left < right,
/// or an all-punctuation string walks the pointers past each other.
pub fn is_palindrome(s: String) -> bool {
let bytes = s.as_bytes();
let (mut left, mut right) = (0, bytes.len().saturating_sub(1));
while left < right {
while left < right && !bytes[left].is_ascii_alphanumeric() {
left += 1;
}
while left < right && !bytes[right].is_ascii_alphanumeric() {
right -= 1;
}
if left >= right {
break; // pointers met inside punctuation; right - 1 would underflow
}
if bytes[left].to_ascii_lowercase() != bytes[right].to_ascii_lowercase() {
return false;
}
left += 1;
right -= 1;
}
true
}
/** LC 125. Ends inward, skipping non-alphanumerics, comparing lowercased. */
export function isPalindrome(s: string): boolean {
function isAlphanumeric(ch: string): boolean {
return /[a-z0-9]/i.test(ch);
}
let left = 0;
let right = s.length - 1;
while (left < right) {
// the skip loops re-check left < right, or all-punctuation input crosses the pointers
while (left < right && !isAlphanumeric(s[left])) left++;
while (left < right && !isAlphanumeric(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++;
right--;
}
return true;
}
// LC 125. Compare lowercased alphanumerics from both ends inward.
func isPalindrome(s string) bool {
isAlnum := func(c byte) bool {
return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z')
}
lower := func(c byte) byte {
if 'A' <= c && c <= 'Z' {
return c + 'a' - 'A'
}
return c
}
left, right := 0, len(s)-1
for left < right {
// skip loops re-check left < right so all-punctuation input cannot run the pointers past each other
for left < right && !isAlnum(s[left]) {
left++
}
for left < right && !isAlnum(s[right]) {
right--
}
if lower(s[left]) != lower(s[right]) {
return false
}
left++
right--
}
return true
}
// LC 125. Compare lowercased alphanumerics from both ends inward; the skip
// loops re-check left < right so all-punctuation input cannot overrun.
func isPalindrome(_ s: String) -> Bool {
let chars = Array(s)
var left = 0, right = chars.count - 1
while left < right {
while left < right && !(chars[left].isLetter || chars[left].isNumber) { left += 1 }
while left < right && !(chars[right].isLetter || chars[right].isNumber) { right -= 1 }
if chars[left].lowercased() != chars[right].lowercased() { return false }
left += 1
right -= 1
}
return true
}
3. Valid Palindrome II
Easy · LC 680
Given a string, determine whether it can become a palindrome by deleting at most one character. Compare from both ends as usual, and at the first mismatch branch into two checks: verify the remaining range is a palindrome after skipping the left character or after skipping the right one. Trying both skips is essential because either side might be the correct deletion, and with only one mismatch allowed the total work stays O(n).
def valid_palindrome(s: str) -> bool:
"""LC 680. Valid Palindrome II.
Compare from both ends; at the FIRST mismatch the one allowed
deletion must be either end character, so branch into two plain
palindrome checks on the shrunken range. Trying both skips is
essential: either side might be the right deletion. At most one
branch point keeps it O(n) time, O(1) space.
"""
def is_range_palindrome(lo: int, hi: int) -> bool:
while lo < hi:
if s[lo] != s[hi]:
return False
lo += 1
hi -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# either end could be the deletion: try skipping each once
return is_range_palindrome(left + 1, right) or is_range_palindrome(left, right - 1)
left += 1
right -= 1
return True
// LC 680. Palindrome with at most one deletion allowed.
bool validPalindrome(string s) {
auto isRangePalindrome = [&](int left, int right) {
while (left < right)
if (s[left++] != s[right--]) return false;
return true;
};
int left = 0, right = static_cast<int>(s.size()) - 1;
while (left < right) {
if (s[left] != s[right])
// either side could be the bad character, so try skipping each once
return isRangePalindrome(left + 1, right) || isRangePalindrome(left, right - 1);
++left;
--right;
}
return true;
}
/// LC 680. Compare from both ends; at the FIRST mismatch fork into two
/// checks: palindrome after dropping the left char, or after dropping the
/// right one. Either side could be the correct deletion, so try both.
pub fn valid_palindrome(s: String) -> bool {
fn is_pal(range: &[u8]) -> bool {
let (mut lo, mut hi) = (0, range.len() - 1);
while lo < hi {
if range[lo] != range[hi] {
return false;
}
lo += 1;
hi -= 1;
}
true
}
let bytes = s.as_bytes();
let (mut left, mut right) = (0, bytes.len().saturating_sub(1));
while left < right {
if bytes[left] != bytes[right] {
// one free deletion: skip the left char OR skip the right char
return is_pal(&bytes[left + 1..=right]) || is_pal(&bytes[left..right]);
}
left += 1;
right -= 1;
}
true
}
/** LC 680. At the first mismatch, try skipping the left char or the right char. */
export function validPalindrome(s: string): boolean {
function isPalindromeRange(from: number, to: number): boolean {
while (from < to) {
if (s[from] !== s[to]) return false;
from++;
to--;
}
return true;
}
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
// either side could be the one allowed deletion: both branches must be tried
return isPalindromeRange(left + 1, right) || isPalindromeRange(left, right - 1);
}
left++;
right--;
}
return true;
}
// LC 680. Palindrome with at most one deletion allowed.
func validPalindrome(s string) bool {
isRangePalindrome := func(left, right int) bool {
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
left, right := 0, len(s)-1
for left < right {
if s[left] != s[right] {
// either side could be the bad character, so try skipping each once
return isRangePalindrome(left+1, right) || isRangePalindrome(left, right-1)
}
left++
right--
}
return true
}
// LC 680. Palindrome with at most one deletion: at the first mismatch, either
// end could be the bad character, so try skipping each once.
func validPalindrome(_ s: String) -> Bool {
let chars = Array(s)
func isRangePalindrome(_ lo: Int, _ hi: Int) -> Bool {
var lo = lo, hi = hi
while lo < hi {
if chars[lo] != chars[hi] { return false }
lo += 1
hi -= 1
}
return true
}
var left = 0, right = chars.count - 1
while left < right {
if chars[left] != chars[right] {
return isRangePalindrome(left + 1, right) || isRangePalindrome(left, right - 1)
}
left += 1
right -= 1
}
return true
}
4. Merge Strings Alternately
Easy · LC 1768
Given two strings, build the result by taking characters from them alternately, starting with the first, then appending whatever remains of the longer string. Walk a shared index while it is inside both strings, pushing one character from each per step, then append the leftover tail. Handling unequal lengths is the only real content; slicing the tail after the shared loop avoids per-character bounds checks.
def merge_alternately(word1: str, word2: str) -> str:
"""LC 1768. Merge Strings Alternately.
Walk one shared index while it is inside BOTH strings, taking one
character from each per step, then append whatever remains of the
longer string. Slicing the tail after the shared loop avoids
per-character bounds checks. O(n + m) time and space.
"""
shared = 0
merged: list[str] = []
while shared < len(word1) and shared < len(word2):
merged.append(word1[shared])
merged.append(word2[shared])
shared += 1
# at most one of these tails is non-empty; slicing past the end is safely ""
return "".join(merged) + word1[shared:] + word2[shared:]
// LC 1768. Alternate while both words have characters, then append the longer tail.
string mergeAlternately(string word1, string word2) {
string merged;
merged.reserve(word1.size() + word2.size());
size_t shared = 0;
while (shared < word1.size() && shared < word2.size()) {
merged += word1[shared];
merged += word2[shared];
++shared;
}
merged += word1.substr(shared); // at most one of these tails is non-empty
merged += word2.substr(shared);
return merged;
}
/// LC 1768. Shared index while inside both words, one char from each per
/// step, then the longer word's tail goes on in a single slice append.
pub fn merge_alternately(word1: String, word2: String) -> String {
let shared = word1.len().min(word2.len());
let mut merged = String::with_capacity(word1.len() + word2.len());
let (bytes1, bytes2) = (word1.as_bytes(), word2.as_bytes());
for i in 0..shared {
merged.push(bytes1[i] as char);
merged.push(bytes2[i] as char);
}
// at most one of these tails is non-empty
merged.push_str(&word1[shared..]);
merged.push_str(&word2[shared..]);
merged
}
/** LC 1768. Alternate while both words have chars, then append the longer tail. */
export function mergeAlternately(word1: string, word2: string): string {
const shared = Math.min(word1.length, word2.length);
let merged = "";
for (let i = 0; i < shared; i++) merged += word1[i] + word2[i];
// at most one slice is non-empty: the leftover tail of the longer word
return merged + word1.slice(shared) + word2.slice(shared);
}
// LC 1768. Alternate while both words have characters, then append the longer tail.
func mergeAlternately(word1 string, word2 string) string {
merged := make([]byte, 0, len(word1)+len(word2))
shared := 0
for shared < len(word1) && shared < len(word2) {
merged = append(merged, word1[shared], word2[shared])
shared++
}
merged = append(merged, word1[shared:]...) // at most one of these tails is non-empty
merged = append(merged, word2[shared:]...)
return string(merged)
}
// LC 1768. Alternate while both words have characters, then append the longer
// tail; at most one of the tails is non-empty.
func mergeAlternately(_ word1: String, _ word2: String) -> String {
let first = Array(word1), second = Array(word2)
var merged: [Character] = []
merged.reserveCapacity(first.count + second.count)
var shared = 0
while shared < first.count && shared < second.count {
merged.append(first[shared])
merged.append(second[shared])
shared += 1
}
merged.append(contentsOf: first[shared...])
merged.append(contentsOf: second[shared...])
return String(merged)
}
5. Merge Sorted Array
Easy · LC 88
Given two sorted arrays where the first has enough trailing space to hold both, merge the second into the first in place. Compare from the back with three pointers, the last real element of each array and a write pointer at the very end, always placing the larger value. Filling backward is the trick, since the write position never catches up to unread data, and any leftovers of the second array still need copying.
def merge_sorted_array(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
"""LC 88. Merge Sorted Array.
Merge from the BACK with three pointers: the last real element of
each array and a write slot at the very end, always placing the
larger value. Filling backward is the trick -- the write slot never
catches up to unread nums1 data. Leftovers of nums2 still need
copying; leftovers of nums1 are already in place. O(m + n) time,
O(1) space, in place.
"""
read1, read2 = m - 1, n - 1
for write_slot in range(m + n - 1, -1, -1):
if read2 < 0:
break # nums2 exhausted: remaining nums1 values are already in place
if read1 >= 0 and nums1[read1] > nums2[read2]:
nums1[write_slot] = nums1[read1]
read1 -= 1
else:
nums1[write_slot] = nums2[read2]
read2 -= 1
// LC 88. Merge backward, largest first, so writes never overrun unread nums1 data.
void mergeSortedArray(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int last1 = m - 1, last2 = n - 1, writeSlot = m + n - 1;
while (last2 >= 0) { // leftover nums1 values are already in place, leftover nums2 values are not
if (last1 >= 0 && nums1[last1] > nums2[last2]) nums1[writeSlot--] = nums1[last1--];
else nums1[writeSlot--] = nums2[last2--];
}
}
/// LC 88. Merge from the BACK, always placing the larger value: the write
/// slot can never catch up to unread nums1 data, so no scratch buffer.
pub fn merge_sorted_array(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
let mut remaining1 = m as usize; // count of unread nums1 values, not an index
let mut remaining2 = n as usize;
let mut write_slot = remaining1 + remaining2;
while remaining2 > 0 {
write_slot -= 1;
if remaining1 > 0 && nums1[remaining1 - 1] > nums2[remaining2 - 1] {
remaining1 -= 1;
nums1[write_slot] = nums1[remaining1];
} else {
remaining2 -= 1;
nums1[write_slot] = nums2[remaining2];
}
}
// nums2 is drained; any nums1 leftovers already sit in their final slots
}
/** LC 88. Fill nums1 from the back so writes never overtake unread values. */
export function mergeSortedArray(nums1: number[], m: number, nums2: number[], n: number): void {
let read1 = m - 1;
let read2 = n - 1;
let writeSlot = m + n - 1;
// loop on read2 only: leftovers of nums1 are already in place
while (read2 >= 0) {
if (read1 >= 0 && nums1[read1] > nums2[read2]) {
nums1[writeSlot--] = nums1[read1--];
} else {
nums1[writeSlot--] = nums2[read2--];
}
}
}
// LC 88. Merge backward, largest first, so writes never overrun unread nums1 data.
func mergeSortedArray(nums1 []int, m int, nums2 []int, n int) {
last1, last2, writeSlot := m-1, n-1, m+n-1
for last2 >= 0 { // leftover nums1 values are already in place, leftover nums2 values are not
if last1 >= 0 && nums1[last1] > nums2[last2] {
nums1[writeSlot] = nums1[last1]
last1--
} else {
nums1[writeSlot] = nums2[last2]
last2--
}
writeSlot--
}
}
// LC 88. Merge backward, largest first, so writes never overrun unread nums1
// data; leftover nums1 values are already in place, leftover nums2 values are not.
func mergeSortedArray(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
var last1 = m - 1, last2 = n - 1, writeSlot = m + n - 1
while last2 >= 0 {
if last1 >= 0 && nums1[last1] > nums2[last2] {
nums1[writeSlot] = nums1[last1]
last1 -= 1
} else {
nums1[writeSlot] = nums2[last2]
last2 -= 1
}
writeSlot -= 1
}
}
6. Remove Duplicates From Sorted Array
Easy · LC 26
Given a sorted integer array, remove the duplicates in place so each value appears once, and return the new length k with the unique values at the front. Use a slow write pointer and a fast read pointer, copying an element forward only when it differs from the last written value. Sortedness guarantees duplicates are adjacent, which is why a single O(n) comparison against the previous keeper suffices.
def remove_duplicates(nums: list[int]) -> int:
"""LC 26. Remove Duplicates from Sorted Array.
Slow write pointer, fast read pointer: copy a value forward only
when it differs from the LAST WRITTEN value. Sortedness guarantees
duplicates are adjacent, so one comparison against the previous
keeper suffices. Returns the new length k. O(n) time, O(1) space,
in place.
"""
if not nums:
return 0
write_slot = 1 # nums[0] is always a keeper, so writing starts at 1
for read in range(1, len(nums)):
if nums[read] != nums[write_slot - 1]: # compare against the last keeper, not the last read
nums[write_slot] = nums[read]
write_slot += 1
return write_slot
// LC 26. Sortedness makes duplicates adjacent: keep a value only if it differs
// from the last keeper.
int removeDuplicates(vector<int>& nums) {
int writeSlot = 0;
for (int value : nums)
if (writeSlot == 0 || value != nums[writeSlot - 1]) nums[writeSlot++] = value;
return writeSlot;
}
/// LC 26. Slow write pointer, fast read pointer: copy a value forward only
/// when it differs from the last keeper -- sorted means duplicates are
/// adjacent, so one comparison suffices.
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
if nums.is_empty() {
return 0;
}
let mut write_slot = 1; // nums[0] is always its own first occurrence
for read in 1..nums.len() {
// compare against the last KEPT value, not the previous raw element
if nums[read] != nums[write_slot - 1] {
nums[write_slot] = nums[read];
write_slot += 1;
}
}
write_slot as i32
}
/** LC 26. Slow writeSlot, fast reader; keep values that differ from the last keeper. */
export function removeDuplicates(nums: number[]): number {
if (nums.length === 0) return 0;
let writeSlot = 1; // nums[0] is always a keeper
for (let read = 1; read < nums.length; read++) {
// sorted input: comparing against the last written value catches every duplicate
if (nums[read] !== nums[writeSlot - 1]) nums[writeSlot++] = nums[read];
}
return writeSlot;
}
// LC 26. Sortedness makes duplicates adjacent: keep a value only if it differs
// from the last keeper.
func removeDuplicates(nums []int) int {
writeSlot := 0
for _, value := range nums {
if writeSlot == 0 || value != nums[writeSlot-1] {
nums[writeSlot] = value
writeSlot++
}
}
return writeSlot
}
// LC 26. Sortedness makes duplicates adjacent: keep a value only if it differs
// from the last keeper, written at the slow pointer.
func removeDuplicates(_ nums: inout [Int]) -> Int {
var writeSlot = 0
for read in 0..<nums.count {
if writeSlot == 0 || nums[read] != nums[writeSlot - 1] {
nums[writeSlot] = nums[read]
writeSlot += 1
}
}
return writeSlot
}
7. Two Sum II Input Array Is Sorted
Medium · LC 167
Given a 1-indexed array sorted in ascending order and a target, return the 1-based indices of the two numbers that sum to it, using constant extra space. Start pointers at both ends: if the sum is too small move the left pointer right, if too large move the right pointer left, until the target is hit. Sortedness is what makes each move safe, since the discarded element could not appear in any valid pair.
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
"""LC 167. Two Sum II - Input Array Is Sorted.
Pointers at both ends: a sum that is too small forces left right-
ward, too large forces right leftward. Sortedness makes each move
safe -- the discarded element could not appear in ANY valid pair.
Returns 1-based indices per the problem contract. O(n) time, O(1)
space.
"""
left, right = 0, len(numbers) - 1
while left < right:
pair_sum = numbers[left] + numbers[right]
if pair_sum == target:
return [left + 1, right + 1] # problem wants 1-based indices
if pair_sum < target:
left += 1 # too small: nothing pairs with numbers[left], it is the floor
else:
right -= 1 # too large: numbers[right] overshoots with everything remaining
return []
// LC 167. Sorted ends inward: a too-small sum drops the left value, a too-large
// sum drops the right value; the dropped value fits no remaining pair.
vector<int> twoSumSorted(vector<int> numbers, int target) {
int left = 0, right = static_cast<int>(numbers.size()) - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return {left + 1, right + 1}; // problem wants 1-based indices
if (sum < target) ++left;
else --right;
}
return {};
}
/// LC 167. Pointers at both ends of the sorted array: a too-small sum moves
/// left up, a too-large sum moves right down. Each discarded end provably
/// belongs to no valid pair, which is what sortedness buys.
pub fn two_sum_sorted(numbers: Vec<i32>, target: i32) -> Vec<i32> {
let (mut left, mut right) = (0, numbers.len() - 1);
while left < right {
let sum = numbers[left] + numbers[right];
if sum == target {
return vec![left as i32 + 1, right as i32 + 1]; // answer is 1-indexed
}
if sum < target {
left += 1; // need a larger sum; only the low end can supply it
} else {
right -= 1; // need a smaller sum; drop the high end
}
}
Vec::new() // LC guarantees exactly one solution, so this is unreachable
}
/** LC 167. Ends inward: too small moves left up, too large moves right down. */
export function twoSumSorted(numbers: number[], target: number): number[] {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left + 1, right + 1]; // problem wants 1-based indices
// sortedness makes the discard safe: the dropped value fits no remaining pair
if (sum < target) left++;
else right--;
}
return [];
}
// LC 167. Sorted ends inward: a too-small sum drops the left value, a too-large
// sum drops the right value; the dropped value fits no remaining pair.
func twoSumSorted(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{left + 1, right + 1} // problem wants 1-based indices
}
if sum < target {
left++
} else {
right--
}
}
return nil
}
// LC 167. Sorted ends inward: a too-small sum drops the left value, a too-large
// sum drops the right value; the dropped value fits no remaining pair.
func twoSumSorted(_ numbers: [Int], _ target: Int) -> [Int] {
var left = 0, right = numbers.count - 1
while left < right {
let sum = numbers[left] + numbers[right]
if sum == target { return [left + 1, right + 1] } // problem wants 1-based indices
if sum < target { left += 1 } else { right -= 1 }
}
return []
}
8. 3Sum
Medium · LC 15
Given an integer array, return all unique triplets that sum to zero. Sort the array, then for each index i run the sorted two-sum two-pointer scan on the suffix looking for the complement of nums[i]. Duplicate handling is the hard part: skip repeated values for i, and after recording a triplet advance both inner pointers past their own repeats, which keeps results unique without a set in O(n^2).
def three_sum(nums: list[int]) -> list[list[int]]:
"""LC 15. 3Sum.
Sort, then for each anchor run the sorted two-sum scan on the
suffix looking for the complement. Duplicate handling is the hard
part: skip repeated anchor values, and after recording a triplet
advance BOTH inner pointers past their own repeats, keeping results
unique without a set. O(n^2) time after the O(n log n) sort, O(1)
extra space beyond the output.
"""
nums.sort()
triplets: list[list[int]] = []
for anchor in range(len(nums) - 2):
if nums[anchor] > 0:
break # sorted: a positive anchor can never sum to zero with larger values
if anchor > 0 and nums[anchor] == nums[anchor - 1]:
continue # same anchor value would rebuild the same triplets
left, right = anchor + 1, len(nums) - 1
while left < right:
total = nums[anchor] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([nums[anchor], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1 # hop repeats of the value just used, or the triplet reappears
while left < right and nums[right] == nums[right + 1]:
right -= 1
return triplets
// LC 15. Sort, fix the smallest element, then two-pointer the suffix for its complement.
vector<vector<int>> threeSum(vector<int> nums) {
sort(nums.begin(), nums.end());
int n = static_cast<int>(nums.size());
vector<vector<int>> triplets;
for (int first = 0; first < n - 2; ++first) {
if (nums[first] > 0) break; // smallest element positive: no zero sum remains
if (first > 0 && nums[first] == nums[first - 1]) continue; // skip duplicate anchors
int left = first + 1, right = n - 1;
while (left < right) {
int sum = nums[first] + nums[left] + nums[right];
if (sum < 0) ++left;
else if (sum > 0) --right;
else {
triplets.push_back({nums[first], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) ++left; // hop both pointers past their repeats
while (left < right && nums[right] == nums[right - 1]) --right;
++left;
--right;
}
}
}
return triplets;
}
/// LC 15. Sort, fix an anchor, run sorted two-sum on the suffix. The hard
/// part is duplicates: skip repeated anchor values, and after each hit hop
/// both inner pointers past their own repeats -- unique output, no HashSet.
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort_unstable();
let mut triplets = Vec::new();
for anchor in 0..nums.len() {
if nums[anchor] > 0 {
break; // sorted: a positive anchor can never sum back to zero
}
if anchor > 0 && nums[anchor] == nums[anchor - 1] {
continue; // this anchor value already produced its triplets
}
let (mut left, mut right) = (anchor + 1, nums.len() - 1);
while left < right {
let sum = nums[anchor] + nums[left] + nums[right];
if sum < 0 {
left += 1;
} else if sum > 0 {
right -= 1;
} else {
triplets.push(vec![nums[anchor], nums[left], nums[right]]);
left += 1;
right -= 1;
// hop past repeats so the same triplet is never re-recorded
while left < right && nums[left] == nums[left - 1] {
left += 1;
}
while left < right && nums[right] == nums[right + 1] {
right -= 1;
}
}
}
}
triplets
}
/** LC 15. Sort; fix an anchor, run sorted two-sum on the suffix, skip dupes. */
export function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const triplets: number[][] = [];
for (let anchor = 0; anchor < nums.length - 2; anchor++) {
if (nums[anchor] > 0) break; // sorted: an all-positive triplet cannot sum to zero
if (anchor > 0 && nums[anchor] === nums[anchor - 1]) continue; // repeated anchor repeats triplets
let left = anchor + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[anchor] + nums[left] + nums[right];
if (sum < 0) left++;
else if (sum > 0) right--;
else {
triplets.push([nums[anchor], nums[left], nums[right]]);
// step both pointers past their own repeats so each triplet is recorded once
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
}
}
}
return triplets;
}
// LC 15. Sort, fix the smallest element, then two-pointer the suffix for its complement.
func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
triplets := [][]int{}
for first := 0; first < n-2; first++ {
if nums[first] > 0 {
break // smallest element positive: no zero sum remains
}
if first > 0 && nums[first] == nums[first-1] {
continue // skip duplicate anchors
}
left, right := first+1, n-1
for left < right {
sum := nums[first] + nums[left] + nums[right]
if sum < 0 {
left++
} else if sum > 0 {
right--
} else {
triplets = append(triplets, []int{nums[first], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++ // hop both pointers past their repeats
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
}
}
}
return triplets
}
// LC 15. Sort, fix the smallest element, then two-pointer the suffix for its
// complement, hopping both inner pointers past their repeats.
func threeSum(_ nums: [Int]) -> [[Int]] {
let nums = nums.sorted()
let n = nums.count
var triplets: [[Int]] = []
for first in 0..<max(n - 2, 0) {
if nums[first] > 0 { break } // smallest element positive: no zero sum remains
if first > 0 && nums[first] == nums[first - 1] { continue } // skip duplicate anchors
var left = first + 1, right = n - 1
while left < right {
let sum = nums[first] + nums[left] + nums[right]
if sum < 0 {
left += 1
} else if sum > 0 {
right -= 1
} else {
triplets.append([nums[first], nums[left], nums[right]])
while left < right && nums[left] == nums[left + 1] { left += 1 } // hop both pointers past their repeats
while left < right && nums[right] == nums[right - 1] { right -= 1 }
left += 1
right -= 1
}
}
}
return triplets
}
9. 4Sum
Medium · LC 18
Given an integer array and a target, return all unique quadruplets summing to the target. Sort, then fix two indices with nested loops and close each pair with the standard two-pointer scan on the remaining range, skipping duplicate values at every one of the four levels. This is the general k-sum recursion pattern: peel off fixed elements until two remain, and beware overflow when summing four large values.
def four_sum(nums: list[int], target: int) -> list[list[int]]:
"""LC 18. 4Sum.
The general k-sum pattern: sort, peel off fixed elements with
nested loops until two remain, then close with the two-pointer
scan, skipping duplicate values at every one of the four levels.
(The classic overflow caveat is moot in Python -- ints are
arbitrary precision.) O(n^3) time, O(1) extra space beyond the
output.
"""
nums.sort()
n = len(nums)
quads: list[list[int]] = []
for first in range(n - 3):
if first > 0 and nums[first] == nums[first - 1]:
continue # duplicate first anchor would rebuild identical quads
for second in range(first + 1, n - 2):
if second > first + 1 and nums[second] == nums[second - 1]:
continue # > first + 1, not > 0: the first repeat AFTER the anchor is legal
left, right = second + 1, n - 1
while left < right:
total = nums[first] + nums[second] + nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
quads.append([nums[first], nums[second], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1 # inner duplicate skip mirrors 3Sum
while left < right and nums[right] == nums[right + 1]:
right -= 1
return quads
// LC 18. k-sum pattern: fix two anchors, close with the sorted two-pointer scan,
// and skip duplicates at all four levels.
vector<vector<int>> fourSum(vector<int> nums, int target) {
sort(nums.begin(), nums.end());
int n = static_cast<int>(nums.size());
vector<vector<int>> quads;
for (int first = 0; first < n - 3; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) continue;
for (int second = first + 1; second < n - 2; ++second) {
if (second > first + 1 && nums[second] == nums[second - 1]) continue;
long long need = static_cast<long long>(target) - nums[first] - nums[second]; // four ints can overflow int
int left = second + 1, right = n - 1;
while (left < right) {
long long sum = static_cast<long long>(nums[left]) + nums[right];
if (sum < need) ++left;
else if (sum > need) --right;
else {
quads.push_back({nums[first], nums[second], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
++left;
--right;
}
}
}
}
return quads;
}
/// LC 18. The k-sum pattern: peel off two fixed indices with nested loops,
/// close each pair with the two-pointer scan, and skip duplicates at all
/// four levels. Sums go through i64 -- four i32s near the limits overflow.
pub fn four_sum(mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
nums.sort_unstable();
let n = nums.len();
let mut quads = Vec::new();
if n < 4 {
return quads; // also guards the n - 3 underflow below
}
let target = target as i64;
for first in 0..n - 3 {
if first > 0 && nums[first] == nums[first - 1] {
continue; // duplicate first value
}
for second in first + 1..n - 2 {
if second > first + 1 && nums[second] == nums[second - 1] {
continue; // duplicate second value
}
let (mut left, mut right) = (second + 1, n - 1);
while left < right {
// i64: e.g. four copies of 10^9 wrap around in i32
let sum = nums[first] as i64
+ nums[second] as i64
+ nums[left] as i64
+ nums[right] as i64;
if sum < target {
left += 1;
} else if sum > target {
right -= 1;
} else {
quads.push(vec![nums[first], nums[second], nums[left], nums[right]]);
left += 1;
right -= 1;
while left < right && nums[left] == nums[left - 1] {
left += 1;
}
while left < right && nums[right] == nums[right + 1] {
right -= 1;
}
}
}
}
}
quads
}
/** LC 18. k-sum pattern: fix two indices, close with two pointers, dedupe all four levels. */
export function fourSum(nums: number[], target: number): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const quads: number[][] = [];
for (let first = 0; first < n - 3; first++) {
if (first > 0 && nums[first] === nums[first - 1]) continue; // dedupe the first fixed value
for (let second = first + 1; second < n - 2; second++) {
// second > first + 1 still allows nums[second] === nums[first]
if (second > first + 1 && nums[second] === nums[second - 1]) continue;
let left = second + 1;
let right = n - 1;
while (left < right) {
const sum = nums[first] + nums[second] + nums[left] + nums[right];
if (sum < target) left++;
else if (sum > target) right--;
else {
quads.push([nums[first], nums[second], nums[left], nums[right]]);
// dedupe the two pointer levels before stepping inward
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
}
}
}
}
return quads;
}
// LC 18. k-sum pattern: fix two anchors, close with the sorted two-pointer scan,
// and skip duplicates at all four levels.
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n := len(nums)
quads := [][]int{}
for first := 0; first < n-3; first++ {
if first > 0 && nums[first] == nums[first-1] {
continue
}
for second := first + 1; second < n-2; second++ {
if second > first+1 && nums[second] == nums[second-1] {
continue
}
need := target - nums[first] - nums[second] // Go's 64-bit int keeps the sums that overflow int32 exact
left, right := second+1, n-1
for left < right {
sum := nums[left] + nums[right]
if sum < need {
left++
} else if sum > need {
right--
} else {
quads = append(quads, []int{nums[first], nums[second], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
}
}
}
}
return quads
}
// LC 18. k-sum pattern: fix two anchors, close with the sorted two-pointer scan,
// and skip duplicates at all four levels. Swift's 64-bit Int absorbs the overflow trap.
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let nums = nums.sorted()
let n = nums.count
var quads: [[Int]] = []
for first in 0..<max(n - 3, 0) {
if first > 0 && nums[first] == nums[first - 1] { continue }
for second in (first + 1)..<(n - 2) {
if second > first + 1 && nums[second] == nums[second - 1] { continue }
let need = target - nums[first] - nums[second]
var left = second + 1, right = n - 1
while left < right {
let sum = nums[left] + nums[right]
if sum < need {
left += 1
} else if sum > need {
right -= 1
} else {
quads.append([nums[first], nums[second], nums[left], nums[right]])
while left < right && nums[left] == nums[left + 1] { left += 1 }
while left < right && nums[right] == nums[right - 1] { right -= 1 }
left += 1
right -= 1
}
}
}
}
return quads
}
10. Rotate Array
Medium · LC 189
Given an array and an integer k, rotate the array to the right by k steps in place. Take k modulo n, reverse the entire array, then reverse the first k elements and finally the remaining n minus k elements. The triple-reversal identity is the whole trick, and forgetting the k mod n reduction breaks the case where k exceeds the array length.
def rotate_array(nums: list[int], k: int) -> None:
"""LC 189. Rotate Array.
Triple reversal: reverse the whole array, then un-reverse the first
k elements and the remaining n - k separately. Reversing the whole
array brings the rotated-in tail to the front (each block backward),
and the two block reversals fix their internal order. Forgetting
k mod n breaks k > n. O(n) time, O(1) space, in place.
"""
n = len(nums)
if n == 0:
return
k %= n # a full lap is a no-op; only the remainder matters
def reverse(lo: int, hi: int) -> None:
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
reverse(0, n - 1) # whole array: the last k now lead, but both blocks are backward
reverse(0, k - 1) # fix the new front block
reverse(k, n - 1) # fix the new back block
// LC 189. Triple reversal: reverse everything, then each block, and the two
// blocks have swapped places in original order.
void rotateArray(vector<int>& nums, int k) {
int n = static_cast<int>(nums.size());
if (n == 0) return;
k %= n; // rotating by n is a no-op, and k may exceed n
auto reverseRange = [&](int left, int right) {
while (left < right) swap(nums[left++], nums[right--]);
};
reverseRange(0, n - 1);
reverseRange(0, k - 1); // the first k entries are the old tail; restore their order
reverseRange(k, n - 1);
}
/// LC 189. Triple reversal: reverse the whole array, then re-reverse the
/// first k and the last n - k separately. Reduce k mod n first, or any
/// k larger than the array breaks it.
pub fn rotate_array(nums: &mut Vec<i32>, k: i32) {
let n = nums.len();
if n == 0 {
return; // k % 0 would divide by zero
}
let k = k as usize % n; // rotating by n is a no-op; only k mod n matters
nums.reverse(); // tail elements now lead, but both halves are backwards
nums[..k].reverse(); // restore order inside the moved tail
nums[k..].reverse(); // restore order inside the rest
}
/** LC 189. Reverse everything, then reverse the first k and the last n - k, in place. */
export function rotateArray(nums: number[], k: number): void {
function reverseRange(from: number, to: number): void {
while (from < to) {
[nums[from], nums[to]] = [nums[to], nums[from]];
from++;
to--;
}
}
const n = nums.length;
if (n === 0) return;
const shift = k % n; // k may exceed n, and rotating by n is a no-op
reverseRange(0, n - 1);
reverseRange(0, shift - 1);
reverseRange(shift, n - 1);
}
// LC 189. Triple reversal: reverse everything, then each block, and the two
// blocks have swapped places in original order.
func rotateArray(nums []int, k int) {
n := len(nums)
if n == 0 {
return
}
k %= n // rotating by n is a no-op, and k may exceed n
reverseRange := func(left, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
reverseRange(0, n-1)
reverseRange(0, k-1) // the first k entries are the old tail; restore their order
reverseRange(k, n-1)
}
// LC 189. Triple reversal: reverse everything, then each block, and the two
// blocks have swapped places in original order. k mod n handles k > n.
func rotateArray(_ nums: inout [Int], _ k: Int) {
let n = nums.count
if n == 0 { return }
let k = k % n // rotating by n is a no-op, and k may exceed n
func reverseRange(_ lo: Int, _ hi: Int) {
var lo = lo, hi = hi
while lo < hi {
nums.swapAt(lo, hi)
lo += 1
hi -= 1
}
}
reverseRange(0, n - 1)
reverseRange(0, k - 1) // the first k entries are the old tail; restore their order
reverseRange(k, n - 1)
}
11. Container With Most Water
Medium · LC 11
Given an array of line heights, pick the two lines that hold the most water against the x-axis and return that maximum area. Start pointers at both ends, record width times the smaller height, and move the pointer at the shorter line inward each step. Width only shrinks as pointers advance, so any pairing kept with the shorter wall cannot beat the current area, which is what makes one O(n) pass sufficient.
def max_area(height: list[int]) -> int:
"""LC 11. Container With Most Water.
Walls at both ends; area is width times the SHORTER wall. Width
only shrinks as the pointers advance, so keeping the shorter wall
can never beat the current area -- moving it inward is the only
hope of a taller pairing. One O(n) pass, O(1) space.
"""
left_wall, right_wall = 0, len(height) - 1
best = 0
while left_wall < right_wall:
width = right_wall - left_wall
best = max(best, width * min(height[left_wall], height[right_wall]))
if height[left_wall] <= height[right_wall]:
left_wall += 1 # move the shorter wall: it is the binding constraint
else:
right_wall -= 1
return best
// LC 11. Best water between two walls, one O(n) pass from both ends.
int maxArea(vector<int> height) {
int leftWall = 0, rightWall = static_cast<int>(height.size()) - 1, best = 0;
while (leftWall < rightWall) {
int water = (rightWall - leftWall) * min(height[leftWall], height[rightWall]);
best = max(best, water);
if (height[leftWall] < height[rightWall]) ++leftWall; // move the shorter wall: it is the binding constraint
else --rightWall;
}
return best;
}
/// LC 11. Walls at both ends: record width times the shorter wall, then move
/// the shorter wall inward. Width only shrinks, so keeping the shorter wall
/// can never beat the current area -- one O(n) pass suffices.
pub fn max_area(height: Vec<i32>) -> i32 {
let (mut left_wall, mut right_wall) = (0, height.len() - 1);
let mut best = 0;
while left_wall < right_wall {
let width = (right_wall - left_wall) as i32;
let depth = height[left_wall].min(height[right_wall]);
best = best.max(width * depth);
// move the shorter wall: it is the binding constraint
if height[left_wall] < height[right_wall] {
left_wall += 1;
} else {
right_wall -= 1;
}
}
best
}
/** LC 11. Ends inward, tracking width times the shorter wall, moving that wall. */
export function maxArea(height: number[]): number {
let leftWall = 0;
let rightWall = height.length - 1;
let best = 0;
while (leftWall < rightWall) {
const width = rightWall - leftWall;
const depth = Math.min(height[leftWall], height[rightWall]);
best = Math.max(best, width * depth);
// move the shorter wall: it is the binding constraint, and width only shrinks
if (height[leftWall] < height[rightWall]) leftWall++;
else rightWall--;
}
return best;
}
// LC 11. Best water between two walls, one O(n) pass from both ends.
func maxArea(height []int) int {
leftWall, rightWall, best := 0, len(height)-1, 0
for leftWall < rightWall {
water := (rightWall - leftWall) * height[leftWall]
if height[rightWall] < height[leftWall] {
water = (rightWall - leftWall) * height[rightWall]
}
if water > best {
best = water
}
if height[leftWall] < height[rightWall] {
leftWall++ // move the shorter wall: it is the binding constraint
} else {
rightWall--
}
}
return best
}
// LC 11. Best water between two walls, one O(n) pass from both ends; always
// move the shorter wall, it is the binding constraint.
func maxArea(_ height: [Int]) -> Int {
var leftWall = 0, rightWall = height.count - 1, best = 0
while leftWall < rightWall {
let water = (rightWall - leftWall) * min(height[leftWall], height[rightWall])
best = max(best, water)
if height[leftWall] < height[rightWall] { leftWall += 1 } else { rightWall -= 1 }
}
return best
}
12. Boats to Save People
Medium · LC 881
Given people's weights and a boat weight limit, with at most two people per boat, return the minimum number of boats. Sort the weights, then point at the lightest and heaviest: if they fit together send both, otherwise send the heaviest alone, counting one boat either way. The greedy pairing is safe because the heaviest person must board something and the lightest is the best possible companion, giving O(n log n) overall.
def num_rescue_boats(people: list[int], limit: int) -> int:
"""LC 881. Boats to Save People.
Sort, then point at the lightest and heaviest: if they fit
together send both, otherwise the heaviest goes alone -- one boat
either way. Greedy pairing is safe because the heaviest person must
board something and the lightest is the best possible companion.
O(n log n) time for the sort, O(1) extra space.
"""
people.sort()
lighter, heavier = 0, len(people) - 1
boats = 0
while lighter <= heavier: # <= not <: the last person alone still needs a boat
if people[lighter] + people[heavier] <= limit:
lighter += 1 # the lightest fits alongside, so pair them up
heavier -= 1 # the heaviest boards this boat no matter what
boats += 1
return boats
// LC 881. Sort, then greedily pair the lightest with the heaviest.
int numRescueBoats(vector<int> people, int limit) {
sort(people.begin(), people.end());
int lighter = 0, heavier = static_cast<int>(people.size()) - 1, boats = 0;
while (lighter <= heavier) {
if (people[lighter] + people[heavier] <= limit) ++lighter; // the lightest is the best possible companion
--heavier; // the heaviest must board something, so seat them now
++boats;
}
return boats;
}
/// LC 881. Sort, then pair lightest with heaviest. The heaviest person must
/// board SOMETHING, and the lightest is the best possible companion, so the
/// greedy pairing is safe. One boat per loop turn.
pub fn num_rescue_boats(mut people: Vec<i32>, limit: i32) -> i32 {
people.sort_unstable();
let (mut lighter, mut heavier) = (0, people.len() - 1);
let mut boats = 0;
while lighter < heavier {
// the heaviest sails either way; bring the lightest along if they fit
if people[lighter] + people[heavier] <= limit {
lighter += 1;
}
heavier -= 1;
boats += 1;
}
if lighter == heavier {
boats += 1; // exactly one person remains and needs their own boat
}
boats
}
/** LC 881. Sort; pair the lightest with the heaviest, else the heaviest rides alone. */
export function numRescueBoats(people: number[], limit: number): number {
people.sort((a, b) => a - b);
let lighter = 0;
let heavier = people.length - 1;
let boats = 0;
while (lighter <= heavier) {
// the lightest is the heaviest person's best possible companion
if (people[lighter] + people[heavier] <= limit) lighter++;
heavier--; // the heaviest boards this boat either way
boats++;
}
return boats;
}
// LC 881. Sort, then greedily pair the lightest with the heaviest.
func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
lighter, heavier, boats := 0, len(people)-1, 0
for lighter <= heavier {
if people[lighter]+people[heavier] <= limit {
lighter++ // the lightest is the best possible companion
}
heavier-- // the heaviest must board something, so seat them now
boats++
}
return boats
}
// LC 881. Sort, then greedily pair the lightest with the heaviest; the heaviest
// boards a boat either way, the lightest is the best possible companion.
func numRescueBoats(_ people: [Int], _ limit: Int) -> Int {
let people = people.sorted()
var lighter = 0, heavier = people.count - 1, boats = 0
while lighter <= heavier { // <= not <: the last person alone still needs a boat
if people[lighter] + people[heavier] <= limit { lighter += 1 }
heavier -= 1
boats += 1
}
return boats
}
13. Trapping Rain Water
Hard · LC 42
Given an elevation map of bar heights, compute how much rainwater is trapped between the bars. Keep two pointers with running maxima leftMax and rightMax, always advancing the side whose maximum is smaller and adding that side's max minus its current height. The invariant is that water over the smaller-max side is already determined, because a wall at least that tall exists on the other side, giving O(n) time and O(1) space.
def trap(height: list[int]) -> int:
"""LC 42. Trapping Rain Water.
Two pointers with running maxima: always advance the side whose max
is SMALLER and add that side's max minus its current height. The
invariant: water over the smaller-max side is already determined,
because a wall at least that tall is known to exist on the other
side. O(n) time, O(1) space -- no prefix arrays.
"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if left_max <= right_max: # left's ceiling is settled: something >= left_max waits on the right
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left] # never negative: left_max already includes height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return water
// LC 42. Two pointers with running maxima: O(n) time, O(1) space.
int trap(vector<int> height) {
if (height.empty()) return 0;
int left = 0, right = static_cast<int>(height.size()) - 1;
int leftMax = height[left], rightMax = height[right], water = 0;
while (left < right) {
if (leftMax < rightMax) {
++left;
leftMax = max(leftMax, height[left]);
water += leftMax - height[left]; // a wall >= leftMax exists to the right, so this fill is final
} else {
--right;
rightMax = max(rightMax, height[right]);
water += rightMax - height[right]; // symmetric: rightMax is the binding level here
}
}
return water;
}
/// LC 42. Two pointers with running maxima: always advance the side whose
/// max is SMALLER, adding that side's max minus its bar. Water over the
/// smaller-max side is already decided -- a wall at least that tall exists
/// on the other side. O(n) time, O(1) space.
pub fn trap(height: Vec<i32>) -> i32 {
if height.is_empty() {
return 0;
}
let (mut left, mut right) = (0, height.len() - 1);
let (mut left_max, mut right_max) = (height[left], height[right]);
let mut water = 0;
while left < right {
if left_max < right_max {
left += 1;
left_max = left_max.max(height[left]);
// never negative: left_max was just refreshed with height[left]
water += left_max - height[left];
} else {
right -= 1;
right_max = right_max.max(height[right]);
water += right_max - height[right];
}
}
water
}
/** LC 42. Advance the side with the smaller running max; its water level is settled. */
export function trap(height: number[]): number {
if (height.length === 0) return 0;
let left = 0;
let right = height.length - 1;
let leftMax = height[left];
let rightMax = height[right];
let water = 0;
while (left < right) {
if (leftMax < rightMax) {
left++; // advance before measuring so the meeting column is never skipped
leftMax = Math.max(leftMax, height[left]);
// a wall of at least leftMax exists to the right, so this column's water is final
water += leftMax - height[left];
} else {
right--;
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
}
}
return water;
}
// LC 42. Two pointers with running maxima: O(n) time, O(1) space.
func trap(height []int) int {
if len(height) == 0 {
return 0
}
left, right := 0, len(height)-1
leftMax, rightMax, water := height[left], height[right], 0
for left < right {
if leftMax < rightMax {
left++
if height[left] > leftMax {
leftMax = height[left]
}
water += leftMax - height[left] // a wall >= leftMax exists to the right, so this fill is final
} else {
right--
if height[right] > rightMax {
rightMax = height[right]
}
water += rightMax - height[right] // symmetric: rightMax is the binding level here
}
}
return water
}
// LC 42. Two pointers with running maxima: advance the side whose max is smaller;
// a wall at least that tall is known to exist on the other side. O(n), O(1).
func trap(_ height: [Int]) -> Int {
if height.isEmpty { return 0 }
var left = 0, right = height.count - 1
var leftMax = height[left], rightMax = height[right], water = 0
while left < right {
if leftMax < rightMax {
left += 1
leftMax = max(leftMax, height[left])
water += leftMax - height[left] // never negative: leftMax already includes height[left]
} else {
right -= 1
rightMax = max(rightMax, height[right])
water += rightMax - height[right]
}
}
return water
}