Tag: binary-search

LeetCode 2594 – Minimum Time To Repair Cars
Although this problem is not frequently asked by companies, it offers an interesting perspective. Initially, this problem may seem to require a complex solution, but it can be efficiently solved using binary search.

Binary Search Approach

The key is to frame the problem as finding the minimum time required to repair all cars, within a range from 1 to the maximum possible time. The maximum possible time is determined by the minimum rank multiplied by the square of the number of cars. Since the number of cars is always greater than 0, the theoretical minimum possible time is 1, and the solution lies within this range.

Therefore, the problem is transformed into a binary search, where at each iteration, we check if all cars can be repaired within a given time. If yes, we search the left half for a potentially lower time; otherwise, we search the right half.

We know that a mechanic with rank ‘r’ takes $r*n^{2}$ time to repair ‘n’ cars, so within time ‘t’, they can repair sqrt(t/r) cars. We need to create a helper function that returns a boolean indicating whether all cars can be repaired within a given time ‘t’. We have to take the floor and then we sum the values to determine number of cars that can be repaired in time t. If this value is greater than or equal to the desired number of cars, we will return True.
```
def can_repair(self, t,n,ranks):
        n_each_mech = [int((t/r)**0.5) for r in ranks]
        return sum(n_each_mech)>=n
```
The solution to the problem.
```
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        min_rank = min(ranks)
        low = 1
        high = min_rank*cars*cars

        min_time = None

        while low <= high:
            mid = (high+low)//2

            if self.can_repair(mid,cars,ranks):
                min_time = mid
                high = mid-1

            else:
                low = mid+1
        
        return min_time

    def can_repair(self, t,n,ranks):
        n_each_mech = [int((t/r)**0.5) for r in ranks]
        return sum(n_each_mech)>=n
```
Complexity Analysis

The time complexity is O(N log(C)), where N is the number of mechanics and C is the range of possible times. The binary search contributes a factor of O(log(C)), and the can_repair function contributes a factor of O(N). The space complexity is O(1) as we are only using constant extra space.

Let me know if you would like to cover any additional aspects or if you have any further questions.
March 16, 2025
LeetCode 2529 – Maximum Count of Positive Integer and Negative Integer
The question has been asked by a few companies including Meta, but is not a super popular question.

Nonetheless the question is important as it focusses on a variation of binary search.

The naive solution to the problem would be iterating through the array, finding out the first index you see a positive number, also keeping track the last index you saw a negative number. Then you can then calculate the number of positive numbers and number of negative numbers in the list. But this would be O(n) in time complexity. We can solve this problem by using binary search and this will bring down the time complexity to O(logn).

The trick is to phrase the question as to finding the index of the first occurrence of positive number. Since the array is sorted, we can then calculate the number of positive integers.

We also need to find the last occurence of a negative number in the array. This will then provide us the information about how many negative numbers are there in the array.

Also remember that the array is not guaranteed to have both positive or negative integers, so we need to take that into account as well.
```
        n = len(nums)

        # First positive index
        l,r = 0,n-1
        first_positive_idx = n
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val > 0:
                first_positive_idx = mid
                r = mid-1
            else:
                l = mid+1
```
Here we initialise the first positive index to be n as it may be the case that the array either has all 0s or negative integers, in that case the first positive index has to be outside our array and the first place it can go into is n. We calculate the number of positive integers as n – first_positive_idx, so if it’s at n then we know there are 0 positive integers in the array.

The binary search is the standard binary search, except we search if the value in the middle is positive, if that’s the case we mark that as a possible first positive index and then search towards the left as there could be more positive in the left, otherwise we search in the right half.
```
        # Last negative index
        l,r = 0,n-1
        last_neg_idx = -1
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val < 0:
                last_neg_idx = mid
                l = mid + 1
            else:
                r = mid-1
```
Similarly for the last negative index, we initialise the last negative index to be -1, which is that if all integers in the array are 0 or positive, then its position has to be outside the array. We calculate the number of negative integers as last_negative_idx + 1, so here it will automatically become 0.

We then do a binary search where we check if the middle element is negative, if we find it then we mark it as a possible last negative index and then search towards the right as there could be more negative numbers, otherwise we search in the left half.

Combining everything we have the solution.
```
class Solution:
    def maximumCount(self, nums: List[int]) -> int:

        
        
        n = len(nums)

        # First positive index
        l,r = 0,n-1
        first_positive_idx = n
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val > 0:
                first_positive_idx = mid
                r = mid-1
            else:
                l = mid+1
        # Last negative index
        l,r = 0,n-1
        last_neg_idx = -1
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val < 0:
                last_neg_idx = mid
                l = mid + 1
            else:
                r = mid-1

        num_positive = n-(first_positive_idx)
        num_negative = (last_neg_idx) + 1

        return max(num_positive,num_negative)
```
As you can see the time complexity is O(logn) as we do two binary searches. There is a way to combine both in one pass but in terms of time complexity, it doesn’t matter. It has a space complexity of O(1) as we are not storing anything other than some variables which take up constant space.

Thanks for reading the article, let me know in the comments which problems you want me to either write the solution or create a youtube walkthrough in the comments.
March 12, 2025

Tag: binary-search

LeetCode 2594 – Minimum Time To Repair Cars

LeetCode 2529 – Maximum Count of Positive Integer and Negative Integer