Skip to content

Binary Search Max Answer

Table of Contents

275. H-Index II

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search

  • Hint: logarithmic time -- binary search
275. H-Index II - Python Solution
from typing import List


# Binary Search Max Answer
def hIndex(citations: List[int]) -> int:
    n = len(citations)
    left, right = 0, n - 1

    while left <= right:
        mid = left + (right - left) // 2

        if citations[mid] >= n - mid:
            right = mid - 1
        else:
            left = mid + 1

    return n - left


if __name__ == "__main__":
    citations = [0, 1, 3, 5, 6]
    assert hIndex(citations) == 3

2226. Maximum Candies Allocated to K Children

2226. Maximum Candies Allocated to K Children - Python Solution
from typing import List


# Binary Search Max Answer
def maximumCandies(candies: List[int], k: int) -> int:
    def check(low):
        return sum(c // low for c in candies) >= k

    left, right = 0, max(candies) + 1
    while left + 1 < right:
        mid = left + (right - left) // 2
        if check(mid):
            left = mid
        else:
            right = mid

    return left


# Binary Search Max Answer - Optimized
def maximumCandiesOptimized(candies: List[int], k: int) -> int:
    def check(low):
        return sum(c // low for c in candies) >= k

    # Use the minimum of max(candies) and sum(candies) // k to limit the search space
    left, right = 0, min(max(candies), sum(candies) // k) + 1

    while left + 1 < right:
        mid = left + (right - left) // 2
        if check(mid):
            left = mid
        else:
            right = mid

    return left


if __name__ == "__main__":
    candies = [5, 8, 6]
    k = 3
    assert maximumCandies(candies, k) == 5
    assert maximumCandiesOptimized(candies, k) == 5

2982. Find Longest Special Substring That Occurs Thrice II

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, binary search, sliding window, counting

2576. Find the Maximum Number of Marked Indices

2576. Find the Maximum Number of Marked Indices - Python Solution
from typing import List


# Fast Slow Pointers
def maxNumOfMarkedIndices(nums: List[int]) -> int:
    nums.sort()
    n = len(nums)
    slow, fast = 0, n // 2
    count = 0

    while slow < n // 2 and fast < n:
        if nums[fast] >= 2 * nums[slow]:
            count += 2
            slow += 1
        fast += 1

    return count


nums = [3, 5, 2, 4]
print(maxNumOfMarkedIndices(nums))  # 2

1898. Maximum Number of Removable Characters

1802. Maximum Value at a Given Index in a Bounded Array

1642. Furthest Building You Can Reach

2861. Maximum Number of Alloys

3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K

2141. Maximum Running Time of N Computers

2258. Escape the Spreading Fire

2071. Maximum Number of Tasks You Can Assign

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, greedy, queue, sorting, monotonic queue

1618. Maximum Font to Fit a Sentence in a Screen

1891. Cutting Ribbons

2137. Pour Water Between Buckets to Make Water Levels Equal

644. Maximum Average Subarray II

Comments