Partition Array into Disjoint Intervals - Practice Coding Problems

Partition Array into Disjoint Intervals - Problem

Array Medium

Given an integer array nums, partition it into two contiguous subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning.

Test cases are generated such that partitioning exists.

Input & Output

Example 1 — Basic Partition

$ Input: nums = [5,0,3,8,6]

› Output: 3

💡 Note: Partition into left=[5,0,3] and right=[8,6]. Max of left is 5, min of right is 6. Since 5 ≤ 6, this is valid. Length of left is 3.

Example 2 — All Left Except Last

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

› Output: 3

💡 Note: Partition into left=[1,1,1] and right=[2]. Max of left is 1, min of right is 2. Since 1 ≤ 2, this is valid. Length of left is 3.

Example 3 — Minimum Valid Partition

$ Input: nums = [1,2]

› Output: 1

💡 Note: Partition into left=[1] and right=[2]. Max of left is 1, min of right is 2. Since 1 ≤ 2, this is valid. Length of left is 1.

Constraints

2 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [5,0,3,8,6] needs valid partition

Find Partition

Check where max(left) ≤ min(right)

Output Length

Return length of left partition: 3

Key Takeaway

🎯 Key Insight: The optimal partition minimizes left size while ensuring max(left) ≤ min(right)

Asked in

G Google 42 f Facebook 38 M Microsoft 31 a Amazon 29

The key insight is to find the minimum partition point where max(left) ≤ min(right). Best approach uses precomputed min_suffix array with single pass scanning. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Splits	O(n²)	O(1)	Try every possible partition point and verify the condition
Optimized Single Pass	O(n)	O(n)	Single pass with running maximum and precomputed minimum suffix
Two Pass - Precompute Max and Min	O(n)	O(n)	Precompute maximum prefix and minimum suffix arrays

Brute Force - Check All Splits — Algorithm Steps

Iterate through all possible partition points from 1 to n-1
For each split, find max in left subarray and min in right subarray
Check if max(left) ≤ min(right), return first valid partition

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Split at i=1

Check if max([5]) ≤ min([0,3,8,6])

Try Split at i=2

Check if max([5,0]) ≤ min([3,8,6])

Found Valid Split

max([5,0,3]) = 5 ≤ min([8,6]) = 6

Code -

solution.c — C

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

int solution(int* nums, int n) {
    for (int i = 1; i < n; i++) {
        int leftMax = INT_MIN;
        for (int j = 0; j < i; j++) {
            if (nums[j] > leftMax) {
                leftMax = nums[j];
            }
        }
        
        int rightMin = INT_MAX;
        for (int j = i; j < n; j++) {
            if (nums[j] < rightMin) {
                rightMin = nums[j];
            }
        }
        
        if (leftMax <= rightMin) {
            return i;
        }
    }
    
    return n - 1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        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 of n partition points, we scan O(n) elements to find max/min

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track max, min, and indices

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Brute Force - Check All Splits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler