MediumNo. 0915
Partition Array into Disjoint Intervals — LeetCode 915 Python Solution
- Topics
- Array
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- nums = [5,0,3,8,6]
- Output
- 3
- Explanation
- left = [5,0,3], right = [8,6]
Python solution
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 iComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
Frequently asked questions
- How hard is LeetCode 915. Partition Array into Disjoint Intervals?
LeetCode 915. Partition Array into Disjoint Intervals is rated Medium on LeetCode.
- What is the time complexity of LeetCode 915. Partition Array into Disjoint Intervals?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 915. Partition Array into Disjoint Intervals?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 915. Partition Array into Disjoint Intervals cover?
LeetCode 915. Partition Array into Disjoint Intervals is tagged Array on LeetCode.