Top Interview 150

list.pop(i) shifts the whole tail left on every delete. Passes on LeetCode's small tests but is quadratic — fine at n <= 2000, times out well before LeetCode's 3 * 10^4 worst case.

Scan each run of equal values and copy min(run, 2) of them forward. Linear now, and generalizes to "keep at most k" by changing a single constant — but it needs lookahead to find each run's end, and the nested loops obscure what is really a one-condition filter.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer. One pass, one comparison per element, no lookahead — an online filter.

Walk each run of equal values, append min(run, 2) copies to a fresh vector, then copy the result back. Correct and linear, but the follow-up explicitly asks for O(1) extra memory.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer, so keep everything else and overwrite in place — no scratch vector needed.

Walk each run of equal values, push min(run, 2) copies onto a fresh Vec, then copy the result back. Correct and linear, but the follow-up explicitly asks for O(1) extra memory.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer, so keep everything else and overwrite in place — no scratch Vec needed.

Walk each run of equal values, push min(run, 2) copies onto a fresh array, then copy the result back. Correct and linear, but the follow-up explicitly asks for O(1) extra memory.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer, so keep everything else and overwrite in place — no scratch array needed.

Walk each run of equal values, append min(run, 2) copies to a fresh slice, then copy the result back. Correct and linear, but the follow-up explicitly asks for O(1) extra memory.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer, so keep everything else and overwrite in place — no scratch slice needed.

Walk each run of equal values, append min(run, 2) copies to a fresh array, then copy the result back. Correct and linear, but the follow-up explicitly asks for O(1) extra memory.

Sorted input means nums[i] is a 3rd-or-later copy exactly when it equals the element two slots behind the write pointer, so keep everything else and overwrite in place — no scratch array needed.

def removeDuplicates_pop(self, nums: List[int]) -> int:
    i = 2
    while i < len(nums):
        if nums[i] == nums[i - 2]:  # sorted => three equal in a row
            nums.pop(i)
        else:
            i += 1
    return len(nums)

def removeDuplicates_run_length(self, nums: List[int]) -> int:
    n = len(nums)
    write = read = 0
    while read < n:
        run_end = read
        while run_end < n and nums[run_end] == nums[read]:
            run_end += 1
        for _ in range(min(run_end - read, 2)):
            nums[write] = nums[read]
            write += 1
        read = run_end
    return write

def removeDuplicates(self, nums: List[int]) -> int:
    write = 0
    for num in nums:
        if write < 2 or num != nums[write - 2]:
            nums[write] = num
            write += 1
    return write

int removeDuplicatesExtraArray(vector<int>& nums) {
    vector<int> kept;
    size_t read = 0;
    while (read < nums.size()) {
        size_t runEnd = read;
        while (runEnd < nums.size() && nums[runEnd] == nums[read]) {
            ++runEnd;
        }
        for (size_t c = 0; c < min<size_t>(runEnd - read, 2); ++c) {
            kept.push_back(nums[read]);
        }
        read = runEnd;
    }
    copy(kept.begin(), kept.end(), nums.begin());
    return static_cast<int>(kept.size());
}

int removeDuplicates(vector<int>& nums) {
    int write = 0;
    for (int num : nums) {
        if (write < 2 || num != nums[write - 2]) {
            nums[write++] = num;
        }
    }
    return write;
}

pub fn remove_duplicates_extra_array(nums: &mut Vec<i32>) -> i32 {
    let mut kept: Vec<i32> = Vec::with_capacity(nums.len());
    let mut read = 0usize;
    while read < nums.len() {
        let mut run_end = read;
        while run_end < nums.len() && nums[run_end] == nums[read] {
            run_end += 1;
        }
        for _ in 0..(run_end - read).min(2) {
            kept.push(nums[read]);
        }
        read = run_end;
    }
    nums[..kept.len()].copy_from_slice(&kept);
    kept.len() as i32
}

pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    let mut write = 0usize;
    for i in 0..nums.len() {
        let num = nums[i];
        if write < 2 || num != nums[write - 2] {
            nums[write] = num;
            write += 1;
        }
    }
    write as i32
}

function removeDuplicatesExtraArray(nums: number[]): number {
    const kept: number[] = [];
    let read = 0;
    while (read < nums.length) {
        let runEnd = read;
        while (runEnd < nums.length && nums[runEnd] === nums[read]) {
            runEnd += 1;
        }
        for (let c = 0; c < Math.min(runEnd - read, 2); c += 1) {
            kept.push(nums[read]);
        }
        read = runEnd;
    }
    for (let i = 0; i < kept.length; i += 1) {
        nums[i] = kept[i];
    }
    return kept.length;
}

function removeDuplicates(nums: number[]): number {
    let write = 0;
    for (const num of nums) {
        if (write < 2 || num !== nums[write - 2]) {
            nums[write] = num;
            write += 1;
        }
    }
    return write;
}

func removeDuplicatesExtraArray(nums []int) int {
	kept := make([]int, 0, len(nums))
	read := 0
	for read < len(nums) {
		runEnd := read
		for runEnd < len(nums) && nums[runEnd] == nums[read] {
			runEnd++
		}
		take := runEnd - read
		if take > 2 {
			take = 2
		}
		for c := 0; c < take; c++ {
			kept = append(kept, nums[read])
		}
		read = runEnd
	}
	copy(nums, kept)
	return len(kept)
}

func removeDuplicates(nums []int) int {
	write := 0
	for _, num := range nums {
		if write < 2 || num != nums[write-2] {
			nums[write] = num
			write++
		}
	}
	return write
}

func removeDuplicatesExtraArray(_ nums: inout [Int]) -> Int {
    var kept: [Int] = []
    kept.reserveCapacity(nums.count)
    var read = 0
    while read < nums.count {
        var runEnd = read
        while runEnd < nums.count && nums[runEnd] == nums[read] {
            runEnd += 1
        }
        for _ in 0..<min(runEnd - read, 2) {
            kept.append(nums[read])
        }
        read = runEnd
    }
    nums.replaceSubrange(0..<kept.count, with: kept)
    return kept.count
}

func removeDuplicates(_ nums: inout [Int]) -> Int {
    var write = 0
    for num in nums {
        if write < 2 || num != nums[write - 2] {
            nums[write] = num
            write += 1
        }
    }
    return write
}

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

"h papers have >= h citations" is monotone in h (true for all values up to the answer, false after), so binary search the largest true h. Drops Approach 1's sorted copy and never mutates the input.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers >= h. Linear time — no comparison sort, no repeated counting passes.

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers with >= h citations reaches h. Beats the sort's n log n outright.

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers with >= h citations reaches h. Beats the sort's n log n outright.

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers with >= h citations reaches h. Beats the sort's n log n outright.

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers with >= h citations reaches h. Beats the sort's n log n outright.

After sorting high-to-low, position i (1-based) has i papers with >= citations[i-1] citations; the last position where the citation count still reaches i is the h-index. The sort dominates the cost.

h <= n, so any citation count above n acts exactly like n. Clamp every paper into buckets[0..n], then sweep h from n downward and return the first h where the running count of papers with >= h citations reaches h. Beats the sort's n log n outright.

def hIndex_sort(self, citations: List[int]) -> int:
    h = 0
    for i, c in enumerate(sorted(citations, reverse=True), start=1):
        if c >= i:
            h = i
        else:
            break
    return h

def hIndex_binary_search(self, citations: List[int]) -> int:
    lo, hi = 0, len(citations)
    while lo < hi:
        mid = (lo + hi + 1) // 2  # upper mid so the loop shrinks
        if sum(c >= mid for c in citations) >= mid:
            lo = mid
        else:
            hi = mid - 1
    return lo

def hIndex(self, citations: List[int]) -> int:
    n = len(citations)
    buckets = [0] * (n + 1)
    for c in citations:
        buckets[min(c, n)] += 1

    papers = 0  # papers with >= h citations
    for h in range(n, -1, -1):
        papers += buckets[h]
        if papers >= h:
            return h
    return 0  # unreachable: h = 0 always satisfies papers >= 0

int hIndexSort(vector<int>& citations) {
    sort(citations.begin(), citations.end(), greater<int>());
    int h = 0;
    for (int i = 0; i < static_cast<int>(citations.size()); ++i) {
        if (citations[i] >= i + 1) {
            h = i + 1;
        } else {
            break;
        }
    }
    return h;
}

int hIndex(vector<int>& citations) {
    int n = static_cast<int>(citations.size());
    vector<int> buckets(n + 1, 0);
    for (int c : citations) {
        ++buckets[min(c, n)];
    }
    int papers = 0;  // papers with >= h citations
    for (int h = n; h >= 0; --h) {
        papers += buckets[h];
        if (papers >= h) {
            return h;
        }
    }
    return 0;  // unreachable: h = 0 always satisfies papers >= 0
}

pub fn h_index_sort(citations: Vec<i32>) -> i32 {
    let mut citations = citations;
    citations.sort_unstable_by(|a, b| b.cmp(a));
    let mut h = 0;
    for (i, &c) in citations.iter().enumerate() {
        if c >= i as i32 + 1 {
            h = i as i32 + 1;
        } else {
            break;
        }
    }
    h
}

pub fn h_index(citations: Vec<i32>) -> i32 {
    let n = citations.len();
    let mut buckets = vec![0i32; n + 1];
    for c in citations {
        buckets[(c as usize).min(n)] += 1;
    }
    let mut papers = 0i32; // papers with >= h citations
    for h in (0..=n).rev() {
        papers += buckets[h];
        if papers >= h as i32 {
            return h as i32;
        }
    }
    0 // unreachable: h = 0 always satisfies papers >= 0
}

function hIndexSort(citations: number[]): number {
    const sorted = [...citations].sort((a, b) => b - a);
    let h = 0;
    for (let i = 0; i < sorted.length; i += 1) {
        if (sorted[i] >= i + 1) {
            h = i + 1;
        } else {
            break;
        }
    }
    return h;
}

function hIndex(citations: number[]): number {
    const n = citations.length;
    const buckets = new Array<number>(n + 1).fill(0);
    for (const c of citations) {
        buckets[Math.min(c, n)] += 1;
    }
    let papers = 0; // papers with >= h citations
    for (let h = n; h >= 0; h -= 1) {
        papers += buckets[h];
        if (papers >= h) {
            return h;
        }
    }
    return 0; // unreachable: h = 0 always satisfies papers >= 0
}

func hIndexSort(citations []int) int {
	sort.Sort(sort.Reverse(sort.IntSlice(citations)))
	h := 0
	for i, c := range citations {
		if c >= i+1 {
			h = i + 1
		} else {
			break
		}
	}
	return h
}

func hIndex(citations []int) int {
	n := len(citations)
	buckets := make([]int, n+1)
	for _, c := range citations {
		if c > n {
			c = n
		}
		buckets[c]++
	}
	papers := 0 // papers with >= h citations
	for h := n; h >= 0; h-- {
		papers += buckets[h]
		if papers >= h {
			return h
		}
	}
	return 0 // unreachable: h = 0 always satisfies papers >= 0
}

func hIndexSort(_ citations: [Int]) -> Int {
    let sorted = citations.sorted(by: >)
    var h = 0
    for (i, c) in sorted.enumerated() {
        if c >= i + 1 {
            h = i + 1
        } else {
            break
        }
    }
    return h
}

func hIndex(_ citations: [Int]) -> Int {
    let n = citations.count
    var buckets = [Int](repeating: 0, count: n + 1)
    for c in citations {
        buckets[min(c, n)] += 1
    }
    var papers = 0  // papers with >= h citations
    for h in stride(from: n, through: 0, by: -1) {
        papers += buckets[h]
        if papers >= h {
            return h
        }
    }
    return 0  // unreachable: h = 0 always satisfies papers >= 0
}

Correct, but misses the point of the problem: membership tests and deletions scan the whole array. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

A val->index map kills the scans. remove() just tombstones the slot; the array is compacted once dead slots reach half its length, so at least half of every array is alive and getRandom's rejection loop finishes in < 2 expected draws.

The array gives uniform O(1) random access; the map gives O(1) lookup. remove() swap-pops the victim with the last element so the array never has holes — no tombstones, no compaction spikes, no wasted slots.

Correct, but misses the point of the problem: membership tests and erase() scan and shift the whole vector. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

The vector gives uniform O(1) random access, the map gives O(1) lookup, and remove() swap-pops the victim with the last element so the vector never has holes — no scans, no tail shifts.

Correct, but misses the point of the problem: membership tests scan the whole Vec and Vec::remove shifts the tail. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

The Vec gives uniform O(1) random access, the map gives O(1) lookup, and remove() swap-pops the victim with the last element so the Vec never has holes — no scans, no tail shifts.

Correct, but misses the point of the problem: membership tests scan the whole array and splice() shifts the tail. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

The array gives uniform O(1) random access, the Map gives O(1) lookup, and remove() swap-pops the victim with the last element so the array never has holes — no scans, no tail shifts.

Correct, but misses the point of the problem: membership tests and deletions scan the whole slice. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

The slice gives uniform O(1) random access, the map gives O(1) lookup, and Remove swap-pops the victim with the last element so the slice never has holes — no scans, no tail shifts.

Correct, but misses the point of the problem: membership tests scan the whole array and remove(at:) shifts the tail. Fine at a few thousand ops; the judge's 2 * 10^5 ops would crawl.

The array gives uniform O(1) random access, the dictionary gives O(1) lookup, and remove() swap-pops the victim with the last element so the array never has holes — no scans, no tail shifts.

class RandomizedSetScan:
    """Same interface as RandomizedSet, no auxiliary index."""

    def __init__(self):
        self.values = []  # current members, unordered

    def insert(self, val: int) -> bool:
        if val in self.values:  # O(n) scan
            return False
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.values:  # O(n) scan
            return False
        self.values.remove(val)  # another scan plus a tail shift
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)

class RandomizedSetLazy:
    """Same interface as RandomizedSet, genuinely different bookkeeping."""

    _DEAD = object()  # sentinel; never equal to a stored int

    def __init__(self):
        self.values = []    # members interleaved with _DEAD tombstones
        self.index_of = {}  # val -> position in self.values
        self.dead = 0

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        self.values[self.index_of.pop(val)] = self._DEAD
        self.dead += 1
        if self.dead * 2 >= len(self.values):
            self._compact()
        return True

    def getRandom(self) -> int:
        while True:  # < 2 expected iterations: at least half the slots live
            val = random.choice(self.values)
            if val is not self._DEAD:
                return val

    def _compact(self):
        self.values = [v for v in self.values if v is not self._DEAD]
        self.index_of = {v: i for i, v in enumerate(self.values)}
        self.dead = 0

class RandomizedSet:
    """LeetCode 380. Insert Delete GetRandom O(1) — array + index map."""

    def __init__(self):
        self.values = []    # dense array of current members
        self.index_of = {}  # val -> position in self.values

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        idx = self.index_of.pop(val)
        last = self.values.pop()
        if idx < len(self.values):  # victim wasn't the last element
            self.values[idx] = last
            self.index_of[last] = idx
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)

class RandomizedSetScan {
    vector<int> values;  // current members, unordered
    mt19937 rng{381};

public:
    RandomizedSetScan() {}

    bool insert(int val) {
        if (find(values.begin(), values.end(), val) != values.end()) {
            return false;
        }
        values.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = find(values.begin(), values.end(), val);
        if (it == values.end()) {
            return false;
        }
        values.erase(it);  // shifts the whole tail left
        return true;
    }

    int getRandom() {
        uniform_int_distribution<int> dist(
            0, static_cast<int>(values.size()) - 1);
        return values[dist(rng)];
    }
};

class RandomizedSet {
    vector<int> values;               // dense array of current members
    unordered_map<int, int> indexOf;  // val -> position in values
    mt19937 rng{380};

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (indexOf.count(val)) {
            return false;
        }
        indexOf[val] = static_cast<int>(values.size());
        values.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = indexOf.find(val);
        if (it == indexOf.end()) {
            return false;
        }
        int idx = it->second;
        indexOf.erase(it);
        int last = values.back();
        values.pop_back();
        if (idx < static_cast<int>(values.size())) {  // victim wasn't last
            values[idx] = last;
            indexOf[last] = idx;
        }
        return true;
    }

    int getRandom() {
        uniform_int_distribution<int> dist(
            0, static_cast<int>(values.size()) - 1);
        return values[dist(rng)];
    }
};

struct RandomizedSetScan {
    values: Vec<i32>, // current members, unordered
    rng_state: Cell<u64>,
}

impl RandomizedSetScan {
    fn new() -> Self {
        RandomizedSetScan {
            values: Vec::new(),
            rng_state: Cell::new(0x0381_1234_5678_9abc),
        }
    }

    fn insert(&mut self, val: i32) -> bool {
        if self.values.contains(&val) {
            return false;
        }
        self.values.push(val);
        true
    }

    fn remove(&mut self, val: i32) -> bool {
        match self.values.iter().position(|&v| v == val) {
            None => false,
            Some(idx) => {
                self.values.remove(idx); // shifts the whole tail left
                true
            }
        }
    }

    fn get_random(&self) -> i32 {
        let x = xorshift64(&self.rng_state);
        self.values[(x % self.values.len() as u64) as usize]
    }
}

struct RandomizedSet {
    values: Vec<i32>,              // dense array of current members
    index_of: HashMap<i32, usize>, // val -> position in values
    rng_state: Cell<u64>,
}

impl RandomizedSet {
    fn new() -> Self {
        RandomizedSet {
            values: Vec::new(),
            index_of: HashMap::new(),
            rng_state: Cell::new(0x0380_1234_5678_9abc),
        }
    }

    fn insert(&mut self, val: i32) -> bool {
        if self.index_of.contains_key(&val) {
            return false;
        }
        self.index_of.insert(val, self.values.len());
        self.values.push(val);
        true
    }

    fn remove(&mut self, val: i32) -> bool {
        match self.index_of.remove(&val) {
            None => false,
            Some(idx) => {
                let last = self.values.pop().unwrap();
                if idx < self.values.len() {
                    // victim wasn't the last element: swap it in
                    self.values[idx] = last;
                    self.index_of.insert(last, idx);
                }
                true
            }
        }
    }

    fn get_random(&self) -> i32 {
        let x = xorshift64(&self.rng_state);
        self.values[(x % self.values.len() as u64) as usize]
    }
}

class RandomizedSetScan {
    private values: number[] = []; // current members, unordered

    insert(val: number): boolean {
        if (this.values.includes(val)) { // O(n) scan
            return false;
        }
        this.values.push(val);
        return true;
    }

    remove(val: number): boolean {
        const idx = this.values.indexOf(val); // O(n) scan
        if (idx < 0) {
            return false;
        }
        this.values.splice(idx, 1); // shifts the whole tail left
        return true;
    }

    getRandom(): number {
        return this.values[Math.floor(Math.random() * this.values.length)];
    }
}

class RandomizedSet {
    private values: number[] = [];              // dense array of current members
    private indexOf: Map<number, number> = new Map(); // val -> position in values

    insert(val: number): boolean {
        if (this.indexOf.has(val)) {
            return false;
        }
        this.indexOf.set(val, this.values.length);
        this.values.push(val);
        return true;
    }

    remove(val: number): boolean {
        const idx = this.indexOf.get(val);
        if (idx === undefined) {
            return false;
        }
        this.indexOf.delete(val);
        const last = this.values.pop() as number;
        if (idx < this.values.length) { // victim wasn't the last element
            this.values[idx] = last;
            this.indexOf.set(last, idx);
        }
        return true;
    }

    getRandom(): number {
        return this.values[Math.floor(Math.random() * this.values.length)];
    }
}

type RandomizedSetScan struct {
	values []int // current members, unordered
	rng    *rand.Rand
}

func ConstructorScan() RandomizedSetScan {
	return RandomizedSetScan{rng: rand.New(rand.NewSource(381))}
}

func (s *RandomizedSetScan) scanFor(val int) int {
	for i, v := range s.values {
		if v == val {
			return i
		}
	}
	return -1
}

func (s *RandomizedSetScan) Insert(val int) bool {
	if s.scanFor(val) >= 0 {
		return false
	}
	s.values = append(s.values, val)
	return true
}

func (s *RandomizedSetScan) Remove(val int) bool {
	idx := s.scanFor(val)
	if idx < 0 {
		return false
	}
	s.values = append(s.values[:idx], s.values[idx+1:]...) // shifts the tail
	return true
}

func (s *RandomizedSetScan) GetRandom() int {
	return s.values[s.rng.Intn(len(s.values))]
}

type RandomizedSet struct {
	values  []int       // dense array of current members
	indexOf map[int]int // val -> position in values
	rng     *rand.Rand
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		indexOf: make(map[int]int),
		rng:     rand.New(rand.NewSource(380)),
	}
}

func (s *RandomizedSet) Insert(val int) bool {
	if _, ok := s.indexOf[val]; ok {
		return false
	}
	s.indexOf[val] = len(s.values)
	s.values = append(s.values, val)
	return true
}

func (s *RandomizedSet) Remove(val int) bool {
	idx, ok := s.indexOf[val]
	if !ok {
		return false
	}
	delete(s.indexOf, val)
	last := s.values[len(s.values)-1]
	s.values = s.values[:len(s.values)-1]
	if idx < len(s.values) { // victim wasn't the last element
		s.values[idx] = last
		s.indexOf[last] = idx
	}
	return true
}

func (s *RandomizedSet) GetRandom() int {
	return s.values[s.rng.Intn(len(s.values))]
}

class RandomizedSetScan {
    private var values: [Int] = []  // current members, unordered
    private var rng = SplitMix64(seed: 381)

    init() {}

    func insert(_ val: Int) -> Bool {
        if values.contains(val) {  // O(n) scan
            return false
        }
        values.append(val)
        return true
    }

    func remove(_ val: Int) -> Bool {
        guard let idx = values.firstIndex(of: val) else {  // O(n) scan
            return false
        }
        values.remove(at: idx)  // shifts the whole tail left
        return true
    }

    func getRandom() -> Int {
        return values[Int.random(in: 0..<values.count, using: &rng)]
    }
}

class RandomizedSet {
    private var values: [Int] = []       // dense array of current members
    private var indexOf: [Int: Int] = [:] // val -> position in values
    private var rng = SplitMix64(seed: 380)

    init() {}

    func insert(_ val: Int) -> Bool {
        if indexOf[val] != nil {
            return false
        }
        indexOf[val] = values.count
        values.append(val)
        return true
    }

    func remove(_ val: Int) -> Bool {
        guard let idx = indexOf[val] else {
            return false
        }
        indexOf[val] = nil
        let last = values.removeLast()
        if idx < values.count {  // victim wasn't the last element
            values[idx] = last
            indexOf[last] = idx
        }
        return true
    }

    func getRandom() -> Int {
        return values[Int.random(in: 0..<values.count, using: &rng)]
    }
}

Mirrors how you'd write a numeral by hand: keep subtracting the largest value that still fits, one symbol at a time. Instructive, but re-tests the same table entry once per emitted symbol.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

For each entry take as many copies as fit (divmod), then move on. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

Peel copies of each entry from largest to smallest. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

Peel copies of each entry from largest to smallest. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

Peel copies of each entry from largest to smallest. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

Peel copies of each entry from largest to smallest. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

Each decimal digit maps independently to a fixed Roman chunk, so precompute all chunks and concatenate thousands/hundreds/tens/ones. No loops at all — but the 31 hardcoded chunks only cover 1..3999 and hide the greedy rule that generates them.

Peel copies of each entry from largest to smallest. One pass over 13 entries, no hardcoded chunk tables, and it extends past 3999 by just adding larger entries.

def intToRoman_subtraction(self, num: int) -> str:
    parts = []
    for value, symbol in self._TABLE:
        while num >= value:
            num -= value
            parts.append(symbol)
    return "".join(parts)

def intToRoman_digit_lookup(self, num: int) -> str:
    thousands = ["", "M", "MM", "MMM"]
    hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    return (thousands[num // 1000] + hundreds[num // 100 % 10]
            + tens[num // 10 % 10] + ones[num % 10])

def intToRoman(self, num: int) -> str:
    parts = []
    for value, symbol in self._TABLE:
        if num == 0:
            break
        count, num = divmod(num, value)
        parts.append(symbol * count)
    return "".join(parts)

string intToRomanDigitLookup(int num) {
    static const char* const kThousands[] = {"", "M", "MM", "MMM"};
    static const char* const kHundreds[] = {
        "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    static const char* const kTens[] = {
        "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    static const char* const kOnes[] = {
        "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return string(kThousands[num / 1000]) + kHundreds[num / 100 % 10] +
           kTens[num / 10 % 10] + kOnes[num % 10];
}

string intToRoman(int num) {
    static const pair<int, const char*> kTable[] = {
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
        {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
        {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"},
    };
    string out;
    for (const auto& [value, symbol] : kTable) {
        while (num >= value) {
            num -= value;
            out += symbol;
        }
    }
    return out;
}

pub fn int_to_roman_digit_lookup(num: i32) -> String {
    const THOUSANDS: [&str; 4] = ["", "M", "MM", "MMM"];
    const HUNDREDS: [&str; 10] = [
        "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM",
    ];
    const TENS: [&str; 10] = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    const ONES: [&str; 10] = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    let num = num as usize;
    format!(
        "{}{}{}{}",
        THOUSANDS[num / 1000],
        HUNDREDS[num / 100 % 10],
        TENS[num / 10 % 10],
        ONES[num % 10]
    )
}

pub fn int_to_roman(num: i32) -> String {
    const TABLE: [(i32, &str); 13] = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
        (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I"),
    ];
    let mut num = num;
    let mut out = String::new();
    for (value, symbol) in TABLE {
        while num >= value {
            num -= value;
            out.push_str(symbol);
        }
    }
    out
}

function intToRomanDigitLookup(num: number): string {
    const thousands = ["", "M", "MM", "MMM"];
    const hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    const tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    const ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    return (
        thousands[Math.floor(num / 1000)] +
        hundreds[Math.floor(num / 100) % 10] +
        tens[Math.floor(num / 10) % 10] +
        ones[num % 10]
    );
}

function intToRoman(num: number): string {
    const table: Array<[number, string]> = [
        [1000, "M"], [900, "CM"], [500, "D"], [400, "CD"],
        [100, "C"], [90, "XC"], [50, "L"], [40, "XL"],
        [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"],
    ];
    let out = "";
    for (const [value, symbol] of table) {
        while (num >= value) {
            num -= value;
            out += symbol;
        }
    }
    return out;
}

func intToRomanDigitLookup(num int) string {
	thousands := []string{"", "M", "MM", "MMM"}
	hundreds := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
	tens := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
	ones := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
	return thousands[num/1000] + hundreds[num/100%10] + tens[num/10%10] + ones[num%10]
}

func intToRoman(num int) string {
	values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	var out strings.Builder
	for i, value := range values {
		for num >= value {
			num -= value
			out.WriteString(symbols[i])
		}
	}
	return out.String()
}

func intToRomanDigitLookup(_ num: Int) -> String {
    let thousands = ["", "M", "MM", "MMM"]
    let hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    let tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    let ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    return thousands[num / 1000] + hundreds[num / 100 % 10]
        + tens[num / 10 % 10] + ones[num % 10]
}

func intToRoman(_ num: Int) -> String {
    let table: [(value: Int, symbol: String)] = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
        (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I"),
    ]
    var num = num
    var out = ""
    for (value, symbol) in table {
        while num >= value {
            num -= value
            out += symbol
        }
    }
    return out
}

str.split() with no argument trims the ends and collapses runs of spaces, so the last token is exactly the last word. Costs a full token list just to look at one entry.

Track the word in progress; remember its length on every non-space char. Drops Approach 1's token list, but still walks the whole string even when only the tail matters.

Skip trailing spaces from the end, then count characters until the next space. Never touches the front of a long string.

Let a stringstream do the space handling: extraction skips runs of whitespace, so the last extracted token is the last word. Copies the whole string into a stream just to look at one token.

Skip trailing spaces from the end, then count characters until the next space. No copies, and never touches the front of a long string.

split_whitespace trims the ends and collapses runs of spaces, so the last token is exactly the last word. Materializing every token in a Vec just to read one entry is the naive part; the iterator could stream, but this is the version people write first.

Skip trailing spaces from the end, then count characters until the next space. No allocations, and never touches the front of a long string.

Split on single spaces and filter out the empty pieces that leading/trailing/repeated spaces produce; the last token is exactly the last word. Builds the whole token array to look at one entry.

Skip trailing spaces from the end, then count characters until the next space. No allocations, and never touches the front of a long string.

strings.Fields trims the ends and collapses runs of spaces, so the last token is exactly the last word. Allocates the whole token slice just to look at one entry.

Skip trailing spaces from the end, then count characters until the next space. No allocations, and never touches the front of a long string.

split(separator:) drops the empty pieces that leading/trailing/ repeated spaces would produce, so the last token is exactly the last word. Builds the whole token array just to look at one entry.

Skip trailing spaces from the end, then count characters until the next space. No token list; after the one-time array conversion (Swift strings lack integer indexing) only the tail is touched.

def lengthOfLastWord_split(self, s: str) -> int:
    return len(s.split()[-1])

def lengthOfLastWord_forward(self, s: str) -> int:
    last = current = 0
    for char in s:
        if char == ' ':
            current = 0
        else:
            current += 1
            last = current
    return last

def lengthOfLastWord(self, s: str) -> int:
    i = len(s) - 1
    while i >= 0 and s[i] == ' ':
        i -= 1
    length = 0
    while i >= 0 and s[i] != ' ':
        length += 1
        i -= 1
    return length

int lengthOfLastWordSplit(string s) {
    istringstream in(s);
    string word, last;
    while (in >> word) {
        last = word;
    }
    return static_cast<int>(last.size());
}

int lengthOfLastWord(string s) {
    int i = static_cast<int>(s.size()) - 1;
    while (i >= 0 && s[i] == ' ') {
        --i;
    }
    int length = 0;
    while (i >= 0 && s[i] != ' ') {
        ++length;
        --i;
    }
    return length;
}

pub fn length_of_last_word_split(s: String) -> i32 {
    let words: Vec<&str> = s.split_whitespace().collect();
    words.last().map_or(0, |w| w.len() as i32)
}

pub fn length_of_last_word(s: String) -> i32 {
    let bytes = s.as_bytes();
    let mut i = bytes.len();
    while i > 0 && bytes[i - 1] == b' ' {
        i -= 1;
    }
    let mut length = 0;
    while i > 0 && bytes[i - 1] != b' ' {
        length += 1;
        i -= 1;
    }
    length
}

function lengthOfLastWordSplit(s: string): number {
    const words = s.split(" ").filter((word) => word.length > 0);
    return words[words.length - 1].length;
}

function lengthOfLastWord(s: string): number {
    let i = s.length - 1;
    while (i >= 0 && s[i] === " ") {
        i--;
    }
    let length = 0;
    while (i >= 0 && s[i] !== " ") {
        length++;
        i--;
    }
    return length;
}

func lengthOfLastWordSplit(s string) int {
	words := strings.Fields(s)
	return len(words[len(words)-1])
}

func lengthOfLastWord(s string) int {
	i := len(s) - 1
	for i >= 0 && s[i] == ' ' {
		i--
	}
	length := 0
	for i >= 0 && s[i] != ' ' {
		length++
		i--
	}
	return length
}

func lengthOfLastWordSplit(_ s: String) -> Int {
    let words = s.split(separator: " ")
    return words.last?.count ?? 0
}

func lengthOfLastWord(_ s: String) -> Int {
    let chars = Array(s)
    var i = chars.count - 1
    while i >= 0 && chars[i] == " " {
        i -= 1
    }
    var length = 0
    while i >= 0 && chars[i] != " " {
        length += 1
        i -= 1
    }
    return length
}

Collect each word and prepend it to the answer built so far. Every prepend copies the whole result, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful much beyond that.

The classic C/C++ in-place trick: reverse the whole char array so the words land in the right order (letters backwards), then reverse each word back while compacting spaces with a write pointer. Linear time — no copy per word like Approach 1 — at the price of extra passes.

Walk right-to-left; for each word locate its end, then its start, and slice it out. One backward pass instead of Approach 2's reverse-then-re-reverse, with no character-by-character rebuilding.

str.split() with no argument trims the ends and collapses runs of spaces, doing all the cleanup for free; then it is just a reversed join. Any answer must be O(n) space in Python (strings are immutable).

Tokenize with a stringstream and prepend each word to the answer built so far. Every prepend copies the whole result, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful beyond.

Collect the words, reverse the vector, join with single spaces. Linear — each character is copied a constant number of times — but it buffers every word in a second container next to the input.

Reverse the whole string so the words land in the right order (letters backwards), then reverse each word back while compacting extra spaces with a write pointer. No auxiliary buffers at all.

Prepend each word to the answer built so far. Every prepend rebuilds the whole result string, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful much beyond.

split_whitespace trims the ends and collapses runs of spaces, doing all the cleanup for free; then it is just a reversed join. Each byte is copied a constant number of times.

Grow each word char by char and prepend it to the answer built so far. Every prepend copies the whole result, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful much beyond that.

Split on single spaces, filter out the empty pieces that leading/trailing/repeated spaces produce, then reverse and join with single spaces. Each character is copied a constant number of times.

Grow each word byte by byte and prepend it to the answer built so far. Both the append and the prepend copy their whole operand, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful much beyond that.

strings.Fields trims the ends and collapses runs of spaces, doing all the cleanup for free; then reverse the slice in place and join with single spaces. Each byte is copied a constant number of times.

Prepend each word to the answer built so far. Every prepend copies the whole result string, so many short words go quadratic — fine at LeetCode's n <= 10^4, painful much beyond that.

split(separator:) drops the empty pieces that leading/trailing/ repeated spaces would produce, doing all the cleanup for free; then it is just a reversed join with single spaces. Each character is copied a constant number of times.

def reverseWords_concat(self, s: str) -> str:
    result = ""
    word = ""
    for char in s + " ":
        if char != ' ':
            word += char
        elif word:
            result = word if not result else word + " " + result
            word = ""
    return result

def reverseWords_reverse_all(self, s: str) -> str:
    chars = list(s)[::-1]
    n = len(chars)
    write = read = 0
    while read < n:
        while read < n and chars[read] == ' ':
            read += 1
        if read == n:
            break
        if write > 0:           # single separator between words
            chars[write] = ' '
            write += 1
        start = write
        while read < n and chars[read] != ' ':
            chars[write] = chars[read]
            write += 1
            read += 1
        chars[start:write] = chars[start:write][::-1]
    return "".join(chars[:write])

def reverseWords_two_pointer(self, s: str) -> str:
    words = []
    i = len(s) - 1
    while i >= 0:
        while i >= 0 and s[i] == ' ':
            i -= 1
        if i < 0:
            break
        end = i
        while i >= 0 and s[i] != ' ':
            i -= 1
        words.append(s[i + 1:end + 1])
    return " ".join(words)

def reverseWords(self, s: str) -> str:
    return " ".join(reversed(s.split()))

string reverseWordsConcat(string s) {
    istringstream in(s);
    string word, result;
    while (in >> word) {
        result = result.empty() ? word : word + " " + result;
    }
    return result;
}

string reverseWordsSplit(string s) {
    istringstream in(s);
    vector<string> words;
    string word;
    while (in >> word) {
        words.push_back(word);
    }
    reverse(words.begin(), words.end());
    string out;
    out.reserve(s.size());
    for (size_t i = 0; i < words.size(); ++i) {
        if (i > 0) {
            out += ' ';
        }
        out += words[i];
    }
    return out;
}

string reverseWords(string s) {
    reverse(s.begin(), s.end());
    const int n = static_cast<int>(s.size());
    int write = 0;
    for (int read = 0; read < n;) {
        while (read < n && s[read] == ' ') {
            ++read;
        }
        if (read == n) {
            break;
        }
        if (write > 0) {  // single separator between words
            s[write++] = ' ';
        }
        const int start = write;
        while (read < n && s[read] != ' ') {
            s[write++] = s[read++];
        }
        reverse(s.begin() + start, s.begin() + write);
    }
    s.resize(write);
    return s;
}

pub fn reverse_words_concat(s: String) -> String {
    let mut result = String::new();
    for word in s.split_whitespace() {
        if result.is_empty() {
            result = word.to_string();
        } else {
            result = format!("{} {}", word, result);
        }
    }
    result
}

pub fn reverse_words(s: String) -> String {
    s.split_whitespace().rev().collect::<Vec<_>>().join(" ")
}

function reverseWordsConcat(s: string): string {
    let result = "";
    let word = "";
    for (const ch of s + " ") {
        if (ch !== " ") {
            word += ch;
        } else if (word.length > 0) {
            result = result.length === 0 ? word : word + " " + result;
            word = "";
        }
    }
    return result;
}

function reverseWords(s: string): string {
    return s
        .split(" ")
        .filter((word) => word.length > 0)
        .reverse()
        .join(" ");
}

func reverseWordsConcat(s string) string {
	result := ""
	word := ""
	for i := 0; i <= len(s); i++ {
		if i < len(s) && s[i] != ' ' {
			word += string(s[i])
		} else if word != "" {
			if result == "" {
				result = word
			} else {
				result = word + " " + result
			}
			word = ""
		}
	}
	return result
}

func reverseWords(s string) string {
	words := strings.Fields(s)
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}
	return strings.Join(words, " ")
}

func reverseWordsConcat(_ s: String) -> String {
    var result = ""
    for word in s.split(separator: " ") {
        result = result.isEmpty ? String(word) : String(word) + " " + result
    }
    return result
}

func reverseWords(_ s: String) -> String {
    return s.split(separator: " ").reversed().joined(separator: " ")
}

Walk an actual numRows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

Row 0 and the last row take one char per cycle; each middle row also takes the up-stroke char at j + cycle - 2*row. Kills the grid: emits the answer in order with no storage beyond the output, at the cost of numRows passes over s and fiddly index arithmetic.

For char i, p = i % cycle is its position in the cycle; positions past the bottom fold back up to row cycle - p. One sequential pass over s (better locality than Approach 2's jumps), no direction state to maintain.

Drop each char into its row, bouncing off the top and bottom rows. Same single pass as Approach 3 with the modular arithmetic replaced by a direction flag — nothing to derive, nothing to misremember. numRows == 1 has nowhere to bounce (the flip logic would walk off the end), so it is returned as-is up front.

Walk an actual numRows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

The column never mattered — only the row order did. Drop each char into its row while bouncing off the top and bottom rows, then concatenate the rows. numRows == 1 has nowhere to bounce, so it is returned as-is.

Walk an actual num_rows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

The column never mattered — only the row order did. Drop each char into its row while bouncing off the top and bottom rows, then concatenate the rows. num_rows == 1 has nowhere to bounce, so it is returned as-is.

Walk an actual numRows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

The column never mattered — only the row order did. Drop each char into its row while bouncing off the top and bottom rows, then concatenate the rows. numRows === 1 has nowhere to bounce, so it is returned as-is.

Walk an actual numRows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

The column never mattered — only the row order did. Drop each char into its row while bouncing off the top and bottom rows, then concatenate the rows. numRows == 1 has nowhere to bounce, so it is returned as-is.

Walk an actual numRows x n grid — down a column, then diagonally up-right — and read the non-empty cells row by row. Instructive, but almost every cell is wasted padding.

The column never mattered — only the row order did. Drop each char into its row while bouncing off the top and bottom rows, then concatenate the rows. numRows == 1 has nowhere to bounce, so it is returned as-is.

def convert_grid(self, s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    n = len(s)
    grid = [[''] * n for _ in range(numRows)]
    row = col = 0
    down = True
    for char in s:
        grid[row][col] = char
        if down:
            if row + 1 == numRows:
                down = False
                row -= 1
                col += 1
            else:
                row += 1
        elif row == 0:
            down = True
            row += 1
        else:
            row -= 1
            col += 1
    return "".join(char for r in grid for char in r if char)

def convert_jump(self, s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    n = len(s)
    cycle = 2 * numRows - 2
    out = []
    for row in range(numRows):
        for j in range(row, n, cycle):
            out.append(s[j])
            up = j + cycle - 2 * row
            if 0 < row < numRows - 1 and up < n:
                out.append(s[up])
    return "".join(out)

def convert_fold(self, s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    cycle = 2 * numRows - 2
    rows = [[] for _ in range(numRows)]
    for i, char in enumerate(s):
        p = i % cycle
        rows[p if p < numRows else cycle - p].append(char)
    return "".join("".join(r) for r in rows)

def convert(self, s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    rows = [[] for _ in range(numRows)]
    row, step = 0, 1
    for char in s:
        rows[row].append(char)
        if row == 0:
            step = 1
        elif row == numRows - 1:
            step = -1
        row += step
    return "".join("".join(r) for r in rows)

string convertGrid(string s, int numRows) {
    if (numRows == 1) {
        return s;
    }
    const int n = static_cast<int>(s.size());
    vector<vector<char>> grid(numRows, vector<char>(n, '\0'));
    int row = 0, col = 0;
    bool down = true;
    for (char c : s) {
        grid[row][col] = c;
        if (down) {
            if (row + 1 == numRows) {
                down = false;
                --row;
                ++col;
            } else {
                ++row;
            }
        } else if (row == 0) {
            down = true;
            ++row;
        } else {
            --row;
            ++col;
        }
    }
    string out;
    out.reserve(s.size());
    for (const auto& r : grid) {
        for (char c : r) {
            if (c != '\0') {
                out += c;
            }
        }
    }
    return out;
}

string convert(string s, int numRows) {
    if (numRows == 1) {
        return s;
    }
    vector<string> rows(numRows);
    int row = 0, step = 1;
    for (char c : s) {
        rows[row] += c;
        if (row == 0) {
            step = 1;
        } else if (row == numRows - 1) {
            step = -1;
        }
        row += step;
    }
    string out;
    out.reserve(s.size());
    for (const string& r : rows) {
        out += r;
    }
    return out;
}

pub fn convert_grid(s: String, num_rows: i32) -> String {
    let num_rows = num_rows as usize;
    if num_rows == 1 {
        return s;
    }
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut grid = vec![vec![0u8; n]; num_rows];
    let (mut row, mut col) = (0usize, 0usize);
    let mut down = true;
    for &b in bytes {
        grid[row][col] = b;
        if down {
            if row + 1 == num_rows {
                down = false;
                row -= 1;
                col += 1;
            } else {
                row += 1;
            }
        } else if row == 0 {
            down = true;
            row += 1;
        } else {
            row -= 1;
            col += 1;
        }
    }
    let mut out = Vec::with_capacity(n);
    for r in &grid {
        for &b in r {
            if b != 0 {
                out.push(b);
            }
        }
    }
    String::from_utf8(out).unwrap()
}

pub fn convert(s: String, num_rows: i32) -> String {
    let num_rows = num_rows as usize;
    if num_rows == 1 {
        return s;
    }
    let mut rows = vec![String::new(); num_rows];
    let mut row = 0usize;
    let mut down = true;
    for c in s.chars() {
        rows[row].push(c);
        if row == 0 {
            down = true;
        } else if row == num_rows - 1 {
            down = false;
        }
        if down {
            row += 1;
        } else {
            row -= 1;
        }
    }
    rows.concat()
}

function convertGrid(s: string, numRows: number): string {
    if (numRows === 1) {
        return s;
    }
    const n = s.length;
    const grid: string[][] = Array.from({ length: numRows }, () =>
        new Array<string>(n).fill(""),
    );
    let row = 0;
    let col = 0;
    let down = true;
    for (const ch of s) {
        grid[row][col] = ch;
        if (down) {
            if (row + 1 === numRows) {
                down = false;
                row--;
                col++;
            } else {
                row++;
            }
        } else if (row === 0) {
            down = true;
            row++;
        } else {
            row--;
            col++;
        }
    }
    let out = "";
    for (const r of grid) {
        for (const ch of r) {
            out += ch;
        }
    }
    return out;
}

function convert(s: string, numRows: number): string {
    if (numRows === 1) {
        return s;
    }
    const rows: string[] = new Array(numRows).fill("");
    let row = 0;
    let step = 1;
    for (const ch of s) {
        rows[row] += ch;
        if (row === 0) {
            step = 1;
        } else if (row === numRows - 1) {
            step = -1;
        }
        row += step;
    }
    return rows.join("");
}

func convertGrid(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	n := len(s)
	grid := make([][]byte, numRows)
	for r := range grid {
		grid[r] = make([]byte, n)
	}
	row, col := 0, 0
	down := true
	for i := 0; i < n; i++ {
		grid[row][col] = s[i]
		if down {
			if row+1 == numRows {
				down = false
				row--
				col++
			} else {
				row++
			}
		} else if row == 0 {
			down = true
			row++
		} else {
			row--
			col++
		}
	}
	out := make([]byte, 0, n)
	for _, r := range grid {
		for _, b := range r {
			if b != 0 {
				out = append(out, b)
			}
		}
	}
	return string(out)
}

func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	rows := make([][]byte, numRows)
	row, step := 0, 1
	for i := 0; i < len(s); i++ {
		rows[row] = append(rows[row], s[i])
		if row == 0 {
			step = 1
		} else if row == numRows-1 {
			step = -1
		}
		row += step
	}
	out := make([]byte, 0, len(s))
	for _, r := range rows {
		out = append(out, r...)
	}
	return string(out)
}

func convertGrid(_ s: String, _ numRows: Int) -> String {
    if numRows == 1 {
        return s
    }
    let chars = Array(s)
    let n = chars.count
    var grid = Array(repeating: [Character?](repeating: nil, count: n), count: numRows)
    var row = 0
    var col = 0
    var down = true
    for ch in chars {
        grid[row][col] = ch
        if down {
            if row + 1 == numRows {
                down = false
                row -= 1
                col += 1
            } else {
                row += 1
            }
        } else if row == 0 {
            down = true
            row += 1
        } else {
            row -= 1
            col += 1
        }
    }
    var out = ""
    out.reserveCapacity(n)
    for r in grid {
        for case let ch? in r {
            out.append(ch)
        }
    }
    return out
}

func convert(_ s: String, _ numRows: Int) -> String {
    if numRows == 1 {
        return s
    }
    var rows = [String](repeating: "", count: numRows)
    var row = 0
    var step = 1
    for ch in s {
        rows[row].append(ch)
        if row == 0 {
            step = 1
        } else if row == numRows - 1 {
            step = -1
        }
        row += step
    }
    return rows.joined()
}

Try every alignment and compare char by char, bailing on the first mismatch. The worst case needs pathological inputs ("aaaa..." vs "aaab"); for interview-sized strings this is the clearest start. A needle longer than the haystack yields an empty range -> -1.

What you would write outside an interview: CPython uses a tuned Crochemore-Perrin two-way search under the hood, so this is already linear. The catch is that the algorithm stays a black box — the next rung builds the linear-time machinery by hand.

Precompute the longest-proper-prefix-that-is-also-a-suffix table for the needle, then scan the haystack once; on a mismatch the needle pointer falls back via the table and no haystack char is re-read.

The first thing most people write: carve out the m-char substring at every start and compare it to the needle. Correct, but every probe allocates a fresh copy just to throw it away.

Same alignments, but compare in place char by char and bail on the first mismatch — no allocation per probe. A needle longer than the haystack makes the loop bound negative, so no alignment is tried and we return -1.

Try every start index — even the tail ones where the needle can no longer fit — and compare byte by byte behind an explicit bounds check. The wasted tail probes and the per-step bound test are what the next rung trims away.

Reject a too-long needle up front (which also keeps the n - m subtraction from underflowing), then compare the m-byte window at each remaining alignment with slice equality — a memcmp under the hood, with no per-step bounds checks.

The first thing most people write: carve out the m-char slice at every start and compare it to the needle. Correct, but every probe builds a fresh string just to throw it away.

Same alignments, but compare in place char by char and bail on the first mismatch — no slice per probe. A needle longer than the haystack leaves no alignment to try, so the loop never runs and we return -1.

Try every start index — even the tail ones where the needle can no longer fit — and compare byte by byte behind an explicit bounds check. The wasted tail probes and the per-step bound test are what the next rung trims away.

Bound the loop so only alignments where the needle fits are tried; the inner compare then needs no bounds check and bails on the first mismatch. A needle longer than the haystack leaves no alignment to try, so the loop never runs and we return -1.

The first thing most people write: copy out the m-char window at every start and compare whole arrays. Correct, but every probe materializes a fresh array just to throw it away.

Same alignments, but compare in place char by char and bail on the first mismatch — no copy per probe. A needle longer than the haystack is rejected up front (it also keeps the range bound non-negative).

def strStr_sliding(self, haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

def strStr_find(self, haystack: str, needle: str) -> int:
    return haystack.find(needle)

def strStr(self, haystack: str, needle: str) -> int:
    m = len(needle)
    if m == 0:
        return 0

    # lps[i] = length of the longest proper prefix of needle[:i+1]
    # that is also a suffix of it.
    lps = [0] * m
    length = 0
    for i in range(1, m):
        while length and needle[i] != needle[length]:
            length = lps[length - 1]
        if needle[i] == needle[length]:
            length += 1
        lps[i] = length

    j = 0
    for i, char in enumerate(haystack):
        while j and char != needle[j]:
            j = lps[j - 1]
        if char == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

int strStrSubstr(string haystack, string needle) {
    const int n = static_cast<int>(haystack.size());
    const int m = static_cast<int>(needle.size());
    for (int start = 0; start + m <= n; ++start) {
        if (haystack.substr(start, m) == needle) {
            return start;
        }
    }
    return -1;
}

int strStr(string haystack, string needle) {
    const int n = static_cast<int>(haystack.size());
    const int m = static_cast<int>(needle.size());
    for (int start = 0; start + m <= n; ++start) {
        int j = 0;
        while (j < m && haystack[start + j] == needle[j]) {
            ++j;
        }
        if (j == m) {
            return start;
        }
    }
    return -1;
}

pub fn str_str_nested(haystack: String, needle: String) -> i32 {
    let h = haystack.as_bytes();
    let nd = needle.as_bytes();
    if nd.is_empty() {
        return 0;
    }
    for start in 0..h.len() {
        let mut j = 0;
        while start + j < h.len() && j < nd.len() && h[start + j] == nd[j] {
            j += 1;
        }
        if j == nd.len() {
            return start as i32;
        }
    }
    -1
}

pub fn str_str(haystack: String, needle: String) -> i32 {
    let h = haystack.as_bytes();
    let nd = needle.as_bytes();
    let (n, m) = (h.len(), nd.len());
    if m > n {
        return -1;
    }
    for start in 0..=(n - m) {
        if &h[start..start + m] == nd {
            return start as i32;
        }
    }
    -1
}

function strStrSlice(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    for (let start = 0; start + m <= n; start++) {
        if (haystack.slice(start, start + m) === needle) {
            return start;
        }
    }
    return -1;
}

function strStr(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    for (let start = 0; start + m <= n; start++) {
        let j = 0;
        while (j < m && haystack[start + j] === needle[j]) {
            j++;
        }
        if (j === m) {
            return start;
        }
    }
    return -1;
}

func strStrNested(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	if m == 0 {
		return 0
	}
	for start := 0; start < n; start++ {
		j := 0
		for start+j < n && j < m && haystack[start+j] == needle[j] {
			j++
		}
		if j == m {
			return start
		}
	}
	return -1
}

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	for start := 0; start+m <= n; start++ {
		j := 0
		for j < m && haystack[start+j] == needle[j] {
			j++
		}
		if j == m {
			return start
		}
	}
	return -1
}

func strStrSlice(_ haystack: String, _ needle: String) -> Int {
    let h = Array(haystack)
    let nd = Array(needle)
    if nd.count > h.count {
        return -1
    }
    for start in 0...(h.count - nd.count) {
        if Array(h[start..<start + nd.count]) == nd {
            return start
        }
    }
    return -1
}

func strStr(_ haystack: String, _ needle: String) -> Int {
    let h = Array(haystack)
    let nd = Array(needle)
    if nd.count > h.count {
        return -1
    }
    for start in 0...(h.count - nd.count) {
        var j = 0
        while j < nd.count && h[start + j] == nd[j] {
            j += 1
        }
        if j == nd.count {
            return start
        }
    }
    return -1
}