Partition Array into Disjoint Intervals

Medium
363.

Partition Array into Disjoint Intervals

Partition Array into Disjoint Intervals is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.

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

  • every element of left is less than or equal to every element of right;
  • both parts are non-empty;
  • left is as short as possible.

Return the length of left. A valid split is guaranteed to exist.

Example 1

Input
nums = [5,0,3,8,6]
Output
3
Explanation
left = [5,0,3], right = [8,6].

Example 2

Input
nums = [1,1,1,0,6,12]
Output
4

Example 3

Input
nums = [1,2]
Output
1

Constraints

  • 2 <= nums.length <= 40
  • 0 <= nums[i] <= 1000
  • A valid partition exists.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition Array into Disjoint Intervals — Problem & Solution

Partition Array into Disjoint Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Partition Array into Disjoint Intervals is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

  • every element of left is less than or equal to every element of right;
  • both parts are non-empty;
  • left is as short as possible.

Return the length of left. A valid split is guaranteed to exist.

Example 1

Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6].

Example 2

Input: nums = [1,1,1,0,6,12]
Output: 4

Example 3

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

Constraints

  • 2 <= nums.length <= 40
  • 0 <= nums[i] <= 1000
  • A valid partition exists.

Hints for Partition Array into Disjoint Intervals

  1. Hint 1

    Track two maxima: the maximum of the committed left part, and the maximum seen so far overall.

  2. Hint 2

    Any element smaller than the left maximum forces the cut to move past it.

  3. Hint 3

    When that happens, the left part absorbs everything up to here, so its maximum becomes the running overall maximum.

How to solve Partition Array into Disjoint Intervals

Track the max of the committed left part and the max seen so far; any element smaller than the left max forces the cut past it, at which point the left max becomes the overall max.

Approach

  1. Start leftMax = curMax = nums[0], cut = 1.
  2. For each i: update curMax; if nums[i] < leftMax, set leftMax = curMax and cut = i + 1.
  3. Return cut.

Why it works

The cut must be after every element smaller than something before it; when such an element is found, everything up to it joins the left part, whose max is then the running max. The last such event fixes the shortest valid left.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The alternative uses prefix-max and suffix-min arrays and returns the first i with prefixMax[i] <= suffixMin[i+1].

Reference solution

Python

def partitionDisjoint(nums) -> int:
    left_max = cur_max = nums[0]
    cut = 1
    for i in range(1, len(nums)):
        cur_max = max(cur_max, nums[i])
        if nums[i] < left_max:
            left_max = cur_max
            cut = i + 1
    return cut

Java

public static int partitionDisjoint(int[] nums) {
    int leftMax = nums[0], curMax = nums[0], cut = 1;
    for (int i = 1; i < nums.length; i++) {
        curMax = Math.max(curMax, nums[i]);
        if (nums[i] < leftMax) {
            leftMax = curMax;
            cut = i + 1;
        }
    }
    return cut;
}

C++

int partitionDisjoint(vector<int>& nums) {
    int leftMax = nums[0], curMax = nums[0], cut = 1;
    for (int i = 1; i < (int) nums.size(); i++) {
        curMax = max(curMax, nums[i]);
        if (nums[i] < leftMax) {
            leftMax = curMax;
            cut = i + 1;
        }
    }
    return cut;
}

JavaScript

var partitionDisjoint = function(nums) {
    let leftMax = nums[0], curMax = nums[0], cut = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > curMax) curMax = nums[i];
        if (nums[i] < leftMax) {
            leftMax = curMax;
            cut = i + 1;
        }
    }
    return cut;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms