Array

Basic linear data structure

0) Concept

• Java Array
  • Low level : continuous blocks in memory space

0-1) Types

• Types

  • greedy.md
  • matrix.md

• Algorithm

  • index op
  • array op
  • sorting
  • binary search
  • 2 pointers
    • fast-slow pointers
    • left-right pointers
  • sliding window
  • prefix sum
  • difference array
  • Kadane algo

• Data structure

  • dict
  • set
  • array

0-2) Pattern

1) General form

1-1) Basic OP

1-1-0) Split Array

# 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]

1-1-1) Insert into Array

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]]

1-1-2) Delete from Array

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]]

1-1-3) check if element in Array

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

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

1-1-4) append to array (head, tail)

# 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]]

1-1-5) Sort Array*****

# Pattern :
# V1
_array.sort(key = lambda x : <your_sorting_func>)

# V2
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-1-6) Flatten Array

# 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 NestedInteger(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 NestedInteger(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();
    }
}

1-1-7) Sort array with 2 keys

y = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
print (y)
y.sort(key = lambda x : (-x[0], x[1]))
print (y)
# [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
# [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

1-1-8) go through 2 arrays (length could be different)

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

1-1-9) shallow, deep copy

# LC 670
# V0'
# IDEA : BRUTE FORCE
# NOTE : there is also 2 pointers solution : 
#        -> https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Array/maximum-swap.py#L49
# NOTE : ans = A[:]
#        A[:] is a `shallow copy` syntax in python,
#        it will copy "parent obj" (not child obj) to the other instance
#        so the changes ("parent obj" only) in original instance will NOT affect the copied instance
# https://stackoverflow.com/questions/4081561/what-is-the-difference-between-list-and-list-in-python
# https://github.com/yennanliu/til#20210923
class Solution(object):
    def maximumSwap(self, num):
        A = list(str(num))
        ans = A[:]
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                A[i], A[j] = A[j], A[i]
                if A > ans: 
                    ans = A[:]
                A[i], A[j] = A[j], A[i]

        return int("".join(ans))

---

1-2) Special Array Algorithms

1-2-1) Boyer-Moore Majority Vote Algorithm

Concept:

• Find element(s) appearing more than ⌊n/k⌋ times in an array
• Key Idea: Pair different elements and cancel them out
• Majority element survives cancellation
• Two-phase: (1) Find candidates, (2) Verify counts
• Space: O(k) for k-1 candidates

When to Use:

• “Find majority element” → element appearing > n/2 times
• “Find all elements appearing more than n/3 times”
• “Heavy hitters” or “frequent elements” problems
• Need O(1) space (better than HashMap O(n))

Related: See streaming_algorithms.md for detailed explanation.

---

Pattern 1: Standard Majority Element (> n/2) - LC 169

Algorithm:

• Maintain one candidate and count
• When count=0, select new candidate
• Increment count for same element, decrement for different
• Majority element survives

# 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;
}

Example Trace: nums = [2,2,1,1,1,2,2]

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)

---

Pattern 2: Elements Appearing > n/3 Times - LC 229

Key Insight: At most 2 elements can appear more than n/3 times.

Algorithm:

• Maintain two candidates and two counts
• Cancellation requires decrementing both counts
• Must verify both candidates in phase 2

# 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;
}

Example Trace: nums = [3,2,3]

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]

---

Pattern 3: Generalized k-Majority (> n/k times)

Concept: For elements appearing more than n/k times, at most k-1 candidates exist.

// 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;
    }
}

---

Boyer-Moore: Common Mistakes & Tips

🚫 Common Mistakes:

1. Missing Verification Phase

   // ❌ WRONG: Assuming candidate is always majority
   return candidate;
   
   // ✅ CORRECT: Verify count (if not guaranteed)
   int actualCount = 0;
   for (int num : nums) {
       if (num == candidate) actualCount++;
   }
   return actualCount > nums.length / 2 ? candidate : -1;
   

2. Wrong Cancellation Logic for LC 229

   // ❌ WRONG: Only checking candidate1
   if (num != candidate1) count1--;
   
   // ✅ CORRECT: Check both, reset on count=0
   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 {
       count1--; count2--;
   }
   

3. Not Handling Duplicate Candidates (LC 229)

   // ❌ WRONG: candidate1 and candidate2 can be same initially
   
   // ✅ CORRECT: Check candidate1 first, then candidate2
   if (num == candidate1) count1++;
   else if (num == candidate2) count2++;
   // ... rest of logic
   

💡 Interview Tips:

1. When to Use:

   • “Find majority element” keywords
   • Need O(1) space (vs HashMap O(n))
   • Guaranteed majority exists

2. Talking Points:

   • “Pairing and cancellation eliminates non-majority elements”
   • “At most k-1 elements can appear more than n/k times”
   • “Two-phase: find candidates, then verify”

3. Complexity:

   • Time: O(n) single pass (+ O(n) for verification = O(n) total)
   • Space: O(1) for standard, O(k) for generalized

---

Related LeetCode Problems:

Problem	Difficulty	Threshold	Candidates	Verify?
LC 169	Easy	> n/2	1	Optional*
LC 229	Medium	> n/3	2	Required
General	-	> n/k	k-1	Required

*Optional if problem guarantees majority element exists.

---

Summary:

• ✅ Boyer-Moore: O(n) time, O(1) space majority finding
• ✅ Key insight: Cancellation eliminates non-majority elements
• ✅ Two-phase: (1) Find candidates, (2) Verify counts
• ✅ For > n/2: 1 candidate, for > n/3: 2 candidates, for > n/k: k-1 candidates
• ✅ Alternative: HashMap O(n) space for exact counts

---

1-2-2) Frequency Array + Running Count

Concept:

• Track element occurrences using a frequency array (when values are bounded, e.g., 1 to n)
• Use array index as hash key for O(1) lookups
• Maintain a running count that updates as conditions are met
• Key Insight: When frequency reaches a threshold, trigger an action

When to Use:

• Values are bounded/constrained (e.g., permutations with values 1 to n)
• Need to track “seen in both” or “appeared k times” conditions
• Prefix-based counting problems
• Real-time/streaming count updates

Related: Useful for permutation problems, prefix arrays, and intersection counting.

---

Pattern: Prefix Common Array (LC 2657)

Problem: Given two permutations A and B of length n, find C where C[i] = count of numbers present at or before index i in both A and B.

Algorithm:

• Use frequency array of size n+1 (since values are 1 to n)
• For each index, process A[i] and B[i]
• When any element’s frequency reaches 2, it’s common (seen in both arrays)
• Increment running count and store in 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;
}

Example Trace: A = [1,3,2,4], B = [3,1,2,4]

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 Pattern: Frequency Threshold Detection

Use this pattern when you need to detect when elements reach a specific count threshold:

// 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...
    }
}

---

Frequency Array + Running Count: Common Mistakes & Tips

🚫 Common Mistakes:

1. Wrong Array Size

   // ❌ WRONG: Off-by-one for 1-indexed values
   int[] frequency = new int[n];  // Can't access frequency[n]
   
   // ✅ CORRECT: Size n+1 for values 1..n
   int[] frequency = new int[n + 1];
   

2. Checking Threshold Before Increment

   // ❌ WRONG: Check before increment misses the transition
   if (frequency[x] == 2) count++;
   frequency[x]++;
   
   // ✅ CORRECT: Increment first, then check
   frequency[x]++;
   if (frequency[x] == 2) count++;
   

3. Not Handling Same Element in Both Arrays at Same Index

   // For A[i] == B[i] case, frequency goes 0→1→2 in same iteration
   // This is handled correctly by processing A[i] then B[i] separately
   

💡 Interview Tips:

1. When to Use:

   • “Permutation” or “values 1 to n” keywords
   • “Prefix” or “running” count requirements
   • “Common elements” or “intersection” problems
   • Need O(1) lookup with bounded values

2. Talking Points:

   • “Array index as hash key gives O(1) lookup”
   • “Frequency threshold detection for condition triggers”
   • “Running count avoids recomputation”

3. Complexity:

   • Time: O(n) single pass
   • Space: O(n) or O(max_value) for frequency array

---

Related LeetCode Problems:

Problem	Difficulty	Pattern Variant
LC 2657	Medium	Prefix common array (frequency == 2)
LC 349	Easy	Intersection of two arrays (frequency >= 1 in both)
LC 350	Easy	Intersection with duplicates
LC 442	Medium	Find duplicates (frequency == 2, in-place)
LC 448	Easy	Find missing numbers (frequency == 0)
LC 645	Easy	Set mismatch (frequency == 2 and == 0)
LC 1	Easy	Two Sum (complement frequency check)
LC 217	Easy	Contains duplicate (frequency >= 2)

---

Summary:

• ✅ Frequency Array: Use array index as hash for bounded values (O(1) lookup)
• ✅ Running Count: Maintain cumulative count, update on threshold
• ✅ Key Insight: frequency[x] == k means x appeared k times across sources
• ✅ Best for: Permutations, prefix problems, intersection counting
• ✅ Alternative: HashMap for unbounded/sparse values

---

2) LC Example

2-1) Queue Reconstruction by Height

# LC 406 Queue Reconstruction by Height
class Solution(object):
    def reconstructQueue(self, people):
        people.sort(key = lambda x : (-x[0], x[1]))
        res = []
        for p in people:
        """
        py insert syntax
        # syntax : 
        # python_trick.html#1-6-insert-into-array-in-place

        # arr.insert(<index>,<value>)
        """
            res.insert(p[1], p)
        return res

2-2) Product of Array Except Self

# 238 Product of Array Except Self
# IDEA : 
# SINCE output[i] = (x0 * x1 * ... * xi-1) * (xi+1 * .... * xn-1)
# -> SO DO A 2 LOOP
# -> 1ST LOOP : GO THROGH THE ARRAY (->) : (x0 * x1 * ... * xi-1)
# -> 2ND LOOP : GO THROGH THE ARRAY (<-) : (xi+1 * .... * xn-1)
# e.g.
# given [1,2,3,4], return [24,12,8,6].
# -> output = [2*3*4, 1,1,1]  <-- 2*3*4    (right of 1: 2,3,4)
# -> output = [2*3*4, 1*3*4,1,1] <-- 1*3*4 (left of 2 :1, right of 2: 3,4)
# -> output = [2*3*4, 1*3*4,1*2*4,1] <-- 1*2*4 (left of 3: 1,2 right of 3 : 4)
# -> output = [2*3*4, 1*3*4,1*2*4,1*2*3] <-- 1*2*3 (left of 4 : 1,2,3)
# -> final output  = [2*3*4, 1*3*4,1*2*4,1*2*3] = [24,12,8,6]
class Solution:
    def productExceptSelf(self, nums):
        size = len(nums)
        output = [1] * size
        left = 1
        for x in range(size - 1):
            left *= nums[x]
            output[x + 1] *= left
        right = 1
        for x in range(size - 1, 0, -1):
            right *= nums[x]
            output[x - 1] *= right
        return output

2-3) Maximum Swap

# 670 Maximum Swap
class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        # BE AWARE OF IT 
        digits = list(str(num))
        left, right = 0, 0
        max_idx = len(digits)-1
        for i in range(len(digits))[::-1]:
            # BE AWARE OF IT 
            if digits[i] > digits[max_idx]:
                max_idx = i
            # BE AWARE OF IT  
            # if current digit > current max digit -> swap them 
            elif digits[max_idx] > digits[i]:
                left, right = i, max_idx        # if current max digit > current digit -> save current max digit to right idnex, and save current index to left
        digits[left], digits[right] = digits[right], digits[left] # swap left and right when loop finished 
        return int("".join(digits))

2-7) Best Time to Buy and Sell Stock

# LC 121 Best Time to Buy and Sell Stock
# V0
# IDEA : array op + problem understanding
class Solution(object):
    def maxProfit(self, prices):
        if len(prices) == 0:
            return 0
        ### NOTE : we define 1st minPrice as prices[0]
        minPrice = prices[0]
        maxProfit = 0
        ### NOTE : we only loop prices ONCE
        for p in prices:
            # only if p < minPrice, we get minPrice
            if p < minPrice:
                minPrice = p
            ### NOTE : only if p - minPrice > maxProfit, we get maxProfit
            elif p - minPrice > maxProfit:
                maxProfit = p - minPrice
        return maxProfit

2-8) Bulb Switcher III

# LC 1375. Bulb Switcher III
# V0
class Solution:
    def numTimesAllBlue(self, light):
        max_bulb_ind = 0
        count = 0
        turnedon_bulb = 0
        
        for bulb in light:
            max_bulb_ind = max(max_bulb_ind,bulb)
            turnedon_bulb += 1
            if turnedon_bulb == max_bulb_ind:
                count += 1
        
        return count

2-9) Robot Bounded In Circle

# LC 1041. Robot Bounded In Circle
# V0
# IDEA : math + array
class Solution:
    def isRobotBounded(self, instructions):
        """
        NOTE !!! we make direction as below

         c == 'L':  move LEFT : [0,-1]
         c == 'R':  move RIGHT : [0,1]
        """
        dirs = [[0,1], [1,0], [0,-1], [-1,0]]
        x = 0;
        y = 0;
        idx = 0;
        for c in instructions:
            print ("c = " + str(c) + " idx = " + str(idx))
            """
            NOTE !!! since we need to verify if robot back to start point
                -> we use (idx + k)  % 4 for detecting cyclic cases
            """
            if c == 'L':
                idx = (idx + 3) % 4
            elif c == 'R':
                idx = (idx + 1) % 4
            elif c == 'G':
                x = x + dirs[idx][0]
                y = y + dirs[idx][1]
        return (x == 0 and y ==0) or idx !=0

2-10) Maximum Length of Subarray With Positive Product

# LC 1567 Maximum Length of Subarray With Positive Product

# V0
class Solution:
    def getMaxLen(self, nums):
        first_neg, zero = None, -1
        mx = neg = 0
        for i,v in enumerate(nums):
            if v == 0:
                first_neg, zero, neg = None, i, 0
                continue
            if v < 0:
                neg += 1
                if first_neg == None:
                    first_neg = i
            j = zero if not neg % 2 else first_neg if first_neg != None else 10**9
            mx = max(mx, i-j)
        return mx

# V0'
# IDEA : 2 POINTERS
class Solution:
    def getMaxLen(self, nums):
        res = 0
        k = -1 # most recent 0
        j = -1 # first negative after most recent 0
        cnt = 0 # count of negatives after most recent 0
        for i, n in enumerate(nums):
            if n == 0:
                k = i
                j = i
                cnt = 0
            elif n < 0:
                cnt += 1
                if cnt % 2 == 0:
                    res = max(res, i - k)
                else:
                    if cnt == 1:
                        j = i
                    else:
                        res = max(res, i - j)        
            else:
                if cnt % 2 == 0:
                    res = max(res, i - k)
                else:
                    res = max(res, i - j)
        return res

2-11) Corporate Flight Bookings

# LC 1109. Corporate Flight Bookings
# V1
# IDEA : ARRAY + prefix sum
# https://leetcode.com/problems/corporate-flight-bookings/discuss/328856/JavaC%2B%2BPython-Sweep-Line
# IDEA :
# Set the change of seats for each day.
# If booking = [i, j, k],
# it needs k more seat on ith day,
# and we don't need these seats on j+1th day.
# We accumulate these changes then we have the result that we want.
# Complexity
# Time O(booking + N) for one pass on bookings
# Space O(N) for the result
class Solution:
    def corpFlightBookings(self, bookings, n):
        res = [0] * (n + 1)
        for i, j, k in bookings:
            res[i - 1] += k
            res[j] -= k
        for i in range(1, n):
            res[i] += res[i - 1]
        return res[:-1]

# V1''
# IDEA : ARRAY
# https://leetcode.com/problems/corporate-flight-bookings/discuss/328893/Short-python-solution
# IDEA : Simply use two arrays to keep track of how many bookings are added for every flight.
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:        
        opens = [0]*n
        closes = [0]*n
        
        for e in bookings:
            opens[e[0]-1] += e[2]
            closes[e[1]-1] += e[2]
            
        ret, tmp = [0]*n, 0
        for i in range(n):
            tmp += opens[i]
            ret[i] = tmp
            tmp -= closes[i]
            
        return ret

2-12) First Missing Positive

# LC 41. First Missing Positive
# V1'
# IDEA :  Index as a hash key.
# https://leetcode.com/problems/first-missing-positive/solution/
# /doc/pic/first-missing-positive.png
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        # Base case.
        if 1 not in nums:
            return 1

        # Replace negative numbers, zeros,
        # and numbers larger than n by 1s.
        # After this convertion nums will contain
        # only positive numbers.
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = 1

        # Use index as a hash key and number sign as a presence detector.
        # For example, if nums[1] is negative that means that number `1`
        # is present in the array.
        # If nums[2] is positive - number 2 is missing.
        for i in range(n):
            a = abs(nums[i])
            # If you meet number a in the array - change the sign of a-th element.
            # Be careful with duplicates : do it only once.
            if a == n:
                nums[0] = - abs(nums[0])
            else:
                nums[a] = - abs(nums[a])

        # Now the index of the first positive number
        # is equal to first missing positive.
        for i in range(1, n):
            if nums[i] > 0:
                return i

        if nums[0] > 0:
            return n

        return n + 1

// java
// LC 41. First Missing Positive
// V0
// IDEA: CYCLIC SORT
/**
 * Cyclic Sort Pattern:
 * Place each positive number x at its "correct" index (x - 1)
 *
 * Key idea:
 * - For a valid positive integer x (1 <= x <= n), it should be at index x-1
 * - Example: number 3 should be at nums[2], number 1 should be at nums[0]
 *
 * Algorithm:
 * 1. For each position i, keep swapping nums[i] to its correct position
 *    until nums[i] is already at the right place or out of range
 * 2. After sorting, scan for the first index i where nums[i] != i + 1
 * 3. That index + 1 is the first missing positive
 *
 * Example: nums = [3, 4, -1, 1]
 * Step 1: Place 3 at index 2 → [-1, 4, 3, 1]
 * Step 2: Place 4 at index 3 → [-1, 1, 3, 4]
 * Step 3: Place 1 at index 0 → [1, -1, 3, 4]
 * Step 4: Scan → nums[1] = -1 ≠ 2, return 2
 *
 * Time: O(N) - each element is swapped at most once
 * Space: O(1) - in-place sorting
 */
public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // 1. "Cyclic Sort": Place each number x at index x - 1
    // Example: nums[i] = 3 should be at nums[2]
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            // Swap nums[i] with the element at its target index
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }

    // 2. Scan for the first index where the number is wrong
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1; // Found the missing positive!
        }
    }

    // 3. If all numbers 1 to n are present, the answer is n + 1
    return n + 1;
}

2-13) Increasing Triplet Subsequence

# LC 334 Increasing Triplet Subsequence
# V0
# IDEA : MAINTAIN var first, second
#        AND GO THROUGH nums to check if there exists x (on the right hand side of a, b )
#        such that x > second > first
class Solution(object):
    def increasingTriplet(self, nums):
        """
        NOTE !!! we init first, second as POSITIVE float('inf')
        """
        first = float('inf')
        second = float('inf')
        # loop with normal ordering
        for num in nums:
            if num <= first:     # min num
                first = num
            elif num <= second:  # 2nd min num
                second = num
            else:                # 3rd min num
                return True      
        return False

2-14) First Missing Positive

# LC 41. First Missing Positive
# V0
# IDEA : for loop + while loop + problem understanding
class Solution:
    def firstMissingPositive(self, nums):
        for i, n in enumerate(nums):
            if n < 0:
                continue
            else:
                while n <= len(nums) and n > 0:
                    tmp = nums[n-1]
                    nums[n-1] = float('inf')
                    n = tmp
        for i in range(len(nums)):
            if nums[i] != float('inf'):
                return i+1
            
        return len(nums)+1

2-15) Rotate Array

# LC 189. Rotate Array
# V0
# IDEA : pop + insert
class Solution(object):
    def rotate(self, nums, k):
        _len = len(nums)
        k = k % _len
        while k > 0:
            tmp = nums.pop(-1)
            nums.insert(0, tmp)
            k -= 1

# V0'
# IDEA : SLICE (in place)
class Solution(object):
    def rotate(self, nums, k):
        # edge case
        if k == 0 or not nums or len(nums) == 1:
            return nums
        ### NOTE this
        k = k % len(nums)
        if k == 0:
            return nums
        """
        NOTE this !!!!
        """
        nums[:k], nums[k:] = nums[-k:], nums[:-k]
        return nums

// java
// LC 189. Rotate Array
// V0
// IDEA: REVERSE ARRAY (3-reverse trick)
/**
 * The 3-reverse trick:
 * 1. Reverse the entire array
 * 2. Reverse the first k elements
 * 3. Reverse the remaining elements
 *
 * Example: nums = [1,2,3,4,5,6,7], k = 3
 * Step 1: Reverse entire array → [7,6,5,4,3,2,1]
 * Step 2: Reverse first k=3 elements → [5,6,7,4,3,2,1]
 * Step 3: Reverse remaining elements → [5,6,7,1,2,3,4]
 *
 * Time: O(N) - each element is reversed twice
 * Space: O(1) - in-place rotation
 */
public void rotate(int[] nums, int k) {
    if (nums == null || nums.length <= 1)
        return;

    int n = nums.length;
    // Step 1: Handle cases where k > n
    k = k % n;
    if (k == 0)
        return;

    // Step 2: Apply the 3-reverse trick
    // 1. Reverse the whole array
    reverse(nums, 0, n - 1);
    // 2. Reverse the first k elements (0 to k-1)
    reverse(nums, 0, k - 1);
    // 3. Reverse the rest (k to n-1)
    reverse(nums, k, n - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

2-16) Flatten 2D Vector

# LC 251. Flatten 2D Vector
# V0
# IDEA : ARRAY OP
class Vector2D:

    def __init__(self, v):
        # We need to iterate over the 2D vector, getting all the integers
        # out of it and putting them into the nums list.
        self.nums = []
        for inner_list in v:
            for num in inner_list:
                self.nums.append(num)
        # We'll keep position 1 behind the next number to return.
        self.position = -1

    def next(self):
        # Move up to the current element and return it.
        self.position += 1
        return self.nums[self.position]

    def hasNext(self):
        # If the next position is a valid index of nums, return True.
        return self.position + 1 < len(self.nums)

2-17) Maximize Distance to Closest Person

// java
// LC 849. Maximize Distance to Closest Person

// V0-1
// IDEA (fixed by gpt)
/**
*  IDEA :
*
*  Explanation of the Code:
*    1.  Initial Setup:
*        •   lastOccupied keeps track of the index of the last seat occupied by a person.
*        •   maxDistance is initialized to 0 to store the maximum distance found.
*
*    2.  Iterate Through the Array:
*        •   When a seat is occupied (seats[i] == 1):
*        •   If it’s the first occupied seat, calculate the distance from the start of the array to this seat (i).
*        •   Otherwise, calculate the middle distance between the current and the last occupied seat using (i - lastOccupied) / 2.
*
*    3.  Check the Last Segment:
*        •   If the last seat is empty, calculate the distance from the last occupied seat to the end of the array (seats.length - 1 - lastOccupied).
*
*    4.  Return the Maximum Distance:
*        •   The value of maxDistance at the end of the loop is the answer.
*
*
* Example :
*  input : seats = [1, 0, 0, 0, 1, 0, 1]
*
*   Execution Steps:
*    1.  First occupied seat at index 0 → Distance to start = 0.
*    2.  Second occupied seat at index 4 → Middle distance = (4 - 0) / 2 = 2.
*    3.  Third occupied seat at index 6 → Middle distance = (6 - 4) / 2 = 1.
*    4.  No empty seats after the last occupied seat.
*    5.  maxDistance = 2.
*
*  output:  2
*
*/
/**
*  Cases
*
*  Case 1)  0001  ( all "0" till meat first "1")
*  Case 2)  1001001 (all "0" are enclosed by "1")
*  Case 3)  1001000 (there are "0" that NOT enclosed by "1" on the right hand side)
*
*/
public int maxDistToClosest_0_1(int[] seats) {
    int maxDistance = 0;
    int lastOccupied = -1;

    // Traverse the array to calculate maximum distances
    for (int i = 0; i < seats.length; i++) {
        /** NOTE !!! handle the seat val == 1 cases */
        if (seats[i] == 1) {
            if (lastOccupied == -1) {
                // Handle the case where the `first` occupied seat is found
                /**
                 * NOTE !!!
                 *
                 *  for handling below case:
                 *
                 *    e.g. :  0001
                 *
                 *  (so, elements are all "0" till first visit "1")
                 *  in this case, we still can get put a person to seat, and get distance
                 *
                 */
                maxDistance = i; // Distance from the start to the first occupied seat
            } else {
                // Calculate the distance to the closest person for the middle segment
                /** NOTE !!! need to divided by 2, since the person need to seat at `middle` seat */
                maxDistance = Math.max(maxDistance, (i - lastOccupied) / 2);
            }
            lastOccupied = i;
        }
    }

    // Handle the case where the last segment is empty
   /**
    *  NOTE !!!
    *
    *   the condition is actually quite straightforward,
    *   just need to check if the last element in array is "0"
    *   if is "0", means the array is NOT enclosed by "1"
    *   then we need to handle such case
    *   (example as below)
    *
    *   e.g.  100010000
    *
    */
    if (seats[seats.length - 1] == 0) {
        maxDistance = Math.max(maxDistance, seats.length - 1 - lastOccupied);
    }

    return maxDistance;
}