陣列

# python_trick.html

#-----------------------------------------------------------------------------------------------------
# example 7 : itertools.islice : slice on iterator
#-----------------------------------------------------------------------------------------------------
# https://docs.python.org/3/library/itertools.html#itertools.islice
# syntax : itertools.islice(seq, [start,] stop [, step])

In [6]:  x = itertools.islice(range(10), 0, 9, 2)

In [7]: print (list(x))
[0, 2, 4, 6, 8]


In [18]: y = itertools.islice(range(10), 0, 10, 3)
    ...: print (list(y))
[0, 3, 6, 9]

p=[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
Out[27]: [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
In [28]: p.insert(1, [6,1])
In [29]: p
Out[29]: [[7, 0], [6, 1], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

p=[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

In [4]: p
Out[4]: [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

In [5]: p.remove([7, 1])

In [6]: p
Out[6]: [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]

In [7]: p
Out[7]: [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]

In [8]: [7,0] in p
Out[8]: True

# tail
In [9]: p
Out[9]: [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4]]

In [10]: p.append([0,0])

In [11]: p
Out[11]: [[7, 0], [6, 1], [5, 0], [5, 2], [4, 4], [0, 0]]

# Pattern :
# V1 : IN PLACE, returns None
_array.sort(key = lambda x : <your_sorting_func>)

# V2 : returns a NEW list, `_array` unchanged
new_array = sorted(_array, key = lambda x : <your_sorting_func>)

# 049  Group Anagrams
strs = ["eat","tea","tan","ate","nat","bat"]
strs.sort(key = lambda x : ''.join(sorted(x)) )
print (strs)
# ['bat', 'eat', 'tea', 'ate', 'tan', 'nat']

### NOTE can use this as well
sorted(strs, key = lambda x : ''.join(sorted(x)))

# 1) Assigning the result of an in-place sort
arr = arr.sort()          # ❌ arr becomes None !!!
arr.sort(); use(arr)      # ✅

# 2) Calling .sort() on a non-list
s = "cba"
s.sort()                  # ❌ AttributeError : 'str' has no attribute 'sort'
sorted(s)                 # ✅ ['a','b','c']

# 3) Sorting a dict / set (only `sorted` works)
sorted({'b':2, 'a':1})    # ✅ ['a','b']  <-- iterates over KEYS
sorted({3,1,2})           # ✅ [1,2,3]

# 4) Mutating the input when the caller still needs it
def f(nums):
    nums.sort()           # ❌ caller's list is modified (side effect)
    return nums
def f(nums):
    return sorted(nums)   # ✅ no side effect

// java
// in place (like py .sort())
Arrays.sort(arr);                                  // primitive array, in place
Collections.sort(list);                            // List, in place
list.sort((a, b) -> a[0] - b[0]);                  // List, in place

// returns NEW collection (like py sorted())
List<Integer> sortedList = list.stream()
        .sorted()
        .collect(Collectors.toList());             // new list, original untouched

# LC 341
# V0
class NestedIterator(object):

    def __init__(self, nestedList):

        self.queue = []
        
        def getAll(nests):
            for nest in nests:
                if nest.isInteger():
                    self.queue.append(nest.getInteger())
                else:
                    getAll(nest.getList())
        getAll(nestedList)

    def next(self):

        return self.queue.pop(0)

    def hasNext(self):

        return len(self.queue)

# default py
# V1
def flatten_array(_array):
    r = []
    def helper(_array):
        for i in _array:
            if type(i) == int:
                print (i)
                r.append(i)
            else:
                helper(i)

    helper(_array)
    return r
    
_input = [1,0, [1,2,[4,[5,[6,[7]]]]]]#[1,[4,[6]]] #[[1,1],2,[1,1]]

res = flatten_array(_input)
print ("res = " + str(res))

# V2
# https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists
def flatten(L):
    for item in L:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

r2 = flatten(_input)
r2_ = [x for x in r2]
print (r2_)

# V3
def flatten2(L):
    for item in L:
        try:
            yield from flatten2(item)
        except:
            yield item

r3 = flatten2(_input)
r3_ = [x for x in r3]
print (r3_)

// java
// algorithm book (labu) p.355
//------------------------------------------
// implement NestedInteger data structure
//------------------------------------------
public class NestedInteger {
    private Integer val;
    private List<NestedInteger> list;

    public NestedInteger(Integer val){
        this.val = val;
        this.list = null;
    }

    public NestedInteger(List<NestedInteger> list){
        this.list = list;
        this.val = null;
    }

    // if saved value is integer, return true, else false
    public boolean isIntger(){
        return val != null;
    }

    // if saved value is integer, return it, else return null
    public Integer getInteger(){
        return this.val;
    }

    // if saved value is array, return it, else return null
    public List<NestedInteger> getList(){
        return this.list;
    }

}

// java
// LC 341
// algorithm book (labu) p.357
//-----------------------------------------------------------
// NestedInteger solution V1 :  via tree algorithm
//-----------------------------------------------------------
class NestedIterator implements Iterator<Integer>{

    private Iterator<Integer> it;

    public NestedIterator(List<NestedInteger> nestedList){
        // save flatten result
        List<Integer> result = new LinkedList<>();

        for (NestedInteger node: nestedList){
            // start from each node and proceed
            traverse(node, result);
        }

        // get result's iterator
        this.it = result.iterator();
    }

    public Integer next(){
        return it.next();
    }

    public boolean hasNext(){
        return it.hasNext();
    }

    // traverse tree with root as root, and add nodes to result array
    private void traverse(NestedInteger root, List<Integer> result){
        if (root.isIntger()){
            // arrive root node
            result.add(root.getInteger());
            return;
        }

        // traverse framework
        for (NestedInteger child: root.getList()){
            traverse(child, result);
        }
    }
}

// java
// LC 341
// algorithm book (labu) p.358
//-----------------------------------------------------------
// NestedInteger solution V2 :  via lazy calling
//-----------------------------------------------------------
public class NestedIterator implements Iterator<Integer>{

    private LinkedList<NestedInteger> list;

    public NestedIterator(List<NestedInteger> nestedList){
        // use LinkedList, for good performance in below op
        list = new LinkedList<>(nestedList);
    }

    public Integer next(){
        // hasNext method make sure 1st element must be Integer type
        return list.remove(0).getInteger();
    }

    public boolean hasNext(){
        // for loop split elements in array until 1st element is Integer type
        while (!list.isEmpty() && list.get(0).isIntger()){
            // when 1st element is array type, go into the loop
            List<NestedInteger> first = list.remove(0).getList();
            // flatten 1st array, and add to "start" in ordering
            for (int i = first.size() - 1; i >= 0; i--){
                list.addFirst(first.get(i));
            }  
        }
        return !list.isEmpty();
    }
}

#--------------------
# example 1
#--------------------

# 2 array : s,t
# len(s) = 10, len(t) = 7
# or
# len(s) = 10, len(t) = 11
if len(s) > len(t):
    s,t  = t,s

for i in range(len(s)):
    print (s[i], t[i])


#--------------------
# example 2
#--------------------
# LC 165
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        nums1 = version1.split('.')
        nums2 = version2.split('.')
        n1, n2 = len(nums1), len(nums2)
        
        # NOTE here !!!
        # compare versions
        for i in range(max(n1, n2)):
            i1 = int(nums1[i]) if i < n1 else 0
            i2 = int(nums2[i]) if i < n2 else 0
            if i1 != i2:
                return 1 if i1 > i2 else -1
        
        # the versions are equal
        return 0

# Python - LC 169
def majorityElement(nums):
    """
    Find element appearing > n/2 times
    Time: O(n)
    Space: O(1)
    """
    candidate = None
    count = 0

    # Phase 1: Find candidate
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1  # Cancel out

    # Phase 2: Verify (can skip if majority guaranteed)
    # return candidate

    # If not guaranteed, verify:
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None

// Java - LC 169
// V0
// IDEA: Boyer-Moore Majority Vote
/**
 * Key Insight:
 * - Pair different elements and cancel them out
 * - Majority element will survive cancellation
 * - Works because majority element appears > n/2 times
 *
 * Time: O(n)
 * Space: O(1)
 */
public int majorityElement(int[] nums) {
    /**
     * time = O(N)
     * space = O(1)
     */
    int candidate = nums[0];
    int count = 1;

    // Phase 1: Find candidate by cancellation
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            // Start new candidate when count reaches 0
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            // Same element: increment count
            count++;
        } else {
            // Different element: cancel out
            count--;
        }
    }

    // Phase 2: Verify (optional if majority guaranteed)
    // If problem guarantees majority exists, return candidate directly
    return candidate;

    // Otherwise, verify:
    // int actualCount = 0;
    // for (int num : nums) {
    //     if (num == candidate) actualCount++;
    // }
    // return actualCount > nums.length / 2 ? candidate : -1;
}

Index | num | candidate | count | Action
--------------------------------------------
  0   |  2  |     2     |   1   | Initialize
  1   |  2  |     2     |   2   | Same, increment
  2   |  1  |     2     |   1   | Different, decrement
  3   |  1  |     2     |   0   | Different, decrement
  4   |  1  |     1     |   1   | Count=0, new candidate
  5   |  2  |     1     |   0   | Different, decrement
  6   |  2  |     2     |   1   | Count=0, new candidate

Result: 2 (appears 4 times > 7/2 = 3.5)

# Python - LC 229
def majorityElement(nums):
    """
    Find all elements appearing > n/3 times
    Time: O(n)
    Space: O(1)
    """
    # Phase 1: Find up to 2 candidates
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            # Different from both: cancel out
            count1 -= 1
            count2 -= 1

    # Phase 2: Verify candidates
    result = []
    for candidate in [candidate1, candidate2]:
        if candidate is not None and nums.count(candidate) > len(nums) // 3:
            result.append(candidate)

    return result

// Java - LC 229
// V0
// IDEA: Boyer-Moore Majority Vote (Generalized)
/**
 * Key Insight:
 * - At most 2 elements can appear > n/3 times
 * - Use 2 candidates and 2 counts
 * - Cancellation decrements both counts
 * - MUST verify both candidates
 *
 * Time: O(n)
 * Space: O(1)
 */
public List<Integer> majorityElement(int[] nums) {
    /**
     * time = O(N)
     * space = O(1)
     */
    int candidate1 = 0, candidate2 = 0;
    int count1 = 0, count2 = 0;

    // Phase 1: Find up to 2 candidates
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            // Different from both: cancel out
            count1--;
            count2--;
        }
    }

    // Phase 2: Verify candidates (REQUIRED!)
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }

    List<Integer> result = new ArrayList<>();
    if (count1 > nums.length / 3) result.add(candidate1);
    if (count2 > nums.length / 3) result.add(candidate2);

    return result;
}

Index | num | c1 | cnt1 | c2 | cnt2 | Action
-------------------------------------------------
  0   |  3  | 3  |  1   | 0  |  0   | Set candidate1
  1   |  2  | 3  |  1   | 2  |  1   | Set candidate2
  2   |  3  | 3  |  2   | 2  |  1   | Match candidate1

Verification:
- candidate1=3: appears 2 times > 3/3 = 1 ✓
- candidate2=2: appears 1 time ≤ 3/3 = 1 ✗

Result: [3]

// Generalized Boyer-Moore for n/k threshold
import java.util.*;

class BoyerMooreGeneralized {
    /**
     * Find all elements appearing > n/k times
     * time = O(N × k)
     * space = O(k)
     */
    public List<Integer> majorityElement(int[] nums, int k) {
        // At most k-1 candidates for n/k threshold
        Map<Integer, Integer> candidates = new HashMap<>();

        // Phase 1: Find up to k-1 candidates
        for (int num : nums) {
            if (candidates.containsKey(num)) {
                candidates.put(num, candidates.get(num) + 1);
            } else if (candidates.size() < k - 1) {
                candidates.put(num, 1);
            } else {
                // Decrement all counts (cancellation)
                List<Integer> toRemove = new ArrayList<>();
                for (Map.Entry<Integer, Integer> entry : candidates.entrySet()) {
                    int count = entry.getValue() - 1;
                    if (count == 0) {
                        toRemove.add(entry.getKey());
                    } else {
                        candidates.put(entry.getKey(), count);
                    }
                }
                for (int key : toRemove) {
                    candidates.remove(key);
                }
            }
        }

        // Phase 2: Verify all candidates
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (candidates.containsKey(num)) {
                counts.put(num, counts.getOrDefault(num, 0) + 1);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > nums.length / k) {
                result.add(entry.getKey());
            }
        }

        return result;
    }
}

# Python - LC 2657
def findThePrefixCommonArray(A, B):
    """
    Find prefix common array using frequency counting.

    Key Insight:
    - Each number appears at most twice total (once in A, once in B)
    - When count[x] == 2, x has been seen in both arrays → common element

    Time: O(n)
    Space: O(n)
    """
    n = len(A)
    res = [0] * n
    count = [0] * (n + 1)  # values are 1..n
    common = 0

    for i in range(n):
        # Process element from A
        count[A[i]] += 1
        if count[A[i]] == 2:
            common += 1

        # Process element from B
        count[B[i]] += 1
        if count[B[i]] == 2:
            common += 1

        res[i] = common

    return res

// Java - LC 2657
// V0
// IDEA: Frequency Array + Running Count
/**
 * Core Insight:
 * - Each number appears at most twice total (once in A, once in B)
 * - When frequency[x] == 2, x is present in both arrays → common element
 * - Running count tracks cumulative common elements
 *
 * Why This Works:
 * - Permutation guarantee: each value 1..n appears exactly once in each array
 * - Processing both arrays simultaneously at each index
 * - frequency[x] can only be 0, 1, or 2
 * - frequency[x] == 2 means: seen once in A AND once in B
 *
 * Time: O(n) - single pass through both arrays
 * Space: O(n) - frequency array of size n+1
 */
public int[] findThePrefixCommonArray(int[] A, int[] B) {
    int n = A.length;
    int[] res = new int[n];

    // Since values are 1 to n, use array as hash map
    int[] frequency = new int[n + 1];
    int commonCount = 0;

    for (int i = 0; i < n; i++) {
        // Process element from A
        frequency[A[i]]++;
        if (frequency[A[i]] == 2) {
            commonCount++;  // Now seen in both arrays
        }

        // Process element from B
        frequency[B[i]]++;
        if (frequency[B[i]] == 2) {
            commonCount++;  // Now seen in both arrays
        }

        // Store current prefix common count
        res[i] = commonCount;
    }

    return res;
}

Index | A[i] | B[i] | frequency (after)     | commonCount | Action
----------------------------------------------------------------------
  0   |  1   |  3   | [0,1,0,1,0]           |     0       | freq[1]=1, freq[3]=1
  1   |  3   |  1   | [0,2,0,2,0]           |     2       | freq[3]=2 ✓, freq[1]=2 ✓
  2   |  2   |  2   | [0,2,2,2,0]           |     3       | freq[2]=1, then freq[2]=2 ✓
  3   |  4   |  4   | [0,2,2,2,2]           |     4       | freq[4]=1, then freq[4]=2 ✓

Result: [0, 2, 3, 4]

// Generalized frequency threshold pattern
/**
 * Detect when elements reach threshold k
 * Useful for: intersection counting, duplicate detection, k-frequency problems
 */
public void frequencyThresholdPattern(int[] arr1, int[] arr2, int maxVal, int threshold) {
    int[] frequency = new int[maxVal + 1];
    int count = 0;

    for (int i = 0; i < arr1.length; i++) {
        // Process from first source
        frequency[arr1[i]]++;
        if (frequency[arr1[i]] == threshold) {
            count++;  // Element reached threshold
        }

        // Process from second source (if applicable)
        frequency[arr2[i]]++;
        if (frequency[arr2[i]] == threshold) {
            count++;
        }

        // Use count as needed...
    }
}

# subarrays containing index i
   = (choices for LEFT boundary) × (choices for RIGHT boundary)
   = (i + 1) × (n - i)

   where:
     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
class Solution(object):
    def countVowels(self, word):
        # time = O(n), space = O(1)
        total_vowel_count = 0
        vowels = set("aeiou")
        n = len(word)

        # single pass: accumulate each vowel's contribution
        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_vowel_count += starting_choices * ending_choices

        return total_vowel_count

// Java - LC 2063 Vowels of All Substrings
// IDEA: each vowel at index i appears in (i+1)*(n-i) substrings
class Solution {
    /**
     * time = O(n), space = O(1)
     *
     * Each vowel at index i is contained in (i+1)*(n-i) substrings:
     *   - left  boundary can be any of 0..i      → (i+1) choices
     *   - right boundary can be any of i..n-1     → (n-i) choices
     * Use `long` for the running total — it can exceed int range.
     */
    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;
    }
}

Index | char | vowel? | (i+1) | (n-i) | contribution
---------------------------------------------------------
  0   |  a   |  yes   |   1   |   3   |   1 * 3 = 3
  1   |  b   |  no    |   -   |   -   |   0
  2   |  a   |  yes   |   3   |   1   |   3 * 1 = 3

Total = 3 + 0 + 3 = 6

Verify by listing all substrings & their vowel counts:
  "a"   → 1     "ab"  → 1     "aba" → 2
  "b"   → 0     "ba"  → 1
  "a"   → 1
  sum = 1+1+2+0+1+1 = 6 ✓

// Generic "sum a per-element value over all subarrays" template
// time = O(n), space = O(1)
public long sumOverAllSubarrays(int[] arr) {
    long total = 0;
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        long subarraysContainingI = (long) (i + 1) * (n - i);
        total += arr[i] * subarraysContainingI;   // arr[i]'s total contribution
    }
    return total;
}

read  ->  p1 (end of real data in dst), p2 (end of src)
write ->  the LAST slot of dst

while src not exhausted:
    write the LARGER of dst[p1] / src[p2]  into dst[write]
    move that read pointer back, move write back

// java
// LC 88 - Merge Sorted Array
// IDEA: fill nums1 from the BACK, always writing the larger of the two tails
public void merge(int[] nums1, int m, int[] nums2, int n) {
    // time = O(m + n), space = O(1)
    int p1 = m - 1;         // last real value in nums1
    int p2 = n - 1;         // last value in nums2
    int write = m + n - 1;  // write pointer: very end of nums1

    /**
     *  NOTE !!!
     *
     *   loop only while p2 >= 0.
     *   If nums2 runs out, whatever is left in nums1[0..p1] is
     *   ALREADY in the right place -> nothing more to do.
     *   (If nums1 runs out first, the `p1 >= 0` guard sends us
     *    down the nums2 branch and copies the rest over.)
     */
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[write--] = nums1[p1--];
        } else {
            nums1[write--] = nums2[p2--];
        }
    }
}

# python
# LC 88 - Merge Sorted Array
# IDEA: fill nums1 from the BACK, always writing the larger of the two tails
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        # time = O(m + n), space = O(1)
        p1, p2, write = m - 1, n - 1, m + n - 1

        # NOTE : loop on p2 only -> leftovers in nums1 are already in place
        while p2 >= 0:
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[write] = nums1[p1]
                p1 -= 1
            else:
                nums1[write] = nums2[p2]
                p2 -= 1
            write -= 1

              p1        write
[1, 2, 3, _, _, _]   p2=2 (6)   6 > 3  -> write 6
[1, 2, 3, _, _, 6]   p2=1 (5)   5 > 3  -> write 5
[1, 2, 3, _, 5, 6]   p2=0 (2)   3 > 2  -> write 3 (from nums1)
[1, 2, _, 3, 5, 6]   p2=0 (2)   2 > 2? no -> write 2 (from nums2)
[1, 2, 2, 3, 5, 6]   p2 = -1  -> DONE, [1,2] already in place

1. look up the victim's index i   (HashMap: value -> index)
2. move the LAST element into slot i   ("plug the hole")
3. update the moved element's index in the map
4. pop the last slot  (O(1))

// 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
class RandomizedSet {
    // time = O(1) for insert / remove / getRandom, space = O(n)
    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()); // new element goes to the tail
        vals.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer i = idx.get(val);
        if (i == null) return false;

        /**
         *  NOTE !!!  swap-with-last, then pop
         *
         *   - move the LAST value into the hole at index i
         *   - re-point the moved value's index in the map
         *   - remove the tail slot (O(1))
         *
         *   Order matters: `idx.remove(val)` MUST come after
         *   `idx.put(lastVal, i)`, otherwise the self-delete case
         *   (val IS the last element) leaves a stale entry behind.
         */
        int lastIdx = vals.size() - 1;
        int lastVal = vals.get(lastIdx);
        vals.set(i, lastVal);
        idx.put(lastVal, i);
        vals.remove(lastIdx); // remove by INDEX (int), not by object
        idx.remove(val);
        return true;
    }

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

# 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
import random

class RandomizedSet(object):
    # time = O(1) for insert / remove / getRandom, space = O(n)
    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]
        ### NOTE : plug the hole with the last element, then pop
        self.vals[i] = last
        self.idx[last] = i
        self.vals.pop()
        ### NOTE : delete AFTER the re-index, so val == last still works
        del self.idx[val]
        return True

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

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

// how many rotations to make EVERY domino show x (on one row) ? -1 if impossible
private int check(int x, int[] tops, int[] bottoms) {
    int rotTop = 0, rotBottom = 0;
    for (int i = 0; i < tops.length; i++) {
        // x missing on this domino entirely -> impossible
        if (tops[i] != x && bottoms[i] != x) return -1;
        if (tops[i] != x) rotTop++;          // need a flip to put x on TOP
        else if (bottoms[i] != x) rotBottom++; // need a flip to put x on BOTTOM
    }
    return Math.min(rotTop, rotBottom);
}

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

        def check(x):
            rot_top = rot_bottom = 0
            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:
                    rot_bottom += 1
            return min(rot_top, rot_bottom)

        res = check(tops[0])
        if res != -1 or tops[0] == bottoms[0]:
            return res
        return check(bottoms[0])