陣列

# python
# itertools.islice(seq, [start,] stop [, step]) slices any iterator without building a list
import itertools

x = itertools.islice(range(10), 0, 9, 2)
print(list(x))   # -> [0, 2, 4, 6, 8]

y = itertools.islice(range(10), 0, 10, 3)
print(list(y))   # -> [0, 3, 6, 9]

# python
p = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
p.insert(1, [6, 1])   # O(n): shifts everything after index 1
print(p)   # -> [[7, 0], [6, 1], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

# python
p = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
p.remove([7, 1])      # O(n): removes the FIRST equal element; ValueError if absent
print(p)   # -> [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]

# python
p = [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]
print([7, 0] in p)    # -> True   (O(n) scan; use a set for repeated lookups)

# python
p = [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]
p.append([0, 0])      # tail: O(1) amortized
print(p)   # -> [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4], [0, 0]]
p.insert(0, [9, 9])   # head: O(n); use collections.deque.appendleft for O(1)
print(p[0])   # -> [9, 9]

# python
# IDEA: list.sort(key=...) reorders the list itself; sorted(iterable, key=...) builds a new list
# time = O(n log n), space = O(n) for sorted(), no new list for .sort()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

# in place: sort by each word's letters (the LC 49 grouping key); stable, so ties keep input order
strs.sort(key=lambda word: "".join(sorted(word)))
print(strs)        # -> ['bat', 'eat', 'tea', 'ate', 'tan', 'nat']

# a new list: the original keeps its order
nums = [3, 1, 2]
ascending = sorted(nums)
descending = sorted(nums, reverse=True)
print(nums, ascending, descending)   # -> [3, 1, 2] [1, 2, 3] [3, 2, 1]

# python
# 1) assigning the result of an in-place sort: .sort() returns None
arr = [3, 1, 2]
result = arr.sort()
print(result, arr)        # -> None [1, 2, 3]   (so arr = arr.sort() loses the list)

# 2) .sort() exists only on lists
s = "cba"
try:
    s.sort()
except AttributeError as err:
    print(err)            # -> 'str' object has no attribute 'sort'
print("".join(sorted(s)))  # -> abc

# 3) a dict or a set: only sorted() works, and a dict sorts its KEYS
print(sorted({"b": 2, "a": 1}))   # -> ['a', 'b']
print(sorted({3, 1, 2}))          # -> [1, 2, 3]

# 4) sorting the caller's list inside a helper is a side effect
def smallest_two(nums):
    return sorted(nums)[:2]       # sorts a copy: the caller's list keeps its order

original = [5, 1, 4, 2]
print(smallest_two(original), original)   # -> [1, 2] [5, 1, 4, 2]

// java
// in place (like Python's list.sort())
int[] arr = {3, 1, 2};
Arrays.sort(arr);                                    // primitive array -> [1, 2, 3]
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));
Collections.sort(list);                              // List, in place -> [1, 2, 3]
List<int[]> pairs = new ArrayList<>();
pairs.add(new int[]{2, 0});
pairs.add(new int[]{1, 5});
pairs.sort((a, b) -> Integer.compare(a[0], b[0]));   // List + comparator, in place

// a NEW collection (like Python's sorted())
List<Integer> source = Arrays.asList(3, 1, 2);
List<Integer> sortedCopy = source.stream().sorted().collect(Collectors.toList());  // source untouched

# python
# IDEA: depth-first walk - emit an int, recurse into a list, keep the left-to-right order
# time = O(N + L), space = O(D)   N = ints, L = lists, D = nesting depth (the recursion stack)
def flatten(nested):
    out = []

    def walk(items):
        for item in items:
            if isinstance(item, list):
                walk(item)            # a list: descend
            else:
                out.append(item)      # a leaf: emit

    walk(nested)
    return out


print(flatten([1, 0, [1, 2, [4, [5, [6, [7]]]]]]))   # -> [1, 0, 1, 2, 4, 5, 6, 7]
print(flatten([[1, 1], 2, [1, 1]]))                  # -> [1, 1, 2, 1, 1]

# python
# IDEA: the same walk as a generator - values are produced on demand
# time = O(N + L) over a full iteration, space = O(D)
def iter_flat(nested):
    for item in nested:
        if isinstance(item, list):
            yield from iter_flat(item)
        else:
            yield item


print(list(iter_flat([1, [4, [6]]])))   # -> [1, 4, 6]

# python
# LC 251 - Flatten 2D Vector
# IDEA: lazy iterator - two cursors (row, col) into the ORIGINAL 2D array;
#       hasNext() skips exhausted / empty rows, next() reads one element and steps col
# time = O(1) amortized per call (O(R + N) over a full pass), space = O(1) extra
class Vector2D:

    def __init__(self, vec):
        self.vec = vec      # no copy: iterate the input where it is
        self.row = 0        # which inner list
        self.col = 0        # which index inside vec[row]

    def hasNext(self):
        # normalize: move (row, col) onto the next real element, if there is one.
        # re-entrant -> a second call finds col already valid and returns at once
        while self.row < len(self.vec):
            if self.col < len(self.vec[self.row]):
                return True
            # this row is used up (or was empty from the start): go to the next one
            self.row += 1
            self.col = 0
        return False

    def next(self):
        # normalize first, so next() is correct even if the caller never called hasNext()
        if not self.hasNext():
            raise StopIteration
        val = self.vec[self.row][self.col]
        self.col += 1
        return val

// java
// LC 251 - Flatten 2D Vector
// IDEA: same two cursors; hasNext() normalizes, next() is the only method that consumes
// time = O(1) amortized per call, space = O(1) extra
class Vector2D {
    private final int[][] vec;
    private int row = 0;   // which inner array
    private int col = 0;   // which index inside vec[row]

    public Vector2D(int[][] vec) {
        this.vec = vec;
    }

    public boolean hasNext() {
        // skip every used-up or empty row until (row, col) points at an element
        while (row < vec.length) {
            if (col < vec[row].length) {
                return true;
            }
            row++;
            col = 0;
        }
        return false;
    }

    public int next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        int val = vec[row][col];
        col++;
        return val;
    }
}

vec = [[1, 2], [], [3]]          (row, col) after each call

next()     -> 1                  (0, 1)
next()     -> 2                  (0, 2)   row 0 is used up, but nothing moves yet
hasNext()  -> true               (2, 0)   skipped row 0 (used up) and row 1 (empty)
hasNext()  -> true               (2, 0)   idempotent: already on an element
next()     -> 3                  (2, 1)
hasNext()  -> false              (3, 0)   row == len(vec)

# python
# IDEA: loop to max(len); an index past the end of one array reads as the default (0 here)
# time = O(max(m, n)), space = O(1)
from itertools import zip_longest

s = [1, 2, 3, 4]
t = [1, 2]

for i in range(max(len(s), len(t))):
    a = s[i] if i < len(s) else 0
    b = t[i] if i < len(t) else 0
    print(i, a, b)
# -> 0 1 1
#    1 2 2
#    2 3 0
#    3 4 0

# the same walk with the standard library
print(list(zip_longest(s, t, fillvalue=0)))   # -> [(1, 1), (2, 2), (3, 0), (4, 0)]

# only the common prefix: zip stops at the shorter one
print(list(zip(s, t)))                        # -> [(1, 1), (2, 2)]

# python
# LC 169 - Majority Element
# IDEA: Boyer-Moore vote - adopt a candidate when count is 0, +1 on a match, -1 otherwise
# time = O(n), space = O(1)
def majorityElement(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num       # everything before here cancelled out: start fresh
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1            # pair num with one copy of candidate and drop both
    # LC 169 guarantees a majority exists; without that guarantee,
    # verify: return candidate if nums.count(candidate) > len(nums) // 2 else None
    return candidate

// java
// LC 169 - Majority Element
// IDEA: Boyer-Moore vote - adopt a candidate when count is 0, +1 on a match, -1 otherwise
// time = O(n), space = O(1)
public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;      // everything before here cancelled out: start fresh
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;              // pair num with one copy of candidate and drop both
        }
    }
    return candidate;             // guaranteed to exist in LC 169; verify otherwise
}

nums = [2,2,1,1,1,2,2]
num | candidate | count | action
 2  |     2     |   1   | count was 0 -> adopt
 2  |     2     |   2   | match
 1  |     2     |   1   | cancel
 1  |     2     |   0   | cancel
 1  |     1     |   1   | count was 0 -> adopt
 2  |     1     |   0   | cancel
 2  |     2     |   1   | count was 0 -> adopt   -> answer 2 (4 of 7)

# python
# LC 229 - Majority Element II
# IDEA: Boyer-Moore with two candidates; a value matching neither cancels one of each;
#       then a second pass verifies both, because survivors are only candidates
# time = O(n), space = O(1)
def majorityElement(nums):
    cand1, cand2 = None, None
    count1, count2 = 0, 0
    for num in nums:
        if num == cand1:              # check both matches BEFORE adopting
            count1 += 1
        elif num == cand2:
            count2 += 1
        elif count1 == 0:
            cand1, count1 = num, 1
        elif count2 == 0:
            cand2, count2 = num, 1
        else:
            count1 -= 1               # num differs from both: cancel three values at once
            count2 -= 1
    result = []
    for cand in (cand1, cand2):       # verify: required here
        if cand is not None and nums.count(cand) > len(nums) // 3:
            result.append(cand)
    return result

// java
// LC 229 - Majority Element II
// IDEA: Boyer-Moore with two candidates, then count both again to verify
// time = O(n), space = O(1)
public List<Integer> majorityElement(int[] nums) {
    int cand1 = 0, cand2 = 0;         // safe: a num matching cand1 is never also adopted as cand2
    int count1 = 0, count2 = 0;
    for (int num : 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 (int num : nums) {            // second pass: survivors are only candidates
        if (num == cand1) {
            count1++;
        } else if (num == cand2) {
            count2++;
        }
    }
    List<Integer> result = new ArrayList<>();
    if (count1 > nums.length / 3) {
        result.add(cand1);
    }
    if (count2 > nums.length / 3) {
        result.add(cand2);
    }
    return result;
}

# python
# IDEA: generalised Boyer-Moore - at most k-1 candidates; a newcomer that finds the map
#       full decrements every candidate (and drops the ones that reach 0)
# time = O(n * k), space = O(k)
def frequent_over_n_over_k(nums, k):
    candidates = {}                   # value -> surviving count, at most k - 1 keys
    for num in nums:
        if num in candidates:
            candidates[num] += 1
        elif len(candidates) < k - 1:
            candidates[num] = 1
        else:
            for key in list(candidates):
                candidates[key] -= 1
                if candidates[key] == 0:
                    del candidates[key]
    result = []
    for cand in candidates:           # verify each survivor
        if nums.count(cand) > len(nums) // k:
            result.append(cand)
    return result

# python
# LC 2657 - Find the Prefix Common Array of Two Arrays
# IDEA: frequency array indexed by value; bump `common` the moment a count reaches 2
# time = O(n), space = O(n)
def findThePrefixCommonArray(A, B):
    n = len(A)
    count = [0] * (n + 1)        # values are 1..n, so index n must exist
    common = 0
    res = [0] * n
    for i in range(n):
        count[A[i]] += 1         # increment first ...
        if count[A[i]] == 2:     # ... then test, so the crossing step is the one counted
            common += 1
        count[B[i]] += 1
        if count[B[i]] == 2:
            common += 1
        res[i] = common
    return res

// java
// LC 2657 - Find the Prefix Common Array of Two Arrays
// IDEA: frequency array indexed by value; bump commonCount the moment a count reaches 2
// time = O(n), space = O(n)
public int[] findThePrefixCommonArray(int[] A, int[] B) {
    int n = A.length;
    int[] frequency = new int[n + 1];   // values are 1..n
    int commonCount = 0;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        frequency[A[i]]++;
        if (frequency[A[i]] == 2) {
            commonCount++;              // now seen in both arrays
        }
        frequency[B[i]]++;
        if (frequency[B[i]] == 2) {
            commonCount++;
        }
        res[i] = commonCount;
    }
    return res;
}

A = [1,3,2,4], B = [3,1,2,4]
i | A[i] B[i] | counts that reached 2 | common
0 |  1    3   | -                     | 0
1 |  3    1   | 3, 1                  | 2
2 |  2    2   | 2 (0 -> 1 -> 2 in one step) | 3
3 |  4    4   | 4                     | 4      -> [0, 2, 3, 4]

# subarrays containing index i
   = (choices for LEFT boundary) × (choices for RIGHT boundary)
   = (i + 1) × (n - i)
     left  boundary ∈ {0, 1, ..., i}     → (i + 1) choices
     right boundary ∈ {i, i+1, ..., n-1} → (n - i) choices

# python
# LC 2063 - Vowels of All Substrings
# IDEA: each vowel at index i appears in (i+1)*(n-i) substrings; sum those products
# time = O(n), space = O(1)
def countVowels(word):
    vowels = set("aeiou")
    n = len(word)
    total = 0
    for i in range(n):
        if word[i] in vowels:
            starting_choices = i + 1      # left boundary: 0..i
            ending_choices = n - i        # right boundary: i..n-1
            total += starting_choices * ending_choices
    return total

// java
// LC 2063 - Vowels of All Substrings
// IDEA: each vowel at index i appears in (i+1)*(n-i) substrings; sum in a long
// time = O(n), space = O(1)
public long countVowels(String word) {
    long total = 0;
    int n = word.length();
    String vowels = "aeiou";
    for (int i = 0; i < n; i++) {
        if (vowels.indexOf(word.charAt(i)) >= 0) {
            long startingChoices = i + 1;   // left boundary: 0..i
            long endingChoices = n - i;     // right boundary: i..n-1
            total += startingChoices * endingChoices;
        }
    }
    return total;
}

word = "aba" (n = 3)
i | char | vowel? | (i+1) × (n-i)
0 |  a   |  yes   | 1 × 3 = 3
1 |  b   |  no    | -
2 |  a   |  yes   | 3 × 1 = 3        total = 6
check: "a"=1 "ab"=1 "aba"=2 "b"=0 "ba"=1 "a"=1 -> 6

remove(val):
1. i = idx[val]                  (hash map: value -> index)
2. vals[i] = vals[-1]            (plug the hole with the last value)
3. idx[vals[-1]] = i             (the moved value's index changed)
4. vals.pop(); del idx[val]      (O(1) tail removal)

# python
# LC 380 - Insert Delete GetRandom O(1)
# IDEA: list for O(1) random access + dict {value: index};
#       delete by swapping the victim with the LAST element, then pop
# time = O(1) per insert / remove / getRandom, space = O(n)
import random

class RandomizedSet(object):

    def __init__(self):
        self.vals = []   # dense array of values
        self.idx = {}    # value -> index in self.vals

    def insert(self, val):
        if val in self.idx:
            return False
        self.idx[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val):
        if val not in self.idx:
            return False
        i = self.idx[val]
        last = self.vals[-1]
        self.vals[i] = last          # plug the hole with the last element
        self.idx[last] = i
        self.vals.pop()
        del self.idx[val]            # after the re-index, so val == last still works
        return True

    def getRandom(self):
        return random.choice(self.vals)

// java
// LC 380 - Insert Delete GetRandom O(1)
// IDEA: ArrayList for O(1) random access + HashMap<value, index>;
//       delete by swapping the victim with the LAST element, then pop
// time = O(1) per insert / remove / getRandom, space = O(n)
class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Integer> idx = new HashMap<>(); // value -> index in vals
    private final Random rand = new Random();

    public boolean insert(int val) {
        if (idx.containsKey(val)) {
            return false;
        }
        idx.put(val, vals.size());   // the new value goes to the tail
        vals.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer i = idx.get(val);
        if (i == null) {
            return false;
        }
        int lastIdx = vals.size() - 1;
        int lastVal = vals.get(lastIdx);
        vals.set(i, lastVal);        // plug the hole with the last element
        idx.put(lastVal, i);
        vals.remove(lastIdx);        // remove by INDEX (int), not by object
        idx.remove(val);             // after the re-index, so val == lastVal still works
        return true;
    }

    public int getRandom() {
        return vals.get(rand.nextInt(vals.size()));
    }
}

# python
# LC 1007 - Minimum Domino Rotations For Equal Row
# IDEA: the answer must be tops[0] or bottoms[0] -> verify both candidates
# time = O(n), space = O(1)
def minDominoRotations(tops, bottoms):
    n = len(tops)

    def rotations_to_show(x):
        # flips needed so one whole row shows x; -1 if some domino lacks x entirely
        rot_top = 0      # flips to put x on top
        rot_bottom = 0   # flips to put x on bottom
        for i in range(n):
            if tops[i] != x and bottoms[i] != x:
                return -1
            if tops[i] != x:
                rot_top += 1
            elif bottoms[i] != x:      # elif: x on both faces needs no flip at all
                rot_bottom += 1
        return min(rot_top, rot_bottom)

    res = rotations_to_show(tops[0])
    if res != -1 or tops[0] == bottoms[0]:   # one candidate only when the faces match
        return res
    return rotations_to_show(bottoms[0])

// java
// LC 1007 - Minimum Domino Rotations For Equal Row
// IDEA: the answer must be tops[0] or bottoms[0] -> verify both candidates
// time = O(n), space = O(1)
public int minDominoRotations(int[] tops, int[] bottoms) {
    int res = rotationsToShow(tops[0], tops, bottoms);
    if (res != -1 || tops[0] == bottoms[0]) {
        return res;
    }
    return rotationsToShow(bottoms[0], tops, bottoms);
}

// flips needed so one whole row shows x; -1 if some domino lacks x entirely
private int rotationsToShow(int x, int[] tops, int[] bottoms) {
    int rotTop = 0;
    int rotBottom = 0;
    for (int i = 0; i < tops.length; i++) {
        if (tops[i] != x && bottoms[i] != x) {
            return -1;
        }
        if (tops[i] != x) {
            rotTop++;
        } else if (bottoms[i] != x) {
            rotBottom++;
        }
    }
    return Math.min(rotTop, rotBottom);
}

# python
# LC 41 - First Missing Positive
# IDEA: cyclic sort - swap each value v in 1..n to index v - 1; the first index that
#       holds the wrong value names the first missing positive
# time = O(n), space = O(1)
def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # keep swapping until nums[i] is out of range or its home already holds it
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1          # computed first: the swap below changes nums[i]
            nums[i], nums[home] = nums[home], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1                        # 1..n are all present

// java
// LC 41 - First Missing Positive
// IDEA: cyclic sort - swap each value v in 1..n to index v - 1, then scan for the first gap
// time = O(n), space = O(1)
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // keep swapping until nums[i] is out of range or its home already holds it
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int home = nums[i] - 1;
            int tmp = nums[home];
            nums[home] = nums[i];
            nums[i] = tmp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;          // 1..n are all present
}

nums = [3, 4, -1, 1], n = 4
i=0  3 -> home 2   [-1, 4, 3, 1]   -1 is out of range: stop
i=1  4 -> home 3   [-1, 1, 3, 4]
     1 -> home 0   [1, -1, 3, 4]   -1 is out of range: stop
i=2  3 is home
i=3  4 is home
scan: nums[1] = -1 != 2   -> answer 2

# python
# LC 189 - Rotate Array
# IDEA: reverse all, then reverse the first k and the last n - k: AB -> rev(B)rev(A) -> BA
# time = O(n), space = O(1)
def rotate(nums, k):
    n = len(nums)
    k %= n                       # k may exceed n

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

    reverse(0, n - 1)            # rev(B) rev(A)
    reverse(0, k - 1)            # B rev(A)
    reverse(k, n - 1)            # B A

// java
// LC 189 - Rotate Array
// IDEA: reverse all, then reverse the first k and the last n - k
// time = O(n), space = O(1)
public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;                        // k may exceed n
    reverse(nums, 0, n - 1);       // rev(B) rev(A)
    reverse(nums, 0, k - 1);       // B rev(A)
    reverse(nums, k, n - 1);       // B A
}

private void reverse(int[] nums, int lo, int hi) {
    while (lo < hi) {
        int tmp = nums[lo];
        nums[lo] = nums[hi];
        nums[hi] = tmp;
        lo++;
        hi--;
    }
}

nums = [1, 2, 3, 4, 5, 6, 7], k = 3      A = [1,2,3,4], B = [5,6,7]
reverse all          [7, 6, 5, 4, 3, 2, 1]
reverse [0, k-1]     [5, 6, 7, 4, 3, 2, 1]
reverse [k, n-1]     [5, 6, 7, 1, 2, 3, 4]

# python
# LC 849 - Maximize Distance to Closest Person
# IDEA: carry the last occupied index; an inner gap scores (i - last) // 2,
#       the leading and the trailing gap score their full length
# time = O(n), space = O(1)
def maxDistToClosest(seats):
    n = len(seats)
    best = 0
    last = -1                      # no occupied seat seen yet
    for i in range(n):
        if seats[i] == 1:
            if last == -1:
                best = i           # leading gap: sit in seat 0
            else:
                best = max(best, (i - last) // 2)   # inner gap: sit in the middle
            last = i
    return max(best, n - 1 - last) # trailing gap: sit in the last seat (0 if it is taken)

// java
// LC 849 - Maximize Distance to Closest Person
// IDEA: carry the last occupied index; inner gaps are halved, the two end gaps are not
// time = O(n), space = O(1)
public int maxDistToClosest(int[] seats) {
    int n = seats.length;
    int best = 0;
    int last = -1;                 // no occupied seat seen yet
    for (int i = 0; i < n; i++) {
        if (seats[i] == 1) {
            if (last == -1) {
                best = i;          // leading gap: sit in seat 0
            } else {
                best = Math.max(best, (i - last) / 2);   // inner gap: sit in the middle
            }
            last = i;
        }
    }
    return Math.max(best, n - 1 - last);   // trailing gap
}

seats = [0, 0, 1, 0, 1, 0, 0, 0]
i=2  first 1        leading gap  -> best = 2      last = 2
i=4  1              (4 - 2) // 2 = 1, best = 2    last = 4
end                 trailing gap 7 - 4 = 3        best = 3