#915

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Partition Array into Disjoint Intervals

Partition the array into two subarrays such that the left contains the smallest possible elements and the right contains the largest ones.

array

Problem Statement

You are given an integer array nums, and your task is to partition it into two contiguous subarrays, left and right, such that the largest element in the left subarray is strictly smaller than the smallest element in the right subarray.

Return the length of the left subarray after partitioning. It is guaranteed that at least one valid partition exists for the given input.

Examples

Example 1

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

Output: 3

left = [5,0,3], right = [8,6]

Example 2

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

Output: 4

left = [1,1,1,0], right = [6,12]

Constraints

2 <= nums.length <= 105
0 <= nums[i] <= 106
There is at least one valid answer for the given input.

Solution Approach

Array-driven Partitioning

Iterate through the array once while maintaining the current maximum in the left subarray and the minimum in the right subarray. By updating the left's maximum and the right's minimum in each step, find the point where the left subarray’s maximum is strictly less than the right subarray’s minimum.

Left-to-Right Pass

Perform a left-to-right pass while tracking the current maximum value of the left subarray. After each step, compare this maximum with the minimum value from the right subarray to decide the partition point.

Optimal Time Complexity

Since this solution processes the array in linear time, O(N), and uses constant space, O(1), it is optimal for large arrays up to the constraint size.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity of this approach is O(N), as it requires a single pass through the array to find the partition point. The space complexity is O(1), because only a few variables are needed to store intermediate results, such as the maximum of the left subarray and the minimum of the right subarray.

What Interviewers Usually Probe

Candidates should demonstrate proficiency with array-driven strategies and partitioning concepts.
Watch for clear reasoning in determining the partition point based on left and right subarray comparisons.
Efficient solutions with linear time complexity will be expected, especially for large input sizes.

Common Pitfalls or Variants

Common pitfalls

Not maintaining the left subarray's maximum or the right subarray's minimum properly during iteration.
Assuming the partition must be found at the first occurrence of an increasing element, without considering all array elements.
Overcomplicating the problem by using nested loops or extra space when a simple linear scan is sufficient.

Follow-up variants

Modify the problem to partition based on a different condition, such as comparing the sum of left and right subarrays.
Extend the problem to support multiple partitions within the array, resulting in more than two subarrays.
Change the partition condition so that the left subarray contains elements strictly greater than the right subarray.

FAQ

How do I solve the Partition Array into Disjoint Intervals problem efficiently?

Use an array-driven approach with a single pass to maintain the left subarray's maximum and the right subarray's minimum, ensuring linear time complexity.

What is the time complexity of the Partition Array into Disjoint Intervals problem?

The time complexity is O(N) because the solution involves a single scan through the array, where N is the size of the array.

How do I partition the array such that the left subarray has smaller elements than the right?

Track the maximum value of the left subarray and the minimum value of the right subarray while iterating from left to right, and partition when the condition is satisfied.

Are there any edge cases I should be aware of for this problem?

Edge cases include arrays where the partition is at the very beginning or end of the array, or arrays where all elements are the same value.

Can this problem be solved using a divide-and-conquer approach?

While divide-and-conquer may work, the most efficient approach for this problem is a linear scan, which ensures the best time complexity of O(N).

terminal

Solution

Solution 1: Prefix Maximum + Suffix Minimum

To satisfy the requirements of the problem after partitioning into two subarrays, we need to ensure that the "maximum value of the array prefix" is less than or equal to the "minimum value of the array suffix".

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        n = len(nums)
        mi = [inf] * (n + 1)
        for i in range(n - 1, -1, -1):
            mi[i] = min(nums[i], mi[i + 1])
        mx = 0
        for i, v in enumerate(nums, 1):
            mx = max(mx, v)
            if mx <= mi[i]:
                return i

Continue Practicing

#914 x of a kind in a deck of cards #916 word subsets #912 sort an array