We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Array into Disjoint Intervals

Number: 951

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers, partition it into two contiguous subarrays, left and right, such that every element in left is less than or equal to every element in right. Both subarrays must be non-empty, and left should have the smallest possible size. The task is to return the length of left after the partitioning.

Key Insights

  • The partition point can be determined by tracking the maximum value in the left part and the minimum value required for the right part.
  • Iterate through the array while maintaining the maximum seen so far (curMax) and a candidate partition index (partitionIdx).
  • When encountering an element that is less than the maximum of the left part (maxLeft), update the partition index so that it includes this element, ensuring that left contains all elements that could violate the condition.
  • A single pass solution with O(n) time complexity and O(1) space can be achieved by using just a few tracking variables.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves a single pass through the array using three variables:

  1. curMax: Tracks the maximum element seen so far across the entire array.
  2. maxLeft: Tracks the maximum element in the left partition.
  3. partitionIdx: The current candidate for the partition index.

Start by initializing maxLeft and curMax with the first element of the array. Then, iterate from the second element to the end. For each element:

  • If the current element is less than maxLeft, it means the partition must include this element, so update partitionIdx and also update maxLeft with curMax.
  • Otherwise, update curMax if the current element is greater.

At the end, partitionIdx + 1 gives the length of the left subarray.

Code Solutions

# Python solution with line-by-line comments

def partitionDisjoint(nums):
    # Initialize:
    # max_left: Maximum value within the 'left' partition.
    # cur_max: The maximum value found so far in the entire array.
    # partition_idx: The index at which we partition the array.
    max_left = nums[0]
    cur_max = nums[0]
    partition_idx = 0

    # Iterate over the array starting from index 1
    for i in range(1, len(nums)):
        # Update the global maximum so far
        cur_max = max(cur_max, nums[i])
        # If the current element is less than max_left,
        # it violates the condition, so update partition index.
        if nums[i] < max_left:
            partition_idx = i
            # Update max_left to be the current global maximum
            max_left = cur_max
    # The length of the left partition is partition_idx + 1
    return partition_idx + 1

# Example usage:
nums = [5, 0, 3, 8, 6]
print(partitionDisjoint(nums))  # Output: 3
← Back to All Questions