Maximum number of chunks algorithm

January 21, 2018

Introduction

It is the new way to learn the algorithm called maximum number of chunks. Last 2 weeks I asked the algorithm after mock interview over five times, through the discussion with so many peers, I also learned a few things. The peers are super talent on algorithm problem solving, one is senior developer of top four companies, one is computer science Ph.D., and others are preparing Google/ Facebook onsite.

Brute force analysis

One thing I learn is about the brute force solution. What is the time complexity for a brute force solution. I met a software engineer who is also Chinese. He argued with me and then I understood after the mock interview he is correct on the time complexity. For the array of size N, every index can be open chunk/close chunk position or not. So each index has 3 options, open chunk or close chunk or not the first two. So the option should be 2ⁿ time complexity.