Minimum Index of a Valid Split - Boyer-Moore Voting Algorithm [JS]
Description Solution: Boyer-Moore Voting Algorithm 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. Return the first index of a split where both the left and right arrays have the majority element equal to the overall majority element. Time Complexity: O(n) Space Complexity: O(1) var minimumIndex = function ( nums ) { let n = nums.length, count = 0 , majority; for ( let i = 0 ; i < n; i++) { if (count === 0 ) majority = nums[i]; if (nums[i] === majority) count++; else count--; } let majorityCount = nums.reduce( ( res, num ) => res + (num === majority ? 1 : 0 ), 0 ); let leftCount = 0 ; for ( let i = 0 ; i < n - 1 ; i++) { if (nums[i] === majority) leftCount++; let rightCount = ma...