Leetcode: Partition Array into Disjoint Intervals

Partition Array into Disjoint Intervals



Similar Problems:


Given an array A, 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. It is guaranteed that such a partitioning exists.

Example 1:

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

Example 2:

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

Note:

  1. 2 <= A.length <= 30000
  2. 0 <= A[i] <= 10^6
  3. It is guaranteed there is at least one way to partition A as described.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/partition-array-into-disjoint-intervals
// Basic Ideas:
// max: maximum for the target left window
// global_max: maximum from the first element to the current one
//    If A[i] < max, we update max with global_max
// Complexity: Time O(n), Space O(1)
func partitionDisjoint(A []int) int {
    max, global_max, res := A[0], A[0], 1
    for i:= 1; i<len(A); i++ {
        if A[i] < max {
            max = global_max
            res = i+1
        } else {
           if A[i] > global_max { global_max = A[i] }
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.