2780. Minimum Index of a Valid Split LeetCode Solution
In this guide, you will get 2780. Minimum Index of a Valid Split LeetCode Solution with the best time and space complexity. The solution to Minimum Index of a Valid Split problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Index of a Valid Split
An element x of an integer array arr of length m is dominant if more than half the elements of arr have a value of x.
You are given a 0-indexed integer array nums of length n with one dominant element.
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:
0 <= i < n – 1
nums[0, …, i], and nums[i + 1, …, n – 1] have the same dominant element.
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.
Return the minimum index of a valid split. If no valid split exists, return -1.
Example 1:
Input: nums = [1,2,2,2]
Output: 2
Explanation: We can split the array at index 2 to obtain arrays [1,2,2] and [2].
In array [1,2,2], element 2 is dominant since it occurs twice in the array and 2 * 2 > 3.
In array [2], element 2 is dominant since it occurs once in the array and 1 * 2 > 1.
Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split.
It can be shown that index 2 is the minimum index of a valid split.
Example 2:
Input: nums = [2,1,3,1,1,1,7,1,2,1]
Output: 4
Explanation: We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1].
In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
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.
It can be shown that index 4 is the minimum index of a valid split.
Example 3:
Input: nums = [3,3,3,3,7,2,2]
Output: -1
Explanation: It can be shown that there is no valid split.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
nums has exactly one dominant element.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2780. Minimum Index of a Valid Split LeetCode Solution in C++
class Solution {
public:
int minimumIndex(vector<int>& nums) {
const int n = nums.size();
unordered_map<int, int> count1;
unordered_map<int, int> count2;
for (const int num : nums)
++count2[num];
for (int i = 0; i < n; ++i) {
const int freq1 = ++count1[nums[i]];
const int freq2 = --count2[nums[i]];
if (freq1 * 2 > i + 1 && freq2 * 2 > n - 1 - i)
return i;
}
return -1;
}
}; /* code provided by PROGIEZ */
2780. Minimum Index of a Valid Split LeetCode Solution in Java
class Solution {
public int minimumIndex(List<Integer> nums) {
final int n = nums.size();
Map<Integer, Integer> count1 = new HashMap<>();
Map<Integer, Integer> count2 = new HashMap<>();
for (final int num : nums)
count2.merge(num, 1, Integer::sum);
for (int i = 0; i < n; ++i) {
final int freq1 = count1.merge(nums.get(i), 1, Integer::sum);
final int freq2 = count2.merge(nums.get(i), -1, Integer::sum);
if (freq1 * 2 > i + 1 && freq2 * 2 > n - 1 - i)
return i;
}
return -1;
}
} // code provided by PROGIEZ
2780. Minimum Index of a Valid Split LeetCode Solution in Python
class Solution:
def minimumIndex(self, nums: list[int]) -> int:
count1 = collections.Counter()
count2 = collections.Counter(nums)
for i, num in enumerate(nums):
count1[num] = count1[num] + 1
count2[num] = count2[num] - 1
if count1[num] * 2 > i + 1 and count2[num] * 2 > len(nums) - i - 1:
return i
return -1 # code by PROGIEZ
