Skip to content

Binary Search Minimize Max

Table of Contents

410. Split Array Largest Sum

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, dynamic programming, greedy, prefix sum

2064. Minimized Maximum of Products Distributed to Any Store

1760. Minimum Limit of Balls in a Bag

1631. Path With Minimum Effort

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, depth first search, breadth first search, union find, heap priority queue, matrix

  • Return the minimum effort required to travel from the top-left to the bottom-right corner.
1631. Path With Minimum Effort - Python Solution
import heapq
from typing import List


# Prim
def minimumEffortPath(heights: List[List[int]]) -> int:
    m, n = len(heights), len(heights[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False] * n for _ in range(m)]
    heap = [(0, 0, 0)]  # (effort, row, col)

    while heap:
        effort, r, c = heapq.heappop(heap)

        if visited[r][c]:
            continue

        if r == m - 1 and c == n - 1:
            return effort

        visited[r][c] = True

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                updated = max(effort, abs(heights[r][c] - heights[nr][nc]))
                heapq.heappush(heap, (updated, nr, nc))

    return -1


heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
print(minimumEffortPath(heights))  # 2

2439. Minimize Maximum of Array

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, dynamic programming, greedy, prefix sum

2560. House Robber IV

778. Swim in Rising Water

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, depth first search, breadth first search, union find, heap priority queue, matrix

  • Return the minimum time when you can reach the target.

778

778. Swim in Rising Water - Python Solution
import heapq
from typing import List


# Dijkstra's
def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)
    visited = set()
    minHeap = [(grid[0][0], 0, 0)]
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    visited.add((0, 0))

    while minHeap:
        time, r, c = heapq.heappop(minHeap)

        if r == n - 1 and c == n - 1:
            return time

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if nr in range(n) and nc in range(n) and (nr, nc) not in visited:
                visited.add((nr, nc))
                heapq.heappush(minHeap, (max(time, grid[nr][nc]), nr, nc))


grid = [
    [0, 1, 2, 3, 4],
    [24, 23, 22, 21, 5],
    [12, 13, 14, 15, 16],
    [11, 17, 18, 19, 20],
    [10, 9, 8, 7, 6],
]
print(swimInWater(grid))  # 16

2616. Minimize the Maximum Difference of Pairs

3419. Minimize the Maximum Edge Weight of Graph

  • LeetCode | LeetCode CH (Medium)

  • Tags: binary search, depth first search, breadth first search, graph, shortest path

2513. Minimize the Maximum of Two Arrays

3399. Smallest Substring With Identical Characters II

774. Minimize Max Distance to Gas Station

Comments