Algorithm

Problem Name: 915. Partition Array into Disjoint Intervals

Problem Link: https://leetcode.com/problems/partition-array-into-disjoint-intervals/  
 

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.
  • 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 <= 105
  • 0 <= nums[i] <= 106
  • There is at least one valid answer for the given input.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const partitionDisjoint = function(A) {
    let n = A.length;
    let maxLeft = A[0];
    let minRight = new Int32Array(n);
    let min = Infinity;
    for (let i = n - 1; i >= 1; i--) {
        min = Math.min(min, A[i]);
        minRight[i] = min;
   }
   
   for(let i = 1; i  <  n; i++){
       if (maxLeft <= minRight[i]){
           return i;
       }

       maxLeft = Math.max(maxLeft, A[i]);               
   }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [5,0,3,8,6]

Output

x
–
+
cmd
3

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def partitionDisjoint(self, A):
        rMin, lMax, mx, mn = [0] * len(A), [0] * len(A), -float("inf"), float("inf")
        for i, num in enumerate(A):
            mx = max(mx, num)
            lMax[i] = mx 
        for i in range(len(A) - 1, -1, -1):
            mn = min(mn, A[i])
            rMin[i] = mn 
        for i in range(len(A) - 1):
            if lMax[i] <= rMin[i + 1]:
                return i + 1
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [5,0,3,8,6]

Output

x
–
+
cmd
3
Advertisements

Demonstration

Previous
#914 Leetcode X of a Kind in a Deck of Cards Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#916 Leetcode Word Subsets Solution in C, C++, Java, JavaScript, Python, C# Leetcode