2780. Minimum Index of a Valid Split Medium

1/**
2 * [2780] Minimum Index of a Valid Split
3 *
4 * An element x of an integer array arr of length m is dominant if freq(x) * 2 > m, where freq(x) is the number of occurrences of x in arr. Note that this definition implies that arr can have at most one dominant element.
5 * You are given a 0-indexed integer array nums of length n with one dominant element.
6 * You can split nums at an index i into two arrays nums[0, ..., i] and nums[i + 1, ..., n - 1], but the split is only valid if:
7 * 
8 * 	0 <= i < n - 1
9 * 	nums[0, ..., i], and nums[i + 1, ..., n - 1] have the same dominant element.
10 * 
11 * Here, nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j, both ends being inclusive. Particularly, if j < i then nums[i, ..., j] denotes an empty subarray.
12 * Return the minimum index of a valid split. If no valid split exists, return -1.
13 *  
14 * <strong class="example">Example 1:
15 * 
16 * Input: nums = [1,2,2,2]
17 * Output: 2
18 * Explanation: We can split the array at index 2 to obtain arrays [1,2,2] and [2]. 
19 * In array [1,2,2], element 2 is dominant since it occurs twice in the array and 2 * 2 > 3. 
20 * In array [2], element 2 is dominant since it occurs once in the array and 1 * 2 > 1.
21 * Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split. 
22 * It can be shown that index 2 is the minimum index of a valid split. 
23 * <strong class="example">Example 2:
24 * 
25 * Input: nums = [2,1,3,1,1,1,7,1,2,1]
26 * Output: 4
27 * Explanation: We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1].
28 * In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
29 * In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
30 * Both [2,1,3,1,1] and [1,7,1,2,1] have the same dominant element as nums, so this is a valid split.
31 * It can be shown that index 4 is the minimum index of a valid split.
32 * <strong class="example">Example 3:
33 * 
34 * Input: nums = [3,3,3,3,7,2,2]
35 * Output: -1
36 * Explanation: It can be shown that there is no valid split.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= nums.length <= 10^5
42 * 	1 <= nums[i] <= 10^9
43 * 	nums has exactly one dominant element.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/minimum-index-of-a-valid-split/
49// discuss: https://leetcode.com/problems/minimum-index-of-a-valid-split/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn minimum_index(nums: Vec<i32>) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2780() {
67    }
68}
69