Codility ‘MinMaxDivision’ Solution

Short Problem Definition:

Divide array A into K blocks and minimize the largest sum of any block.

Link

MinMaxDivision

Complexity:

expected worst-case time complexity is O(N*log(N+M));

expected worst-case space complexity is O(1)

Execution:

Binary search for the minimal size of a block. A valid block can be checked in a boolean fashion. Two special cases can be sped up (courtesy to CodeSays). At the time of writing (19.9.2014) do not use the variable passed to the solution function as M! It is NOT the maximum element in the test cases! The specification says, that no element is larger than M, yet there is not guarantee that M == max(A).

Solution:
def blockSizeIsValid(A, max_block_cnt, max_block_size):
    block_sum = 0
    block_cnt = 0

    for element in A:
        if block_sum + element > max_block_size:
            block_sum = element
            block_cnt += 1
        else:
            block_sum += element
        if block_cnt >= max_block_cnt:
            return False

    return True

def binarySearch(A, max_block_cnt, using_M_will_give_you_wrong_results):
    lower_bound = max(A)
    upper_bound = sum(A)

    if max_block_cnt == 1:      return upper_bound
    if max_block_cnt >= len(A): return lower_bound

    while lower_bound <= upper_bound:
        candidate_mid = (lower_bound + upper_bound) / 2
        if blockSizeIsValid(A, max_block_cnt, candidate_mid):
            upper_bound = candidate_mid - 1
        else:
            lower_bound = candidate_mid + 1

    return lower_bound

def solution(K, M, A):
    return binarySearch(A,K,M)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Zheng Xu

    Thanks for your warning on not using M. Assuming that M is the max element in A caused my solution to fail. I could not find the bug in my code until I read your post about not assuming M is always the max element.

    However, I’m confused regarding the time complexity. Why is the time complexity O(N*log(N+M)) instead of O(N*log(N*M))? The upper bound of the binary search is equal to the sum of the elements in A, which is at most N*M.

    • That is a very good question there. I trusted the evaluation during the Codility testing. You are right, we are iterating [M, N*M]. Anyways log(M*M) = 2log(M). Therefore the actual O complexity would be O(N*log(M))