Partition Array into Disjoint Intervals

LeetCode 915, Medium. Topics: Array. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 915   # by problem number
lcpy gen -s partition_array_into_disjoint_intervals   # by problem name

Problem

Given an integer array <code>nums</code>, partition it into two (contiguous) subarrays <code>left</code> and <code>right</code> so that: <ul> <li>Every element in <code>left</code> is less than or equal to every element in <code>right</code>.</li> <li><code>left</code> and <code>right</code> are non-empty.</li> <li><code>left</code> has the smallest possible size.</li> </ul> Return the length of <code>left</code> after such a partitioning. Test cases are generated such that partitioning exists.

Examples

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

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

Constraints

2 <= nums.length <= 10^5
0 <= nums[i] <= 10^6
There is at least one valid answer for the given input.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def partition_disjoint(self, nums: list[int]) -> int:
        length = 1
        left_max = nums[0]
        cur_max = nums[0]
        for i in range(1, len(nums)):
            cur_max = max(cur_max, nums[i])
            if nums[i] < left_max:
                left_max = cur_max
                length = i + 1
        return length

Complexity

Time	Space
O(n)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Partition Array into Disjoint Intervals

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags