Binary Search Speedrun - Binary Search / Speedrun

Problems
21

I had multiple choices where two (bad) solutions were the same: is it normal?

22

In problem 7’s problem description:

‘For example, s = “|||||", and a query [3, 8] denotes the substring "||******|”.’

The substring here looks wrong.

1 Like
23

woah, the formatting made the string weird in my comment above. Please refer to the original problem statement.

24

hey, great suggestion! we added quick links to the top of each speedrun. re: test cases there’s a link to each problems at the end of the explanation.

25

Why am I not able to toggle to Javascript on this page?

26

Yeah really need to be able to see these answers in different languages. Love the speed round idea tho

27

Please fix this:

Constraints:

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

is actually

1 <= piles.length <= 10^^4
piles.length <= h <= 10^^9
1 <= piles[i] <= 10^^9
28

In Question 6, it is mentioned that “SnapshotArray(int length) initializes an array-like data structure with the given length.” Later on, it is mentioned that “we keep track of an array histories of size n.” I found this confusing until I saw the solution and realized that n is actually the same as length. Would it be clearer to have a consistent naming convention?

29

Did anyone else find the wording on some questions really confusing? I was pretty lost in the problem statements for questions 2, 4-5. I wish there were more examples. I wonder if it’s because the problems are a bit convoluted when it comes to the examples they’re giving. Like the “bananas before guards” was a confusing concept, especially in the “piles per hour” and then immediately expecting you to understand piles[i] before introducing you to the full code. As a user, it feels like all the information given to me is by someone who forgot that I have no experience with this specific question and the code they’ve written - and their explanation assumes you have 20% background knowledge on it.

I really like the links at the end though because I think the leetcode questions and solutions provided are way clearer.

For instance, on question 4 I was so lost about what the hint meant? I read it multiple times and had no idea how parity could be related, and then I read the solution explanation and was still lost. It was only after reading the top voted solution on leetcode I understand the relationship between [index, index+1] => [even, odd] pattern matching. I think the sections could be improved by describing problems in more casual language before jumping immediately into mathematical translations - it would help users understand the full concept of the problem before trying to parse answers.

30

Answer is wrong. It will fail with index out of bounds for input like - [1,2,2].
Correct algo should be

private boolean goLeft(int m, int[] nums) {
    if(m==nums.length-1) return true;

    if(m%2==0) return nums[m] != nums[m+1];
    else return nums[m] != nums[m-1];
}
31

In the given examples (eg.2 & 3), the arrays are not sorted. How can they apply the binary search template for unsorted array? Doesn’t seem right…

32

@algo.monster
In the question, the important part of the code is missing:

if history[mid][0] <= snap_id:

But in the answer, the code is complete:

if self.histories[index][mid][0] <= snap_id:

This missing code part in the question confused me a lot. It just didn’t comply with the description of the question.

33

There are a bunch of small errors in some questions of Binary Search Speedrun.

34

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

if Koko needs to eat everything BEFORE the guard returns I would say the correct feasibility should be:
hours_used < h instead of hours_used <= h

35

Why does number 5 give an example that appears to be two input arrays, when the method that we are trying to implement just takes an array of two integers. I think the most confusing part is the way that these questions are being asked. Even after seeing the answer, and even understanding the answer, I still don’t understand the question.

36

This is what confuses me:
Input [“MyCalendar”, “book”, “book”, “book”] [, [10, 20], [15, 25], [20, 30]] Output [null, true, false, true]

37

There is an error in all of the given selections in that they start by setting the left bound at 0. This may work for the given examples, but consider the first example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Yes, the correct solution solves this correctly, but if the target was 5 rather than 8, the answer should be 0 but the solution will return -1, because the 0 index is not included in the search.

However, as far as I can tell, the problem statement does not preclude the target from being a number that occurs only once and at the beginning of the array.

DISCLAIMER: looks like the solutions are Python (?) I don’t know Python so perhaps I misunderstand something here.

38

You can just do this, no extra variable needed?

    def firstBadVersion(self, n: int) -> int:
        start = 1, end = n

        while start < end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1

        return start
39

This is what I’m confused about, too. I don’t understand the decision to just have the solutions of the speedruns in python. I use java and I have a difficult time understanding python code.

40

@algo.monster could you please clarify, are there plans to have speedrun section in Java?
Because It’s pretty uncomfortable to have speedrun only in Python.
Even though in the course all examples are in Java.
Would appreciate if option to choose the language for the Speedrun will be available