2780. Minimum Index of a Valid Split

## Problem https://leetcode.com/problems/minimum-index-of-a-valid-split/description/ :::spoiler **Optimal Space & Time Complexity** ``` - Time complexity: O(n) where n is arr.length - Space complexity: O(1) ``` ::: <hr/> ## Solutions :::spoiler 東 ```javascript= ``` ::: :::spoiler Hao ```javascript= ``` ::: :::spoiler YC ```javascript= ``` ::: :::spoiler SOL ```javascript= ``` ::: --- ## Supplement / Discussion ### 東 ### Hao [[Javascript] Boyer-Moore Voting Algorithm](https://leetcode.com/problems/minimum-index-of-a-valid-split/solutions/3771218/javascript-boyer-moore-voting-algorithm/) 1. If a number is the majority element on the left and right arrays, that means it is the majority element in the overall array. - Therefore, we only need to find the majority element on the overall array, then count the occurance of this element on the left and right arrays for each split. - Intuitive: Hash table, space complexity O(n) - **Optimal: Boyer-Moore Majority Voting Algorithm, space complexity O(1)** 2. Return the first index of a split where both the left and right arrays have the majority element equal to the overall majority element. [Note 1] We could also employ a `runningFlags` to record the amount of the majority in `subArray(0, n)` ([reference](https://leetcode.com/problems/minimum-index-of-a-valid-split/solutions/3782558/javascript-o-n-space-and-time/)) ### YC ### SOL