Max Partition

Problem Statement

A partition of an array is a set of indices that separate the array into sub-arrays. For a given partition, if sorting each sub-array in-place sorts the entire array, we call it a sorted partition.

Given an array arr of length n, write a function to calculate the largest number of sub-arrays of any sorted partition of arr.

Example 1: For arr = [1,2,3,5], max_function should return 4, as we have the max sorted partition of [1], [2], [3], [5].

Example 2: For arr = [3,4,1,7,9,8], max_function should return 3, as we have the max sorted partition of [3,4,1], [7], [9,8].

Test Cases

Test 1

Input: [1,2,3,4,5,6,7]
Output: 7

Test 2

Input: [7,6,5,4,3,2,1]
Output: 1

Test 3

Input: [5,6,4,7,6,9,9,9,9,9,9,10,13,21,13]
Output: 11

Starter Code

# returns the size of the maximal sorted partition of arr.
def max_partition(arr):
    #your code here
    pass

Hints

Hint 1 (Click to reveal!)

What must be true for an index i to be a valid partition index? Try to come up with a naive solution first.

Hint 2 (Click to reveal!)

How might we dynamically store this information for each index to avoid redundant scans?

Solution

Click here!

An index is a valid partitioning index iff the maximum element before the index is less than or equal to the minimum element after the index. The maximal sorted partition uses all of these indices as split points. Therefore, the size of the maximal sorted partition is the number of valid partitioning indices.

Naive Solution

def max_partition(arr):
    partitions = 1
    n = len(arr)
    # Note that we go up to index i-1 because 
    # we don't partition at index n-1.
    for i in range(n-1):
        # Compare the max of the elements before index i
        # and the min of the elements after index i. If 
        # the former is smaller, we can partition at this
        # index, thus incrementing number of subarrays.
        if max(arr[0:i+1]) <= min(arr[i+1:n]):
            partitions += 1
    return partitions

This has runtime $O(n^2)$

Dynamic Solution

We dynamically store the “before max” and “after min” for each index in two arrays. The two arrays can be found with a forward scan and a backward scan of a, while keeping track of max_so_far and min_so_far.

def max_partition(arr):
    n = len(arr)
    # forward scan
    max_front = []
    max_so_far = float("-inf")
    for i in range(n):
        if arr[i] > max_so_far:
            max_so_far = arr[i]
        max_front.append(max_so_far)


    # backward scan
    min_back = []
    min_so_far = float("inf")
    for i in range(n-1):
        if arr[n-i-1] < min_so_far: 
            min_so_far = arr[n-i-1]
        # this inserts to the front, as we're scanning backwards
        min_back.insert(0, min_so_far)

    # Now we do a forward scan, and for each index whose before max
    # is smaller than its after min, we increment number of subarrays by 1.
    partitions = 1
    # Note that when we say partition at index i, we divide the array at i,
    # incrementing the number of subarrays by 1. Thus, it doesn't make sense 
    # to partition on the last element since there're no elements after that. 
    for i in range(n-1):
        if max_front[i] <= min_back[i]:
            partitions += 1
    return partitions

This has runtime $O(n)$ and space complexity $O(n)$ . Time is saved by not needing to compute every maximum and minimum separately.