Minimum Index of a Valid Split - Practice Coding Problems

Minimum Index of a Valid Split - Problem

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.

Return the minimum index of a valid split. If no valid split exists, return -1.

Input & Output

Example 1 — Basic Valid Split

$ Input: nums = [10,5,2,10,10]

› Output: 2

💡 Note: Split at index 2: left=[10,5,2] has dominant 10 (count=1 > 3/2), right=[10,10] has dominant 10 (count=2 > 2/2). Both parts have the same dominant element 10.

Example 2 — No Valid Split

$ Input: nums = [2,1,3,1,1,1,7,1,2,1]

› Output: -1

💡 Note: The dominant element is 1 (appears 6 times > 10/2). However, no split position creates two parts where 1 is dominant in both parts simultaneously.

Example 3 — Early Valid Split

$ Input: nums = [3,3,3,3,7,2,2]

› Output: 0

💡 Note: Split at index 0: left=[3] has dominant 3, right=[3,3,3,7,2,2] has dominant 3 (count=3 > 6/2). Valid split found at the earliest possible position.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
nums has exactly one dominant element

Visualization

Tap to expand

Understanding the Visualization

Input Array

[10,5,2,10,10] with dominant element 10 (appears 3 > 5/2 times)

Find Valid Split

Try split positions until both parts have same dominant element

Return Index

Minimum valid split index is 2

Key Takeaway

🎯 Key Insight: The array's dominant element must be the dominant element in both split parts

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that the dominant element of the entire array must remain dominant in both parts of any valid split. The optimal approach tracks the count of the dominant element incrementally as we try each split position. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Precompute with Single Pass	O(n²)	O(n)	Track counts incrementally to avoid recounting elements
Brute Force - Check All Splits	O(n²)	O(1)	Try every split position and verify dominance in both parts

Optimized - Precompute with Single Pass — Algorithm Steps

Find the dominant element of the entire array
Initialize right counts with all elements
For each split position, move one element from right to left
Update counts and check if the dominant element is majority in both parts
Return first valid split index

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Find dominant element (10), start with all on right

Move Split

Move elements from right to left, update counts

Check Validity

When dominant is majority in both parts, return index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n < 2) return -1;
    
    // Find dominant element of entire array
    int dominant = -1;
    int maxCount = 0;
    
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count > n / 2 && count > maxCount) {
            dominant = nums[i];
            maxCount = count;
        }
    }
    
    if (dominant == -1) return -1;
    
    // Initialize counts
    int leftCount = 0;
    int rightCount = maxCount;
    
    // Try each split position
    for (int i = 0; i < n - 1; i++) {
        // Add current element to left part
        if (nums[i] == dominant) {
            leftCount++;
            rightCount--;
        }
        
        // Check if dominant element is majority in both parts
        int leftSize = i + 1;
        int rightSize = n - i - 1;
        
        if (leftCount > leftSize / 2 && rightCount > rightSize / 2) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strspn(token, " \t\n\r") != strlen(token)) {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each split position, we may need to check all unique elements to find dominants

⚠ Quadratic Growth

Space Complexity

O(n)

Hash maps to store element counts for left and right parts

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Precompute with Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler