1. Concatenation of Array
Easy · LC 1929
Given an integer array nums of length n, return an array ans of length 2n where ans[i] and ans[i+n] both equal nums[i]. Allocate the output and walk nums once, writing each value into both of its target slots. The whole problem is the index identity ans[i] = ans[i+n] = nums[i], which turns concatenation into a single O(n) pass with no edge cases.
def get_concatenation(nums: list[int]) -> list[int]:
"""LC 1929. Concatenation of Array.
ans has length 2n with ans[i] == ans[i + n] == nums[i]; list addition
builds exactly that. O(n) time and space.
"""
return nums + nums
// LC 1929. Answer is just nums followed by nums; reserve then re-append.
vector<int> getConcatenation(vector<int> nums) {
int n = static_cast<int>(nums.size());
nums.reserve(2 * n);
for (int i = 0; i < n; ++i) nums.push_back(nums[i]);
return nums;
}
/// LC 1929. ans[i] = ans[i + n] = nums[i]; one extend of a clone does it.
pub fn get_concatenation(nums: Vec<i32>) -> Vec<i32> {
let mut ans = nums.clone();
ans.extend_from_slice(&nums);
ans
}
/** LC 1929. ans[i] = ans[i + n] = nums[i]; one pass writing both halves. */
export function getConcatenation(nums: number[]): number[] {
const n = nums.length;
const ans = new Array<number>(2 * n);
for (let i = 0; i < n; i++) {
ans[i] = nums[i];
ans[i + n] = nums[i];
}
return ans;
}
// LC 1929. ans has length 2n with ans[i] == ans[i+n] == nums[i]; append two copies.
func getConcatenation(nums []int) []int {
ans := make([]int, 0, 2*len(nums))
ans = append(ans, nums...)
ans = append(ans, nums...)
return ans
}
// LC 1929. ans[i] == ans[i + n] == nums[i]; array concatenation builds exactly that.
func getConcatenation(_ nums: [Int]) -> [Int] {
return nums + nums
}
2. Contains Duplicate
Easy · LC 217
Given an integer array, return true if any value appears at least twice and false if every element is distinct. Walk the array once, inserting each number into a hash set and returning true the moment an insert finds the value already present. The set membership check is O(1) on average, so the whole scan is O(n) time and O(n) space, beating the O(n log n) sorting alternative.
def contains_duplicate(nums: list[int]) -> bool:
"""LC 217. Contains Duplicate.
A set remembers every value seen so far; the first repeat answers
immediately. O(n) time, O(n) space.
"""
seen: set[int] = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
// LC 217. unordered_set insert reports whether the value was already there.
bool containsDuplicate(vector<int> nums) {
unordered_set<int> seen;
for (int x : nums)
if (!seen.insert(x).second) return true;
return false;
}
/// LC 217. HashSet::insert returns false on a repeat -- that IS the answer.
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
let mut seen = HashSet::with_capacity(nums.len());
nums.into_iter().any(|n| !seen.insert(n))
}
/** LC 217. A Set built from the array shrinks iff there was a duplicate. */
export function containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>();
for (const num of nums) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
}
// LC 217. A set remembers every value seen so far; the first repeat answers immediately.
func containsDuplicate(nums []int) bool {
seen := make(map[int]struct{}, len(nums))
for _, x := range nums {
if _, ok := seen[x]; ok {
return true
}
seen[x] = struct{}{}
}
return false
}
// LC 217. Set.insert reports whether the value was already there.
func containsDuplicate(_ nums: [Int]) -> Bool {
var seen = Set<Int>()
for x in nums {
if !seen.insert(x).inserted { return true }
}
return false
}
3. Valid Anagram
Easy · LC 242
Given two strings, return true if one is an anagram of the other, meaning the same letters with the same counts. Build a 26-slot count array, incrementing for each character of the first string and decrementing for each of the second, then check every slot is zero. Compare lengths first for an early exit; the count array keeps it O(n) time and O(1) space.
def is_anagram(s: str, t: str) -> bool:
"""LC 242. Valid Anagram.
One 26-slot count array: +1 for chars of s, -1 for chars of t. The
strings are anagrams iff every slot returns to zero. O(n) time,
O(1) space (alphabet is fixed).
"""
if len(s) != len(t):
return False
counts = [0] * 26
for cs, ct in zip(s, t):
counts[ord(cs) - ord("a")] += 1
counts[ord(ct) - ord("a")] -= 1
return all(count == 0 for count in counts)
// LC 242. 26-count array: increment over s, decrement over t, never go negative.
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int count[26] = {};
for (char ch : s) ++count[ch - 'a'];
for (char ch : t)
if (--count[ch - 'a'] < 0) return false;
return true;
}
/// LC 242. One 26-slot count array: +1 for s, -1 for t, all zero = anagram.
pub fn is_anagram(s: String, t: String) -> bool {
if s.len() != t.len() {
return false;
}
let mut counts = [0i32; 26];
for b in s.bytes() {
counts[(b - b'a') as usize] += 1;
}
for b in t.bytes() {
counts[(b - b'a') as usize] -= 1;
}
counts.iter().all(|&c| c == 0)
}
/** LC 242. 26-count array: +1 for s, -1 for t; anagram iff all zero. */
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const count = new Array<number>(26).fill(0);
const base = "a".charCodeAt(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - base]++;
count[t.charCodeAt(i) - base]--;
}
return count.every((c) => c === 0);
}
// LC 242. 26-count array: increment over s, decrement over t, never go negative.
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
var count [26]int
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
}
for i := 0; i < len(t); i++ {
count[t[i]-'a']--
if count[t[i]-'a'] < 0 {
return false
}
}
return true
}
// LC 242. 26-count array: increment over s, decrement over t, never go negative.
func isAnagram(_ s: String, _ t: String) -> Bool {
if s.count != t.count { return false }
var count = [Int](repeating: 0, count: 26)
for byte in s.utf8 { count[Int(byte) - 97] += 1 }
for byte in t.utf8 {
count[Int(byte) - 97] -= 1
if count[Int(byte) - 97] < 0 { return false }
}
return true
}
4. Two Sum
Easy · LC 1
Given an array of integers and a target, return the indices of the two numbers that sum to the target. Walk the array once with a hash map from value to index, and for each number check whether its complement, target minus the number, was already stored. The trick is to check before inserting the current value, which handles duplicate values cleanly and keeps it one pass in O(n).
def two_sum(nums: list[int], target: int) -> list[int]:
"""LC 1. Two Sum.
One pass with a value -> index map: before storing nums[i], check
whether its complement target - nums[i] was already seen. Checking
BEFORE inserting is what makes duplicates like [3, 3] safe.
O(n) time, O(n) space.
"""
seen: dict[int, int] = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
// LC 1. One pass: look up the complement among values already seen.
vector<int> twoSum(vector<int> nums, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
auto it = seen.find(target - nums[i]);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {};
}
/// LC 1. One pass: look up the complement before inserting the current num,
/// so a pair like [3, 3] never matches an element with itself.
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut seen = HashMap::with_capacity(nums.len());
for (i, &num) in nums.iter().enumerate() {
if let Some(&j) = seen.get(&(target - num)) {
return vec![j as i32, i as i32];
}
seen.insert(num, i);
}
Vec::new()
}
/** LC 1. One pass: look up target - num before inserting num, so i != j. */
export function twoSum(nums: number[], target: number): number[] {
const indexOf = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
const j = indexOf.get(need);
if (j !== undefined) return [j, i];
indexOf.set(nums[i], i);
}
return [];
}
// LC 1. One pass with a value-to-index map; check the complement before inserting.
func twoSum(nums []int, target int) []int {
seen := make(map[int]int, len(nums)) // value -> index
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return []int{j, i}
}
seen[x] = i
}
return nil
}
// LC 1. One pass with a value-to-index map; check the complement before inserting.
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var seen: [Int: Int] = [:] // value -> index
for (i, x) in nums.enumerated() {
if let j = seen[target - x] { return [j, i] }
seen[x] = i
}
return []
}
5. Longest Common Prefix
Easy · LC 14
Given an array of strings, return the longest prefix shared by all of them, or an empty string if there is none. Scan vertically, comparing each character position of the first string against the same position in every other string. Stop at the first mismatch or when any string runs out, returning what was matched so far; work is bounded by the total character count.
def longest_common_prefix(strs: list[str]) -> str:
"""LC 14. Longest Common Prefix.
Start with the whole first string and shave one trailing char
whenever some string does not start with the current candidate.
The prefix only ever shrinks, so total work is O(total chars).
O(1) extra space beyond the answer slice.
"""
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
// LC 14. Vertical scan: compare column i of every word against word 0.
string longestCommonPrefix(vector<string> strs) {
for (size_t i = 0; i < strs[0].size(); ++i)
for (size_t j = 1; j < strs.size(); ++j)
if (i >= strs[j].size() || strs[j][i] != strs[0][i]) return strs[0].substr(0, i);
return strs[0];
}
/// LC 14. Shrink the candidate prefix to the longest byte-wise match with
/// each string; the prefix can only get shorter.
pub fn longest_common_prefix(strs: Vec<String>) -> String {
let first = &strs[0];
let mut end = first.len();
for s in &strs[1..] {
let common = first.bytes().zip(s.bytes()).take_while(|(a, b)| a == b).count();
end = end.min(common);
}
first[..end].to_string()
}
/** LC 14. Shrink the candidate prefix against each string in turn. */
export function longestCommonPrefix(strs: string[]): string {
let prefix = strs[0] ?? "";
for (let i = 1; i < strs.length && prefix.length > 0; i++) {
const word = strs[i];
let len = 0;
const max = Math.min(prefix.length, word.length);
while (len < max && prefix[len] === word[len]) len++;
prefix = prefix.slice(0, len);
}
return prefix;
}
// LC 14. Vertical scan: compare column i of every word against word 0.
func longestCommonPrefix(strs []string) string {
for i := 0; i < len(strs[0]); i++ {
for j := 1; j < len(strs); j++ {
if i >= len(strs[j]) || strs[j][i] != strs[0][i] {
return strs[0][:i]
}
}
}
return strs[0]
}
// LC 14. Vertical scan: compare column i of every word against word 0.
func longestCommonPrefix(_ strs: [String]) -> String {
let words = strs.map { Array($0) }
let first = words[0]
for i in 0..<first.count {
for j in 1..<words.count {
if i >= words[j].count || words[j][i] != first[i] {
return String(first[0..<i])
}
}
}
return strs[0]
}
6. Group Anagrams
Medium · LC 49
Given an array of strings, group the words that are anagrams of each other and return the groups. Map each word to a canonical key, either its sorted characters or a 26-letter count signature, and append the word to that key's bucket in a hash map. The count signature avoids sorting each word, making the grouping O(n k) for n words of length k rather than O(n k log k).
def group_anagrams(strs: list[str]) -> list[list[str]]:
"""LC 49. Group Anagrams.
Anagrams share letter counts, so a tuple of 26 counts is a canonical
hashable key -- no sorting needed. O(n * m) time for n strings of
length m (vs O(n * m log m) with sorted keys), O(n * m) space.
"""
groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)
for s in strs:
counts = [0] * 26
for ch in s:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(s)
return list(groups.values())
// LC 49. Key = the 26 letter counts serialized; anagrams share the key.
vector<vector<string>> groupAnagrams(vector<string> strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
array<int, 26> count{};
for (char ch : s) ++count[ch - 'a'];
string key;
for (int c : count) key += to_string(c) + ',';
groups[key].push_back(s);
}
vector<vector<string>> ans;
for (auto& [key, group] : groups) ans.push_back(move(group));
return ans;
}
/// LC 49. Key each word by its 26-letter count array (no sorting needed);
/// anagrams collide on the same key.
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut groups: HashMap<[u8; 26], Vec<String>> = HashMap::new();
for s in strs {
let mut key = [0u8; 26];
for b in s.bytes() {
key[(b - b'a') as usize] += 1;
}
groups.entry(key).or_default().push(s);
}
groups.into_values().collect()
}
/** LC 49. Key = 26-count joined with '#': O(n * k), no sorting per word. */
export function groupAnagrams(strs: string[]): string[][] {
const groups = new Map<string, string[]>();
const base = "a".charCodeAt(0);
for (const str of strs) {
const count = new Array<number>(26).fill(0);
for (let i = 0; i < str.length; i++) count[str.charCodeAt(i) - base]++;
const key = count.join("#");
const bucket = groups.get(key);
if (bucket) bucket.push(str);
else groups.set(key, [str]);
}
return [...groups.values()];
}
// LC 49. Key = the 26 letter counts (a comparable array); anagrams share the
// key, no sorting needed.
func groupAnagrams(strs []string) [][]string {
groups := make(map[[26]int][]string)
for _, s := range strs {
var count [26]int
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
}
groups[count] = append(groups[count], s)
}
ans := make([][]string, 0, len(groups))
for _, group := range groups {
ans = append(ans, group)
}
return ans
}
// LC 49. Key = the 26 letter counts serialized; anagrams share the key.
func groupAnagrams(_ strs: [String]) -> [[String]] {
var groups: [String: [String]] = [:]
for s in strs {
var count = [Int](repeating: 0, count: 26)
for byte in s.utf8 { count[Int(byte) - 97] += 1 }
let key = count.map(String.init).joined(separator: ",")
groups[key, default: []].append(s)
}
return Array(groups.values)
}
7. Remove Element
Easy · LC 27
Given an array and a target value, remove every occurrence in place and return k, the count of remaining elements, which must sit in the first k slots. Walk with a fast read pointer and a slow write pointer, copying each non-target element into the write slot and advancing it. The invariant is that everything before the write pointer is already kept, giving one stable O(n) pass.
def remove_element(nums: list[int], val: int) -> int:
"""LC 27. Remove Element.
Write pointer k: copy every keeper forward, skip every val. The
first k slots end up holding exactly the kept elements, order
preserved. O(n) time, O(1) space, in place.
"""
k = 0
for num in nums:
if num != val:
nums[k] = num
k += 1
return k
// LC 27. Write pointer: copy every keeper forward, return how many kept.
int removeElement(vector<int>& nums, int val) {
int k = 0;
for (int x : nums)
if (x != val) nums[k++] = x;
return k;
}
/// LC 27. Write pointer k: copy every keeper forward, skip the val.
pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
let mut k = 0;
for i in 0..nums.len() {
if nums[i] != val {
nums[k] = nums[i];
k += 1;
}
}
k as i32
}
/** LC 27. Compact in place: keepers overwrite the front, k counts them. */
export function removeElement(nums: number[], val: number): number {
let k = 0;
for (const num of nums) {
if (num !== val) nums[k++] = num;
}
return k;
}
// LC 27. Write pointer: copy every keeper forward, return how many kept.
func removeElement(nums []int, val int) int {
k := 0
for _, x := range nums {
if x != val {
nums[k] = x
k++
}
}
return k
}
// LC 27. Write pointer: copy every keeper forward, return how many kept.
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
var k = 0
for x in nums where x != val {
nums[k] = x
k += 1
}
return k
}
8. Majority Element
Easy · LC 169
Given an array where one value appears more than n/2 times, return that majority value. Run Boyer-Moore voting: keep a candidate and a counter, increment when the current element matches the candidate, decrement otherwise, and adopt a new candidate whenever the counter hits zero. It works because every decrement cancels one majority vote against one other vote, and the majority has votes to spare, giving O(n) time and O(1) space.
def majority_element(nums: list[int]) -> int:
"""LC 169. Majority Element.
Boyer-Moore voting: a matching element increments the candidate's
count, a mismatch decrements it, and count 0 crowns a new candidate.
An element occupying more than half the array survives every
cancellation. O(n) time, O(1) space.
"""
candidate = nums[0]
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
// LC 169. Boyer-Moore: majority survives pairwise cancellation.
int majorityElement(vector<int> nums) {
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) candidate = x;
count += (x == candidate) ? 1 : -1;
}
return candidate;
}
/// LC 169. Boyer-Moore voting: the majority survives pairwise cancellation.
pub fn majority_element(nums: Vec<i32>) -> i32 {
let mut candidate = 0;
let mut count = 0;
for n in nums {
if count == 0 {
candidate = n;
}
count += if n == candidate { 1 } else { -1 };
}
candidate
}
/** LC 169. Boyer-Moore: pairs of different values cancel; majority survives. */
export function majorityElement(nums: number[]): number {
let candidate = nums[0];
let count = 0;
for (const num of nums) {
if (count === 0) candidate = num;
count += num === candidate ? 1 : -1;
}
return candidate;
}
// LC 169. Boyer-Moore voting: the majority element survives pairwise cancellation.
func majorityElement(nums []int) int {
candidate, count := 0, 0
for _, x := range nums {
if count == 0 {
candidate = x
}
if x == candidate {
count++
} else {
count--
}
}
return candidate
}
// LC 169. Boyer-Moore: majority survives pairwise cancellation.
func majorityElement(_ nums: [Int]) -> Int {
var candidate = 0, count = 0
for x in nums {
if count == 0 { candidate = x }
count += x == candidate ? 1 : -1
}
return candidate
}
9. Design HashSet
Easy · LC 705
Implement a hash set supporting add, remove, and contains for integer keys without using built-in hash containers. Back it with a fixed array of buckets, hash each key with modulo the bucket count, and chain collisions inside each bucket using a list. Scan the chain before inserting so duplicates are never stored twice; with a sensible bucket count the average operation stays O(1).
class MyHashSet:
"""LC 705. Design HashSet.
Bucket array + chaining built from plain lists -- no dict or set
inside. key % SIZE picks a bucket; the bucket list holds the keys
that collide there. With SIZE prime and keys <= 10^6, chains stay
short, so add/remove/contains are O(1) average, O(n / SIZE) worst.
"""
_SIZE = 769
def __init__(self) -> None:
self._buckets: list[list[int]] = [[] for _ in range(self._SIZE)]
def add(self, key: int) -> None:
bucket = self._buckets[key % self._SIZE]
if key not in bucket:
bucket.append(key)
def remove(self, key: int) -> None:
bucket = self._buckets[key % self._SIZE]
if key in bucket:
bucket.remove(key)
def contains(self, key: int) -> bool:
return key in self._buckets[key % self._SIZE]
// LC 705. Fixed bucket array + chaining; remove via swap-with-back.
class MyHashSet {
static constexpr int BUCKETS = 1031;
vector<vector<int>> buckets;
public:
MyHashSet() : buckets(BUCKETS) {}
void add(int key) {
auto& bucket = buckets[key % BUCKETS];
for (int v : bucket)
if (v == key) return;
bucket.push_back(key);
}
void remove(int key) {
auto& bucket = buckets[key % BUCKETS];
for (size_t i = 0; i < bucket.size(); ++i)
if (bucket[i] == key) {
bucket[i] = bucket.back();
bucket.pop_back();
return;
}
}
bool contains(int key) {
for (int v : buckets[key % BUCKETS])
if (v == key) return true;
return false;
}
};
/// LC 705. Separate chaining: fixed bucket Vec, key % buckets picks the
/// chain, linear scan inside (chains stay short for uniform keys).
pub struct MyHashSet {
buckets: Vec<Vec<i32>>,
}
impl MyHashSet {
pub fn new() -> Self {
MyHashSet { buckets: vec![Vec::new(); 1024] }
}
fn index(&self, key: i32) -> usize {
key as usize % self.buckets.len()
}
pub fn add(&mut self, key: i32) {
let i = self.index(key);
if !self.buckets[i].contains(&key) {
self.buckets[i].push(key);
}
}
pub fn remove(&mut self, key: i32) {
let i = self.index(key);
self.buckets[i].retain(|&k| k != key);
}
pub fn contains(&self, key: i32) -> bool {
self.buckets[self.index(key)].contains(&key)
}
}
/** LC 705. Bucket array + chaining, no built-in Set; key % buckets picks a chain. */
export class MyHashSet {
private buckets: number[][];
private size: number;
constructor() {
this.size = 1024;
this.buckets = Array.from({ length: this.size }, () => []);
}
private bucketOf(key: number): number[] {
return this.buckets[key % this.size];
}
add(key: number): void {
const bucket = this.bucketOf(key);
if (bucket.indexOf(key) === -1) bucket.push(key);
}
remove(key: number): void {
const bucket = this.bucketOf(key);
const i = bucket.indexOf(key);
if (i !== -1) {
bucket[i] = bucket[bucket.length - 1]; // swap-remove: order is irrelevant
bucket.pop();
}
}
contains(key: number): boolean {
return this.bucketOf(key).indexOf(key) !== -1;
}
}
// LC 705. Fixed bucket array + chaining; remove via swap-with-back.
type MyHashSet struct {
buckets [][]int
}
func newMyHashSet() *MyHashSet {
return &MyHashSet{buckets: make([][]int, 1031)}
}
func (s *MyHashSet) add(key int) {
b := key % len(s.buckets)
for _, v := range s.buckets[b] {
if v == key {
return
}
}
s.buckets[b] = append(s.buckets[b], key)
}
func (s *MyHashSet) remove(key int) {
b := key % len(s.buckets)
bucket := s.buckets[b]
for i, v := range bucket {
if v == key {
bucket[i] = bucket[len(bucket)-1]
s.buckets[b] = bucket[:len(bucket)-1]
return
}
}
}
func (s *MyHashSet) contains(key int) bool {
for _, v := range s.buckets[key%len(s.buckets)] {
if v == key {
return true
}
}
return false
}
// LC 705. Fixed bucket array (1031 buckets) + chaining; remove via swap-with-back.
class MyHashSet {
private var buckets: [[Int]]
init() {
buckets = Array(repeating: [], count: 1031)
}
func add(_ key: Int) {
let b = key % buckets.count
if !buckets[b].contains(key) { buckets[b].append(key) }
}
func remove(_ key: Int) {
let b = key % buckets.count
if let i = buckets[b].firstIndex(of: key) {
buckets[b][i] = buckets[b][buckets[b].count - 1]
buckets[b].removeLast()
}
}
func contains(_ key: Int) -> Bool {
return buckets[key % buckets.count].contains(key)
}
}
10. Design HashMap
Easy · LC 706
Implement a hash map supporting put, get, and remove for integer keys and values without built-in hash containers. Use the same bucket array with chaining as a hash set, but store key and value pairs in each chain, and have put overwrite the value when the key already exists. The overwrite-on-existing-key check inside put is the detail most often missed; modulo bucketing keeps average operations O(1).
class MyHashMap:
"""LC 706. Design HashMap.
Same bucket-and-chain skeleton as LC 705, but each chain entry is a
mutable [key, value] pair so put can overwrite in place. get returns
-1 for a missing key per the problem contract. O(1) average per
operation, O(SIZE + n) space.
"""
_SIZE = 769
def __init__(self) -> None:
self._buckets: list[list[list[int]]] = [[] for _ in range(self._SIZE)]
def put(self, key: int, value: int) -> None:
bucket = self._buckets[key % self._SIZE]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key: int) -> int:
for pair in self._buckets[key % self._SIZE]:
if pair[0] == key:
return pair[1]
return -1
def remove(self, key: int) -> None:
bucket = self._buckets[key % self._SIZE]
for i, pair in enumerate(bucket):
if pair[0] == key:
bucket.pop(i)
return
// LC 706. Same chaining scheme, buckets hold (key, value) pairs.
class MyHashMap {
static constexpr int BUCKETS = 1031;
vector<vector<pair<int, int>>> buckets;
public:
MyHashMap() : buckets(BUCKETS) {}
void put(int key, int value) {
auto& bucket = buckets[key % BUCKETS];
for (auto& kv : bucket)
if (kv.first == key) {
kv.second = value;
return;
}
bucket.push_back({key, value});
}
int get(int key) {
for (const auto& kv : buckets[key % BUCKETS])
if (kv.first == key) return kv.second;
return -1;
}
void remove(int key) {
auto& bucket = buckets[key % BUCKETS];
for (size_t i = 0; i < bucket.size(); ++i)
if (bucket[i].first == key) {
bucket[i] = bucket.back();
bucket.pop_back();
return;
}
}
};
/// LC 706. Same chaining scheme as LC 705 but chains hold (key, value)
/// pairs; put overwrites in place, get returns -1 when absent.
pub struct MyHashMap {
buckets: Vec<Vec<(i32, i32)>>,
}
impl MyHashMap {
pub fn new() -> Self {
MyHashMap { buckets: vec![Vec::new(); 1024] }
}
fn index(&self, key: i32) -> usize {
key as usize % self.buckets.len()
}
pub fn put(&mut self, key: i32, value: i32) {
let i = self.index(key);
for pair in &mut self.buckets[i] {
if pair.0 == key {
pair.1 = value;
return;
}
}
self.buckets[i].push((key, value));
}
pub fn get(&self, key: i32) -> i32 {
let i = self.index(key);
self.buckets[i].iter().find(|&&(k, _)| k == key).map_or(-1, |&(_, v)| v)
}
pub fn remove(&mut self, key: i32) {
let i = self.index(key);
self.buckets[i].retain(|&(k, _)| k != key);
}
}
/** LC 706. Same chaining scheme as LC 705, with [key, value] pairs in chains. */
export class MyHashMap {
private buckets: [number, number][][];
private size: number;
constructor() {
this.size = 1024;
this.buckets = Array.from({ length: this.size }, () => []);
}
private bucketOf(key: number): [number, number][] {
return this.buckets[key % this.size];
}
put(key: number, value: number): void {
const bucket = this.bucketOf(key);
for (const pair of bucket) {
if (pair[0] === key) {
pair[1] = value;
return;
}
}
bucket.push([key, value]);
}
get(key: number): number {
for (const [k, v] of this.bucketOf(key)) {
if (k === key) return v;
}
return -1;
}
remove(key: number): void {
const bucket = this.bucketOf(key);
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i] = bucket[bucket.length - 1]; // swap-remove
bucket.pop();
return;
}
}
}
}
// LC 706. Same chaining scheme, buckets hold {key, value} pairs; get returns
// -1 for a missing key per the problem contract.
type MyHashMap struct {
buckets [][][2]int
}
func newMyHashMap() *MyHashMap {
return &MyHashMap{buckets: make([][][2]int, 1031)}
}
func (m *MyHashMap) put(key int, value int) {
b := key % len(m.buckets)
for i, kv := range m.buckets[b] {
if kv[0] == key {
m.buckets[b][i][1] = value
return
}
}
m.buckets[b] = append(m.buckets[b], [2]int{key, value})
}
func (m *MyHashMap) get(key int) int {
for _, kv := range m.buckets[key%len(m.buckets)] {
if kv[0] == key {
return kv[1]
}
}
return -1
}
func (m *MyHashMap) remove(key int) {
b := key % len(m.buckets)
bucket := m.buckets[b]
for i, kv := range bucket {
if kv[0] == key {
bucket[i] = bucket[len(bucket)-1]
m.buckets[b] = bucket[:len(bucket)-1]
return
}
}
}
// LC 706. Same chaining scheme, buckets hold (key, value) pairs.
class MyHashMap {
private var buckets: [[(key: Int, value: Int)]]
init() {
buckets = Array(repeating: [], count: 1031)
}
func put(_ key: Int, _ value: Int) {
let b = key % buckets.count
for i in 0..<buckets[b].count where buckets[b][i].key == key {
buckets[b][i].value = value
return
}
buckets[b].append((key, value))
}
func get(_ key: Int) -> Int {
for kv in buckets[key % buckets.count] where kv.key == key { return kv.value }
return -1
}
func remove(_ key: Int) {
let b = key % buckets.count
for i in 0..<buckets[b].count where buckets[b][i].key == key {
buckets[b][i] = buckets[b][buckets[b].count - 1]
buckets[b].removeLast()
return
}
}
}
11. Sort an Array
Medium · LC 912
Given an integer array, sort it in ascending order in O(n log n) time without calling the library sort. Implement merge sort: recursively split the array in half, sort each half, and merge the two sorted halves with two pointers into a buffer. Merge sort guarantees O(n log n) worst case, while a quicksort with naive pivots degrades to O(n^2) on sorted or equal-heavy inputs, which is worth being able to explain.
def sort_array(nums: list[int]) -> list[int]:
"""LC 912. Sort an Array.
Merge sort from scratch (no sorted()): split in half, recurse, then
merge the two sorted halves with two read pointers. The <= in the
merge keeps the sort stable. O(n log n) time, O(n) space.
"""
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = sort_array(nums[:mid])
right = sort_array(nums[mid:])
merged: list[int] = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
// LC 912. Merge sort from scratch: O(n log n), stable, one scratch buffer.
vector<int> sortArray(vector<int> nums) {
vector<int> buf(nums.size());
mergeSortRange(nums, buf, 0, static_cast<int>(nums.size()));
return nums;
}
/// LC 912. Top-down merge sort, no library sort: split at mid, recurse,
/// merge the sorted halves through one reused scratch buffer.
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
fn merge_sort(nums: &mut [i32], buf: &mut Vec<i32>) {
if nums.len() <= 1 {
return;
}
let mid = nums.len() / 2;
merge_sort(&mut nums[..mid], buf);
merge_sort(&mut nums[mid..], buf);
buf.clear();
let (mut i, mut j) = (0, mid);
while i < mid && j < nums.len() {
if nums[i] <= nums[j] {
buf.push(nums[i]);
i += 1;
} else {
buf.push(nums[j]);
j += 1;
}
}
buf.extend_from_slice(&nums[i..mid]);
buf.extend_from_slice(&nums[j..]);
nums.copy_from_slice(buf);
}
let mut buf = Vec::with_capacity(nums.len());
merge_sort(&mut nums, &mut buf);
nums
}
/** LC 912. Merge sort from scratch: stable, O(n log n) worst case. */
export function sortArray(nums: number[]): number[] {
const n = nums.length;
if (n <= 1) return nums;
const mid = n >> 1;
const left = sortArray(nums.slice(0, mid));
const right = sortArray(nums.slice(mid));
let i = 0;
let j = 0;
let k = 0;
while (i < left.length && j < right.length) {
nums[k++] = left[i] <= right[j] ? left[i++] : right[j++];
}
while (i < left.length) nums[k++] = left[i++];
while (j < right.length) nums[k++] = right[j++];
return nums;
}
// LC 912. Merge sort from scratch via a recursive closure: split [lo, hi) in
// half, recurse, merge through one scratch buffer. O(n log n), stable.
func sortArray(nums []int) []int {
buf := make([]int, len(nums))
var sortRange func(lo, hi int)
sortRange = func(lo, hi int) {
if hi-lo <= 1 {
return
}
mid := lo + (hi-lo)/2
sortRange(lo, mid)
sortRange(mid, hi)
i, j, k := lo, mid, lo
for i < mid && j < hi {
if nums[i] <= nums[j] {
buf[k] = nums[i]
i++
} else {
buf[k] = nums[j]
j++
}
k++
}
for i < mid {
buf[k] = nums[i]
i++
k++
}
for j < hi {
buf[k] = nums[j]
j++
k++
}
copy(nums[lo:hi], buf[lo:hi])
}
sortRange(0, len(nums))
return nums
}
// LC 912. Merge sort from scratch via a nested range sorter: O(n log n), stable,
// one scratch buffer shared by every merge.
func sortArray(_ nums: [Int]) -> [Int] {
var nums = nums
var buf = [Int](repeating: 0, count: nums.count)
func mergeSortRange(_ lo: Int, _ hi: Int) {
if hi - lo <= 1 { return }
let mid = lo + (hi - lo) / 2
mergeSortRange(lo, mid)
mergeSortRange(mid, hi)
var i = lo, j = mid, k = lo
while i < mid && j < hi {
if nums[i] <= nums[j] {
buf[k] = nums[i]
i += 1
} else {
buf[k] = nums[j]
j += 1
}
k += 1
}
while i < mid {
buf[k] = nums[i]
i += 1
k += 1
}
while j < hi {
buf[k] = nums[j]
j += 1
k += 1
}
for idx in lo..<hi { nums[idx] = buf[idx] }
}
mergeSortRange(0, nums.count)
return nums
}
12. Sort Colors
Medium · LC 75
Given an array containing only 0s, 1s, and 2s, sort it in place in a single pass. Apply the Dutch national flag partition with low, mid, and high pointers: swap a 0 at mid down to low, swap a 2 up to high, and step over 1s. After swapping with high, do not advance mid, because the element brought in from the right is still unexamined.
def sort_colors(nums: list[int]) -> None:
"""LC 75. Sort Colors.
Dutch national flag, one pass in place: everything left of low is 0,
everything right of high is 2, mid scans the unknown middle. After
swapping a 2 to the back, mid does NOT advance -- the swapped-in
value is still unclassified. O(n) time, O(1) space.
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
// LC 75. Dutch national flag, one pass: 0s below low, 2s above high.
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = static_cast<int>(nums.size()) - 1;
while (mid <= high) {
if (nums[mid] == 0) swap(nums[low++], nums[mid++]);
else if (nums[mid] == 2) swap(nums[mid], nums[high--]); // re-examine mid
else ++mid;
}
}
/// LC 75. Dutch national flag, one pass: 0s swap down to low, 2s swap up to
/// high (do NOT advance mid then -- the swapped-in value is unexamined).
pub fn sort_colors(nums: &mut Vec<i32>) {
let (mut low, mut mid, mut high) = (0usize, 0usize, nums.len());
while mid < high {
match nums[mid] {
0 => {
nums.swap(low, mid);
low += 1;
mid += 1;
}
2 => {
high -= 1;
nums.swap(mid, high);
}
_ => mid += 1,
}
}
}
/** LC 75. Dutch national flag: 0s before low, 2s after high, one pass. */
export function sortColors(nums: number[]): void {
let low = 0;
let mid = 0;
let high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 2) {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--; // do NOT advance mid: the swapped-in value is unexamined
} else {
mid++;
}
}
}
// LC 75. Dutch national flag, one pass: 0s below low, 2s above high; after
// swapping a 2 to the back, mid stays put to re-examine the swapped-in value.
func sortColors(nums []int) {
low, mid, high := 0, 0, len(nums)-1
for mid <= high {
switch nums[mid] {
case 0:
nums[low], nums[mid] = nums[mid], nums[low]
low++
mid++
case 2:
nums[mid], nums[high] = nums[high], nums[mid]
high--
default:
mid++
}
}
}
// LC 75. Dutch national flag, one pass: 0s below low, 2s above high; after
// swapping a 2 back, mid stays put to re-examine the swapped-in value.
func sortColors(_ nums: inout [Int]) {
var low = 0, mid = 0, high = nums.count - 1
while mid <= high {
if nums[mid] == 0 {
nums.swapAt(low, mid)
low += 1
mid += 1
} else if nums[mid] == 2 {
nums.swapAt(mid, high)
high -= 1
} else {
mid += 1
}
}
}
13. Top K Frequent Elements
Medium · LC 347
Given an integer array and k, return the k most frequent values in any order. Count occurrences with a hash map, then bucket by frequency: build an array where slot f holds the values appearing exactly f times, and collect from the highest slot down until k values are gathered. Frequency never exceeds n, so the bucket array is linear in size and the whole solution runs in O(n), beating a heap.
def top_k_frequent(nums: list[int], k: int) -> list[int]:
"""LC 347. Top K Frequent Elements.
Bucket sort by frequency: a value appearing c times goes in
buckets[c], and c can never exceed len(nums), so the bucket array is
bounded. Sweep from the high end until k values are collected.
O(n) time, O(n) space -- no heap, no sort.
"""
counts: dict[int, int] = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for num, count in counts.items():
buckets[count].append(num)
ans: list[int] = []
for count in range(len(nums), 0, -1):
for num in buckets[count]:
ans.append(num)
if len(ans) == k:
return ans
return ans
// LC 347. Bucket sort by frequency: index = count, scan from the top.
vector<int> topKFrequent(vector<int> nums, int k) {
unordered_map<int, int> freq;
for (int x : nums) ++freq[x];
int n = static_cast<int>(nums.size());
vector<vector<int>> buckets(n + 1);
for (const auto& [val, count] : freq) buckets[count].push_back(val);
vector<int> ans;
for (int count = n; count >= 1; --count)
for (int val : buckets[count]) {
ans.push_back(val);
if (static_cast<int>(ans.size()) == k) return ans;
}
return ans;
}
/// LC 347. Bucket sort by frequency: index = count (at most n), then sweep
/// buckets from high to low until k numbers are collected. O(n), no heap.
pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
let n = nums.len();
let mut counts = HashMap::new();
for num in nums {
*counts.entry(num).or_insert(0usize) += 1;
}
let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); n + 1];
for (num, freq) in counts {
buckets[freq].push(num);
}
let k = k as usize;
let mut ans = Vec::with_capacity(k);
for bucket in buckets.iter().rev() {
for &num in bucket {
ans.push(num);
if ans.len() == k {
return ans;
}
}
}
ans
}
/** LC 347. Bucket sort by frequency: index = count, so O(n) beats a heap. */
export function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const num of nums) freq.set(num, (freq.get(num) ?? 0) + 1);
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, count] of freq) buckets[count].push(num);
const ans: number[] = [];
for (let count = buckets.length - 1; count >= 1 && ans.length < k; count--) {
for (const num of buckets[count]) {
ans.push(num);
if (ans.length === k) break;
}
}
return ans;
}
// LC 347. Bucket sort by frequency: index = count (never exceeds n), scan
// from the top until k values are collected. O(n), no heap, no sort.
func topKFrequent(nums []int, k int) []int {
freq := make(map[int]int)
for _, x := range nums {
freq[x]++
}
buckets := make([][]int, len(nums)+1)
for val, count := range freq {
buckets[count] = append(buckets[count], val)
}
ans := make([]int, 0, k)
for count := len(nums); count >= 1; count-- {
for _, val := range buckets[count] {
ans = append(ans, val)
if len(ans) == k {
return ans
}
}
}
return ans
}
// LC 347. Bucket sort by frequency: index = count, scan from the top.
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var freq: [Int: Int] = [:]
for x in nums { freq[x, default: 0] += 1 }
var buckets: [[Int]] = Array(repeating: [], count: nums.count + 1)
for (val, count) in freq { buckets[count].append(val) }
var ans: [Int] = []
for count in stride(from: nums.count, through: 1, by: -1) {
for val in buckets[count] {
ans.append(val)
if ans.count == k { return ans }
}
}
return ans
}
14. Encode and Decode Strings
Medium · LC 271
Design encode and decode functions that pack a list of strings into one string and recover it exactly, even when the data contains any delimiter characters. Prefix each string with its length and a sentinel such as '#', producing chunks like 4#word, then decode by reading digits up to the sentinel and slicing exactly that many characters. The length prefix removes all ambiguity because payload bytes are never interpreted, unlike escaping schemes.
def encode(strs: list[str]) -> str:
"""LC 271. Encode and Decode Strings (encode half).
Each string becomes "<length>#<payload>". The length prefix says
exactly how many chars to read, so payloads may freely contain '#'
or digits -- no escaping needed. O(total chars) time and space.
"""
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(s: str) -> list[str]:
"""LC 271. Encode and Decode Strings (decode half).
Read digits up to the first un-consumed '#' to get the length, slice
exactly that many chars as the payload, jump past it, repeat. The
'#' found this way is always a delimiter because every payload is
skipped wholesale. O(total chars) time and space.
"""
ans: list[str] = []
i = 0
while i < len(s):
j = i
while s[j] != "#":
j += 1
length = int(s[i:j])
ans.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
return ans
// LC 271. Length prefix + '#' delimiter makes any byte content unambiguous.
string encode(vector<string> strs) {
string out;
for (const string& s : strs) out += to_string(s.size()) + "#" + s;
return out;
}
// LC 271. Read digits up to '#', then consume exactly that many chars.
vector<string> decode(string s) {
vector<string> out;
size_t i = 0;
while (i < s.size()) {
size_t hash = s.find('#', i);
size_t len = static_cast<size_t>(stoi(s.substr(i, hash - i)));
out.push_back(s.substr(hash + 1, len));
i = hash + 1 + len;
}
return out;
}
/// LC 271 (encode). Length-prefix framing: "len#payload" per string, so
/// empty strings and '#' inside payloads survive the round trip.
pub fn encode(strs: Vec<String>) -> String {
let mut out = String::new();
for s in &strs {
out.push_str(&s.len().to_string());
out.push('#');
out.push_str(s);
}
out
}
/// LC 271 (decode). Byte-based parse: read digits until '#', then take
/// exactly that many bytes as the payload -- '#' in payloads is never a
/// delimiter because we jump over it by length.
pub fn decode(s: String) -> Vec<String> {
let bytes = s.as_bytes();
let mut ans = Vec::new();
let mut i = 0;
while i < bytes.len() {
let mut len = 0usize;
while bytes[i] != b'#' {
len = len * 10 + (bytes[i] - b'0') as usize;
i += 1;
}
i += 1;
ans.push(String::from_utf8(bytes[i..i + len].to_vec()).unwrap());
i += len;
}
ans
}
/** LC 271. Length prefix + '#': "<len>#<chars>", so '#' inside data is safe. */
export function encode(strs: string[]): string {
let out = "";
for (const str of strs) out += `${str.length}#${str}`;
return out;
}
/** LC 271. Read digits up to '#', then take exactly that many characters. */
export function decode(s: string): string[] {
const ans: string[] = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== "#") j++;
const len = Number(s.slice(i, j));
ans.push(s.slice(j + 1, j + 1 + len));
i = j + 1 + len;
}
return ans;
}
// LC 271. Length prefix + '#' delimiter makes any byte content unambiguous.
func encode(strs []string) string {
var sb strings.Builder
for _, s := range strs {
sb.WriteString(strconv.Itoa(len(s)))
sb.WriteByte('#')
sb.WriteString(s)
}
return sb.String()
}
// LC 271. Read digits up to '#' to get the length, then consume exactly that
// many chars as the payload; every payload is skipped wholesale.
func decode(s string) []string {
ans := []string{}
i := 0
for i < len(s) {
length := 0
for s[i] != '#' {
length = length*10 + int(s[i]-'0')
i++
}
i++ // skip '#'
ans = append(ans, s[i:i+length])
i += length
}
return ans
}
// LC 271. Length prefix + '#' delimiter makes any payload content unambiguous.
func encode(_ strs: [String]) -> String {
return strs.map { "\($0.count)#\($0)" }.joined()
}
// LC 271. Read digits up to '#', then consume exactly that many chars.
func decode(_ s: String) -> [String] {
let chars = Array(s)
var ans: [String] = []
var i = 0
while i < chars.count {
var j = i
while chars[j] != "#" { j += 1 }
let length = Int(String(chars[i..<j]))!
ans.append(String(chars[(j + 1)..<(j + 1 + length)]))
i = j + 1 + length
}
return ans
}
15. Range Sum Query 2D Immutable
Medium · LC 304
Preprocess an immutable integer matrix so sumRegion(row1, col1, row2, col2) returns any rectangle's sum in O(1). Build a prefix table with one extra row and column of zeros, where each entry holds the sum of the rectangle from the origin up to that cell. Answer queries by inclusion-exclusion, subtracting the top and left strips and adding back the doubly removed corner; the zero padding eliminates boundary checks.
class NumMatrix:
"""LC 304. Range Sum Query 2D - Immutable.
Padded 2-D prefix sums: prefix[r][c] holds the sum of the r x c
rectangle anchored at the origin, and any sub-rectangle falls out by
inclusion-exclusion (whole - top - left + double-subtracted corner).
O(mn) build, O(1) per query, O(mn) space.
"""
def __init__(self, matrix: list[list[int]]) -> None:
rows, cols = len(matrix), len(matrix[0])
self._prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
row_sum = 0
for c in range(cols):
row_sum += matrix[r][c]
self._prefix[r + 1][c + 1] = self._prefix[r][c + 1] + row_sum
def sum_region(self, row1: int, col1: int, row2: int, col2: int) -> int:
p = self._prefix
return (
p[row2 + 1][col2 + 1]
- p[row1][col2 + 1]
- p[row2 + 1][col1]
+ p[row1][col1]
)
// LC 304. 2-D prefix sums with a padded row/col; region = inclusion-exclusion.
class NumMatrix {
vector<vector<int>> prefix; // prefix[r][c] = sum of matrix[0..r-1][0..c-1]
public:
NumMatrix(vector<vector<int>> matrix) {
int rows = static_cast<int>(matrix.size()), cols = static_cast<int>(matrix[0].size());
prefix.assign(rows + 1, vector<int>(cols + 1, 0));
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c)
prefix[r + 1][c + 1] = prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c] + matrix[r][c];
}
int sumRegion(int row1, int col1, int row2, int col2) {
return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1];
}
};
/// LC 304. 2-D prefix sums with a padded zero row/column, so sum_region is
/// one inclusion-exclusion expression with no edge special-casing.
pub struct NumMatrix {
prefix: Vec<Vec<i32>>,
}
impl NumMatrix {
pub fn new(matrix: Vec<Vec<i32>>) -> Self {
let (rows, cols) = (matrix.len(), matrix[0].len());
let mut prefix = vec![vec![0; cols + 1]; rows + 1];
for r in 0..rows {
for c in 0..cols {
prefix[r + 1][c + 1] =
matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
}
}
NumMatrix { prefix }
}
pub fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
let (r1, c1) = (row1 as usize, col1 as usize);
let (r2, c2) = (row2 as usize + 1, col2 as usize + 1);
self.prefix[r2][c2] - self.prefix[r1][c2] - self.prefix[r2][c1] + self.prefix[r1][c1]
}
}
/** LC 304. Padded 2-D prefix sums: sumRegion is four lookups, O(1) a query. */
export class NumMatrix {
private prefix: number[][];
constructor(matrix: number[][]) {
const rows = matrix.length;
const cols = matrix[0].length;
this.prefix = Array.from({ length: rows + 1 }, () => new Array<number>(cols + 1).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
this.prefix[r + 1][c + 1] =
matrix[r][c] + this.prefix[r][c + 1] + this.prefix[r + 1][c] - this.prefix[r][c];
}
}
}
sumRegion(row1: number, col1: number, row2: number, col2: number): number {
return (
this.prefix[row2 + 1][col2 + 1] -
this.prefix[row1][col2 + 1] -
this.prefix[row2 + 1][col1] +
this.prefix[row1][col1]
);
}
}
// LC 304. 2-D prefix sums with a padded row/col; any region falls out by
// inclusion-exclusion. O(mn) build, O(1) per query.
type NumMatrix struct {
prefix [][]int // prefix[r][c] = sum of matrix[0..r-1][0..c-1]
}
func newNumMatrix(matrix [][]int) *NumMatrix {
rows, cols := len(matrix), len(matrix[0])
prefix := make([][]int, rows+1)
for r := range prefix {
prefix[r] = make([]int, cols+1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
prefix[r+1][c+1] = prefix[r][c+1] + prefix[r+1][c] - prefix[r][c] + matrix[r][c]
}
}
return &NumMatrix{prefix: prefix}
}
func (m *NumMatrix) sumRegion(row1 int, col1 int, row2 int, col2 int) int {
p := m.prefix
return p[row2+1][col2+1] - p[row1][col2+1] - p[row2+1][col1] + p[row1][col1]
}
// LC 304. 2-D prefix sums with a padded row/col; region = inclusion-exclusion.
class NumMatrix {
private var prefix: [[Int]] // prefix[r][c] = sum of matrix[0..<r][0..<c]
init(_ matrix: [[Int]]) {
let rows = matrix.count, cols = matrix[0].count
prefix = Array(repeating: Array(repeating: 0, count: cols + 1), count: rows + 1)
for r in 0..<rows {
for c in 0..<cols {
prefix[r + 1][c + 1] =
prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c] + matrix[r][c]
}
}
}
func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1]
- prefix[row2 + 1][col1] + prefix[row1][col1]
}
}
16. Product of Array Except Self
Medium · LC 238
Given an integer array, return an array where each position holds the product of all other elements, without division and in O(n). Do a forward pass writing the product of everything strictly left of each index, then a backward pass multiplying in a running product of everything to the right. The prefix-times-suffix decomposition is the idea; carrying the suffix product in one variable keeps extra space at O(1).
def product_except_self(nums: list[int]) -> list[int]:
"""LC 238. Product of Array Except Self.
No division: a forward pass writes the product of everything BEFORE
each index, then a backward pass multiplies in the product of
everything AFTER it, carried in a single scalar. O(n) time, O(1)
extra space beyond the output array.
"""
n = len(nums)
ans = [1] * n
for i in range(1, n):
ans[i] = ans[i - 1] * nums[i - 1]
suffix = 1
for i in range(n - 1, -1, -1):
ans[i] *= suffix
suffix *= nums[i]
return ans
// LC 238. ans[i] = product of everything left of i, then multiply in a
// running suffix product on the way back. No division.
vector<int> productExceptSelf(vector<int> nums) {
int n = static_cast<int>(nums.size());
vector<int> ans(n, 1);
for (int i = 1; i < n; ++i) ans[i] = ans[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; --i) {
ans[i] *= suffix;
suffix *= nums[i];
}
return ans;
}
/// LC 238. No division: ans[i] = product of everything left of i (forward
/// pass), then multiply in everything right of i (backward pass).
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![1; n];
let mut prefix = 1;
for i in 0..n {
ans[i] = prefix;
prefix *= nums[i];
}
let mut suffix = 1;
for i in (0..n).rev() {
ans[i] *= suffix;
suffix *= nums[i];
}
ans
}
/** LC 238. ans holds prefix products; a running suffix multiplies in reverse. */
export function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const ans = new Array<number>(n);
ans[0] = 1;
for (let i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
ans[i] *= suffix;
suffix *= nums[i];
}
return ans;
}
// LC 238. No division: a forward pass writes the product of everything left
// of i, then a running suffix product multiplies in everything right of it.
func productExceptSelf(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i := range ans {
ans[i] = 1
}
for i := 1; i < n; i++ {
ans[i] = ans[i-1] * nums[i-1]
}
suffix := 1
for i := n - 1; i >= 0; i-- {
ans[i] *= suffix
suffix *= nums[i]
}
return ans
}
// LC 238. ans[i] = product of everything left of i, then multiply in a running
// suffix product on the way back. No division.
func productExceptSelf(_ nums: [Int]) -> [Int] {
let n = nums.count
var ans = [Int](repeating: 1, count: n)
for i in 1..<n { ans[i] = ans[i - 1] * nums[i - 1] }
var suffix = 1
for i in stride(from: n - 1, through: 0, by: -1) {
ans[i] *= suffix
suffix *= nums[i]
}
return ans
}
17. Valid Sudoku
Medium · LC 36
Given a 9x9 board partially filled with digits, decide whether the placed digits break any Sudoku rule, ignoring solvability. Scan every cell once while maintaining nine row sets, nine column sets, and nine box sets, reporting failure the moment a digit repeats within any of its three sets. The box index is (row / 3) * 3 + col / 3 with integer division, the one formula worth memorizing.
def is_valid_sudoku(board: list[list[str]]) -> bool:
"""LC 36. Valid Sudoku.
One scan with 9 row sets, 9 column sets, and 9 box sets; box index
is (r // 3) * 3 + c // 3. A digit already present in any of its
three sets is a violation. O(81) time, O(81) space -- constant for
the fixed 9 x 9 board.
"""
rows: list[set[str]] = [set() for _ in range(9)]
cols: list[set[str]] = [set() for _ in range(9)]
boxes: list[set[str]] = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
digit = board[r][c]
if digit == ".":
continue
b = (r // 3) * 3 + c // 3
if digit in rows[r] or digit in cols[c] or digit in boxes[b]:
return False
rows[r].add(digit)
cols[c].add(digit)
boxes[b].add(digit)
return True
// LC 36. One bitmask per row, column, and 3x3 box; a repeated bit = invalid.
bool isValidSudoku(vector<vector<char>> board) {
int rows[9] = {}, cols[9] = {}, boxes[9] = {};
for (int r = 0; r < 9; ++r)
for (int c = 0; c < 9; ++c) {
if (board[r][c] == '.') continue;
int bit = 1 << (board[r][c] - '1');
int b = (r / 3) * 3 + c / 3;
if ((rows[r] & bit) || (cols[c] & bit) || (boxes[b] & bit)) return false;
rows[r] |= bit;
cols[c] |= bit;
boxes[b] |= bit;
}
return true;
}
/// LC 36. Three 9x9 seen-tables (rows, cols, boxes); box id is
/// (r / 3) * 3 + c / 3. Any repeat hit = invalid.
pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
let mut rows = [[false; 9]; 9];
let mut cols = [[false; 9]; 9];
let mut boxes = [[false; 9]; 9];
for r in 0..9 {
for c in 0..9 {
let ch = board[r][c];
if ch == '.' {
continue;
}
let d = ch as usize - '1' as usize;
let b = (r / 3) * 3 + c / 3;
if rows[r][d] || cols[c][d] || boxes[b][d] {
return false;
}
rows[r][d] = true;
cols[c][d] = true;
boxes[b][d] = true;
}
}
true
}
/** LC 36. One pass with row/col/box seen-bitmask arrays; box = 3*(r/3)+c/3. */
export function isValidSudoku(board: string[][]): boolean {
const rows = new Array<number>(9).fill(0);
const cols = new Array<number>(9).fill(0);
const boxes = new Array<number>(9).fill(0);
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const cell = board[r][c];
if (cell === ".") continue;
const bit = 1 << (Number(cell) - 1);
const b = 3 * Math.floor(r / 3) + Math.floor(c / 3);
if ((rows[r] & bit) || (cols[c] & bit) || (boxes[b] & bit)) return false;
rows[r] |= bit;
cols[c] |= bit;
boxes[b] |= bit;
}
}
return true;
}
// LC 36. One bitmask per row, column, and 3x3 box; a repeated bit = invalid.
// Box index is (r/3)*3 + c/3.
func isValidSudoku(board [][]byte) bool {
var rows, cols, boxes [9]int
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
if board[r][c] == '.' {
continue
}
bit := 1 << (board[r][c] - '1')
b := (r/3)*3 + c/3
if rows[r]&bit != 0 || cols[c]&bit != 0 || boxes[b]&bit != 0 {
return false
}
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
}
}
return true
}
// LC 36. One bitmask per row, column, and 3x3 box; a repeated bit = invalid.
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rows = [Int](repeating: 0, count: 9)
var cols = [Int](repeating: 0, count: 9)
var boxes = [Int](repeating: 0, count: 9)
for r in 0..<9 {
for c in 0..<9 {
let cell = board[r][c]
if cell == "." { continue }
let bit = 1 << Int(cell.asciiValue! - 49) // '1' is ASCII 49
let b = (r / 3) * 3 + c / 3
if rows[r] & bit != 0 || cols[c] & bit != 0 || boxes[b] & bit != 0 { return false }
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
}
}
return true
}
18. Longest Consecutive Sequence
Medium · LC 128
Given an unsorted integer array, return the length of the longest run of consecutive values, in O(n) rather than by sorting. Load everything into a hash set, then for each value whose predecessor n-1 is absent, count upward while n+1, n+2, and so on remain in the set. Starting only at sequence beginnings is the trick: every element is touched a constant number of times, keeping the scan linear.
def longest_consecutive(nums: list[int]) -> int:
"""LC 128. Longest Consecutive Sequence.
Dump everything in a set, then only start counting upward from n
when n - 1 is absent (n is the START of a run). Every element is
visited at most twice, so the nested-looking while is still O(n)
time, O(n) space.
"""
num_set = set(nums)
best = 0
for num in num_set:
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
best = max(best, length)
return best
// LC 128. Only start counting at sequence heads (n-1 absent), so each
// element is visited O(1) times overall.
int longestConsecutive(vector<int> nums) {
unordered_set<int> values(nums.begin(), nums.end());
int best = 0;
for (int x : values) {
if (values.count(x - 1)) continue; // not a sequence start
int len = 1;
while (values.count(x + len)) ++len;
best = max(best, len);
}
return best;
}
/// LC 128. HashSet, then only count up from sequence STARTS (n - 1 absent),
/// so every element is visited O(1) amortized times.
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
let set: HashSet<i32> = nums.into_iter().collect();
let mut best = 0;
for &n in &set {
if set.contains(&(n - 1)) {
continue;
}
let mut len = 1;
let mut cur = n;
while set.contains(&(cur + 1)) {
cur += 1;
len += 1;
}
best = best.max(len);
}
best
}
/** LC 128. Set lookups; only count up from n when n-1 is absent, so O(n). */
export function longestConsecutive(nums: number[]): number {
const set = new Set(nums);
let best = 0;
for (const num of set) {
if (set.has(num - 1)) continue; // not a sequence start
let end = num;
while (set.has(end + 1)) end++;
best = Math.max(best, end - num + 1);
}
return best;
}
// LC 128. Only start counting upward at sequence heads (x-1 absent), so each
// element is visited O(1) times overall despite the inner loop.
func longestConsecutive(nums []int) int {
values := make(map[int]struct{}, len(nums))
for _, x := range nums {
values[x] = struct{}{}
}
best := 0
for x := range values {
if _, ok := values[x-1]; ok {
continue // not a sequence start
}
length := 1
for {
if _, ok := values[x+length]; !ok {
break
}
length++
}
if length > best {
best = length
}
}
return best
}
// LC 128. Only start counting at sequence heads (n-1 absent), so each element
// is visited O(1) times overall.
func longestConsecutive(_ nums: [Int]) -> Int {
let values = Set(nums)
var best = 0
for x in values {
if values.contains(x - 1) { continue } // not a sequence start
var length = 1
while values.contains(x + length) { length += 1 }
best = max(best, length)
}
return best
}
19. Best Time to Buy And Sell Stock II
Medium · LC 122
Given daily stock prices with unlimited transactions while holding at most one share, return the maximum total profit. Sum every positive day-to-day difference: whenever tomorrow's price beats today's, add the delta, which amounts to buying before every rise and selling at every peak. The justification is that any optimal trade decomposes into consecutive single-day gains, so the greedy one-pass O(n) sweep loses nothing.
def max_profit(prices: list[int]) -> int:
"""LC 122. Best Time to Buy and Sell Stock II.
With unlimited transactions, any upward path decomposes into its
daily rises, so summing every positive delta prices[i] - prices[i-1]
captures the maximum profit. O(n) time, O(1) space.
"""
profit = 0
for i in range(1, len(prices)):
delta = prices[i] - prices[i - 1]
if delta > 0:
profit += delta
return profit
// LC 122. Every upward day is collectable: sum all positive deltas.
int maxProfit(vector<int> prices) {
int profit = 0;
for (size_t i = 1; i < prices.size(); ++i) profit += max(0, prices[i] - prices[i - 1]);
return profit;
}
/// LC 122. Every upward day-to-day move is collectable: sum the positive
/// deltas and you have the optimal multi-transaction profit.
pub fn max_profit(prices: Vec<i32>) -> i32 {
prices.windows(2).map(|w| (w[1] - w[0]).max(0)).sum()
}
/** LC 122. Every upward day is its own trade: sum all positive deltas. */
export function maxProfit(prices: number[]): number {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
}
return profit;
}
// LC 122. Every upward day is collectable: sum all positive deltas.
func maxProfit(prices []int) int {
profit := 0
for i := 1; i < len(prices); i++ {
if delta := prices[i] - prices[i-1]; delta > 0 {
profit += delta
}
}
return profit
}
// LC 122. Every upward day is collectable: sum all positive deltas.
func maxProfit(_ prices: [Int]) -> Int {
var profit = 0
for (prev, cur) in zip(prices, prices.dropFirst()) { profit += max(0, cur - prev) }
return profit
}
20. Majority Element II
Medium · LC 229
Given an integer array, return all values appearing more than n/3 times, of which at most two can exist. Run Boyer-Moore voting with two candidates and two counters, replacing a candidate only when its counter is zero and the element matches neither. The voting pass alone is insufficient: a second pass must verify each surviving candidate's true count exceeds n/3, keeping the whole thing O(n) time and O(1) space.
def majority_element_ii(nums: list[int]) -> list[int]:
"""LC 229. Majority Element II.
At most two values can exceed n/3, so run Boyer-Moore with two
candidates: a mismatch against both decrements both counts, and a
zeroed slot adopts the newcomer. Surviving candidates are only
POSSIBLE answers, so a final counting pass verifies each really
exceeds n/3. O(n) time, O(1) space.
"""
cand1: int | None = None
cand2: int | None = None
count1 = count2 = 0
for num in nums:
if cand1 == num:
count1 += 1
elif cand2 == num:
count2 += 1
elif count1 == 0:
cand1, count1 = num, 1
elif count2 == 0:
cand2, count2 = num, 1
else:
count1 -= 1
count2 -= 1
ans: list[int] = []
for cand in (cand1, cand2):
if cand is not None and sum(1 for num in nums if num == cand) > len(nums) // 3:
ans.append(cand)
return ans
// LC 229. Boyer-Moore with two candidates (at most two values exceed n/3),
// then a second pass verifies the counts.
vector<int> majorityElementII(vector<int> nums) {
int cand1 = 0, cand2 = 1, count1 = 0, count2 = 0; // distinct seeds
for (int x : nums) {
if (x == cand1) ++count1;
else if (x == cand2) ++count2;
else if (count1 == 0) { cand1 = x; count1 = 1; }
else if (count2 == 0) { cand2 = x; count2 = 1; }
else { --count1; --count2; }
}
count1 = count2 = 0;
for (int x : nums) {
if (x == cand1) ++count1;
else if (x == cand2) ++count2;
}
vector<int> ans;
int n = static_cast<int>(nums.size());
if (count1 > n / 3) ans.push_back(cand1);
if (count2 > n / 3) ans.push_back(cand2);
return ans;
}
/// LC 229. Boyer-Moore with TWO candidates (at most two values can exceed
/// n/3), then a second pass verifies the survivors' real counts.
pub fn majority_element_ii(nums: Vec<i32>) -> Vec<i32> {
let (mut cand1, mut cand2) = (0, 1);
let (mut count1, mut count2) = (0i32, 0i32);
for &n in &nums {
if n == cand1 {
count1 += 1;
} else if n == cand2 {
count2 += 1;
} else if count1 == 0 {
cand1 = n;
count1 = 1;
} else if count2 == 0 {
cand2 = n;
count2 = 1;
} else {
count1 -= 1;
count2 -= 1;
}
}
let threshold = nums.len() / 3;
[cand1, cand2]
.into_iter()
.filter(|&cand| nums.iter().filter(|&&n| n == cand).count() > threshold)
.collect()
}
/** LC 229. Boyer-Moore with two candidates (at most two > n/3), then verify. */
export function majorityElementII(nums: number[]): number[] {
let cand1 = 0;
let cand2 = 1; // any two distinct seeds work with zero counts
let count1 = 0;
let count2 = 0;
for (const num of nums) {
if (num === cand1) count1++;
else if (num === cand2) count2++;
else if (count1 === 0) {
cand1 = num;
count1 = 1;
} else if (count2 === 0) {
cand2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (const num of nums) {
if (num === cand1) count1++;
else if (num === cand2) count2++;
}
const ans: number[] = [];
const threshold = Math.floor(nums.length / 3);
if (count1 > threshold) ans.push(cand1);
if (count2 > threshold) ans.push(cand2);
return ans;
}
// LC 229. Boyer-Moore with two candidates (at most two values exceed n/3),
// then a second pass verifies the surviving candidates' counts.
func majorityElementII(nums []int) []int {
cand1, cand2, count1, count2 := 0, 1, 0, 0 // distinct seeds
for _, x := range nums {
switch {
case x == cand1:
count1++
case x == cand2:
count2++
case count1 == 0:
cand1, count1 = x, 1
case count2 == 0:
cand2, count2 = x, 1
default:
count1--
count2--
}
}
count1, count2 = 0, 0
for _, x := range nums {
if x == cand1 {
count1++
} else if x == cand2 {
count2++
}
}
ans := []int{}
if count1 > len(nums)/3 {
ans = append(ans, cand1)
}
if count2 > len(nums)/3 {
ans = append(ans, cand2)
}
return ans
}
// LC 229. Boyer-Moore with two candidates (at most two values exceed n/3),
// then a second pass verifies the counts.
func majorityElementII(_ nums: [Int]) -> [Int] {
var cand1 = 0, cand2 = 1, count1 = 0, count2 = 0 // distinct seeds
for x in nums {
if x == cand1 {
count1 += 1
} else if x == cand2 {
count2 += 1
} else if count1 == 0 {
cand1 = x
count1 = 1
} else if count2 == 0 {
cand2 = x
count2 = 1
} else {
count1 -= 1
count2 -= 1
}
}
count1 = 0
count2 = 0
for x in nums {
if x == cand1 {
count1 += 1
} else if x == cand2 {
count2 += 1
}
}
var ans: [Int] = []
if count1 > nums.count / 3 { ans.append(cand1) }
if count2 > nums.count / 3 { ans.append(cand2) }
return ans
}
21. Subarray Sum Equals K
Medium · LC 560
Given an integer array and a target k, count contiguous subarrays whose elements sum exactly to k. Sweep once with a running prefix sum and a hash map from prefix-sum value to occurrence count, adding the count stored under sum minus k at every step before recording the current sum. Seed the map with zero mapping to one so subarrays starting at index zero count; the map handles negatives where windows fail.
def subarray_sum(nums: list[int], k: int) -> int:
"""LC 560. Subarray Sum Equals K.
A subarray sums to k exactly when prefix[j] - prefix[i] == k, so
count, for each running prefix, how many earlier prefixes equal
prefix - k. Seeding {0: 1} counts subarrays that start at index 0.
Works with negatives where sliding windows fail. O(n) time, O(n)
space.
"""
counts: dict[int, int] = {0: 1}
prefix = 0
ans = 0
for num in nums:
prefix += num
ans += counts.get(prefix - k, 0)
counts[prefix] = counts.get(prefix, 0) + 1
return ans
// LC 560. Count prefix sums seen so far; sum - k seen before means a
// subarray summing to k ends here.
int subarraySum(vector<int> nums, int k) {
unordered_map<long long, int> seen{{0, 1}};
long long sum = 0;
int count = 0;
for (int x : nums) {
sum += x;
auto it = seen.find(sum - k);
if (it != seen.end()) count += it->second;
++seen[sum];
}
return count;
}
/// LC 560. Running prefix sum + HashMap of prefix counts: every earlier
/// prefix equal to (current - k) closes one subarray summing to k.
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut counts = HashMap::from([(0, 1)]);
let mut prefix = 0;
let mut ans = 0;
for n in nums {
prefix += n;
ans += counts.get(&(prefix - k)).copied().unwrap_or(0);
*counts.entry(prefix).or_insert(0) += 1;
}
ans
}
/** LC 560. Count prefix sums: sum - k seen c times means c new subarrays. */
export function subarraySum(nums: number[], k: number): number {
const seen = new Map<number, number>([[0, 1]]);
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
count += seen.get(sum - k) ?? 0;
seen.set(sum, (seen.get(sum) ?? 0) + 1);
}
return count;
}
// LC 560. Count prefix sums seen so far; sum-k seen before means a subarray
// summing to k ends here. Seeding {0: 1} counts subarrays starting at index 0.
func subarraySum(nums []int, k int) int {
seen := map[int]int{0: 1}
sum, count := 0, 0
for _, x := range nums {
sum += x
count += seen[sum-k]
seen[sum]++
}
return count
}
// LC 560. Count prefix sums seen so far; sum - k seen before means a subarray
// summing to k ends here. Seeding [0: 1] counts subarrays starting at index 0.
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
var seen: [Int: Int] = [0: 1]
var sum = 0, count = 0
for x in nums {
sum += x
count += seen[sum - k, default: 0]
seen[sum, default: 0] += 1
}
return count
}
22. First Missing Positive
Hard · LC 41
Given an unsorted integer array, return the smallest missing positive integer in O(n) time and O(1) extra space. Treat the array itself as the hash table: repeatedly swap each value v in 1..n into slot v-1, then scan for the first index i whose value is not i+1 and return i+1. Each swap places one value at its final home, so the loop is linear, and values outside 1..n are simply left alone.
def first_missing_positive(nums: list[int]) -> int:
"""LC 41. First Missing Positive.
Cyclic placement: the answer lies in [1, n + 1], so swap each value
v in [1, n] into its home slot v - 1 until the current slot holds
either its rightful value or junk. The duplicate guard
(nums[v - 1] != v) stops infinite swapping. A second scan reports
the first slot whose value is wrong. O(n) time, O(1) space.
"""
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
// LC 41. Cyclic placement: swap each value v in [1, n] into slot v - 1,
// then the first slot holding the wrong value names the answer. O(n)/O(1).
int firstMissingPositive(vector<int> nums) {
int n = static_cast<int>(nums.size());
for (int i = 0; i < n; ++i)
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
swap(nums[i], nums[nums[i] - 1]);
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}
/// LC 41. Cyclic placement: swap each value v in 1..=n into slot v - 1
/// (don't advance until the landed value is settled), then the first slot
/// where nums[i] != i + 1 names the missing positive. O(n) time, O(1) space.
pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut i = 0;
while i < n {
let v = nums[i];
if v >= 1 && v <= n as i32 && nums[v as usize - 1] != v {
nums.swap(i, v as usize - 1);
} else {
i += 1;
}
}
for i in 0..n {
if nums[i] != i as i32 + 1 {
return i as i32 + 1;
}
}
n as i32 + 1
}
/** LC 41. Cyclic placement: swap each v in [1, n] to index v-1, then scan. */
export function firstMissingPositive(nums: number[]): number {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
const target = nums[i] - 1;
[nums[i], nums[target]] = [nums[target], nums[i]];
}
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
return n + 1;
}
// LC 41. Cyclic placement: swap each value v in [1, n] into slot v-1; the
// duplicate guard nums[v-1] != v stops infinite swapping. O(n) time, O(1) space.
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
}
}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
return n + 1
}
// LC 41. Cyclic placement: swap each value v in [1, n] into slot v - 1, then
// the first slot holding the wrong value names the answer. O(n)/O(1).
func firstMissingPositive(_ nums: [Int]) -> Int {
var nums = nums
let n = nums.count
for i in 0..<n {
while nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
nums.swapAt(i, nums[i] - 1)
}
}
for i in 0..<n where nums[i] != i + 1 { return i + 1 }
return n + 1
}