Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:
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.
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 Explanation: left = [1,1,1,0], right = [6,12]
Constraints:
2 <= nums.length <= 1050 <= nums[i] <= 106This approach involves maintaining a running maximum for the left subarray and a suffix minimum for the right subarray. By iterating through the array and comparing these values, we can determine the appropriate partition point where all conditions are satisfied.
The C solution uses two variables, maxLeft and maxSoFar, to track the maximum values during the iteration through the array. Whenever we encounter an element smaller than maxLeft, it updates the partition index to that position and sets maxLeft to maxSoFar. This ensures all conditions of the partition are maintained.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - Linear scan of the array.
Space Complexity: O(1) - Only variables used for tracking, no extra storage required.
This approach involves using two additional arrays: one to track the maximum values until any index from the left and another to track minimum values from the right. These auxiliary arrays help determine where a valid partition can be made in the original array.
In this C solution, two arrays leftMax and rightMin are used to keep track of the maximum values up to an index and the minimum values from an index onward. By comparing elements from leftMax and rightMin, we determine the appropriate partition point.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - Needs three linear passes through the array.
Space Complexity: O(n) - Additional space for two auxiliary arrays.
| Approach | Complexity |
|---|---|
| Prefix and Suffix Tracking | Time Complexity: O(n) - Linear scan of the array. |
| Two Array Auxiliary Tracking | Time Complexity: O(n) - Needs three linear passes through the array. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,611 views views
Watch 9 more video solutions →Practice Partition Array into Disjoint Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor