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))

      • Rishi Daryanani

        Martin, thank you so much for your answers. I’m learning and am confused about how you got this time complexity. Do you mind explaining it in deeper detail by the code? Or directing me to a good place to understand how to determine the complexity? I’ve read simpler explanations for O(N) and O(N*log(N) but I’m confused how you got your answer above on O(N*log(M)). Perhaps a better question is, what is the worst case input here? The question has also slightly changed I think since you wrote this, as the code returns a float = 6.5 but the answer expected is an int = 6

        • Rishi, thanks for letting me know that the solution no longer works. My code did not round the mid during binary search and returned a float. I fixed that and now the code works again.


          candidate_mid = (lower_bound + upper_bound) / 2

          vs


          candidate_mid = (lower_bound + upper_bound) // 2

          https://codility.com/demo/results/trainingV7JCCX-BVV/

        • For the time complexity, lets look at the binary search. You are searching a space between M and N*M. The lower bound is M, the upper_bound is N times any integer smaller than M. Since M is within the 64bit space we should consider it a constant.

          But since Codility wants to express the complexity in regards to M, we can pretend it is unbounded. Let us consider the two extreme cases, M=1 and M=INT_MAX. If M is 1, all integers have to be one. So you have [1,1,1,1,1…,1]. In the other case each int has to be smaller than INT_MAX. INT_MAX is the worst case scenario, because it will create the largest search space.

          So the largest space we can have is an array of Ms. The sum of all those (the upper bound) is N*M.

          We perform the body of the binary search function a logarithmic number of times. Giving you log(N*M). The body of the function blockSizeIsValid iterates over all elements in N. Therefore N*log(N*M).

          I honestly don’t know why Codility identifies this solution as N+M. It clearly passes the expected time complexity and returns before the time limit, which might be sufficient for the tool. Maybe there is a better (faster) solution available with O(N*log(N+M)) that behaves better with large Ms.

          So in seems that my solution does not pass their expected worst-case time complexity.

          • Rishi Daryanani

            Martin, I get it now, thanks so much for your detailed explanation on both your algorithm and the time complexity of it. This is really great. I’m fine with the “painless”/easy tasks of Codility, but for these challenging questions – like this one – I think I need more practice around concepts like binary search, although it’s pretty simple to grasp when you simply halve the input set and compare one section to another. I need to get better at solving these myself, so I’m going through every Codility exercise one by one and referring to your answers for comparison. Do you recommend any other ways to grow / become an expert in this space?

          • The best approach is going through the exercises 🙂

            Codility used to have a huge gap between the tutorial and the actual challenges. It used to be hard to bridge the gap without additional training. Maybe it has changed these days. Have a look at some other coding challenge websites out there and pick a platform that suits you. https://medium.freecodecamp.org/the-10-most-popular-coding-challenge-websites-of-2016-fb8a5672d22f

            I would also suggest the following: Try to solve everything on your own and only if you get really stuck have a look at other people’s solutions. What I used to do, was to spend some time understanding the solution and then moving on to the next challenge. I would eventually return to the challenge a few weeks later and tried to figure out what the neat trick was.

          • Rishi Daryanani

            That’s great advice – also, coming back to the problem a few weeks later is indeed a neat trick in itself! Thanks very much Martin 🙂 Much appreciated!

  • I find it confusing that it seems to me you’re calling “max_block_size” what actually is a “max_block_sum”. To me block size is the number of elements contained in a block, whereas here we’re talking about the sum of the block elements’ values. Or am I misunderstanding everything?

    • The same about the naming of the check subroutine: to me it sounds more like “tentativeBlockSumIsValid”.

  • Another point of doubt: inside the ckeck subroutine you verify “if block_cnt >= max_block_cnt:”
    Why the “equal”? I understand that we’re still inside the for-loop in the array and that at least one more element is gonna come, but is it not possible that the next element(s) will fit into the last block without increasing block_cnt?

    • However, I’ve tried checking only “if block_cnt > max_block_cnt:” and the test case fails. But I am not sure where this failure comes from. In fact, I am kinda puzzled that you return “candidate_mid + 1” instead of the more customary candidate_mid.

      • Gotta dig all this a little bit more 🙂 In any case, be it clear that I am very thankful to you for this very useful collection of exercises!

  • OK, I got a 100/100 JavaScript solution that seems to me kinda more understandable: https://gist.github.com/Muzietto/ac26b8e3272920ebfb30850aa94536e8

    • Hi Muzietto, welcome to my page and a Happy New Year!

      As you might know, variable names are a mix of both personal preference and the dominant style of the codebase you are working on. When I look over my page I can exactly pinpoint the project I was currently working on. The daily code style finds it’s way into my simple python snippets. If we were working together, we would find our own ‘vocabulary’ that would be understandable to both.

      You figured out your other questions while working on your solution, right :)?

      nice translation of Python into JS on your github page. Would you be able to write a functional equivalent?

      • Happy New Year to you! …and yes, I’d be able to write a functional routine for the job, but we both know it won’t scale and Codility will punish it. What can I say? I am an old man, and the FP season is now past me 🙂 Nowadays I “make it fast” from the beginning by programming in C no matter what the language is. I’ll probably end up my career using Assembler again :-):-):-)

        • In any case, your “Python snippets” made me decide that in 2017 I will definitely learn to use the language 🙂

  • Rishi Daryanani

    Martin thank you. Please consider this a newbie question. On the concept of binary search, do we need to “halve” the solution recursively to make our solution faster, or does it suffice to halve once and then increase/decrease our lower/upper bound as you have done? As this is a codility test, I’m curious what the interviewer expects for this solution and how we should think when it comes to binary search.

    • I “halve” the search space in every iteration.

      • Rishi Daryanani

        Of course! Sorry about that, silly question. Thanks for your reply 🙂