LeetCode #3600 — HARD

Maximize Spanning Tree Stability with Upgrades

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

You are given an integer n, representing n nodes numbered from 0 to n - 1 and a list of edges, where edges[i] = [u_i, v_i, s_i, must_i]:

u_i and v_i indicates an undirected edge between nodes u_i and v_i.
s_i is the strength of the edge.
must_i is an integer (0 or 1). If must_i == 1, the edge must be included in the spanning tree. These edges cannot be upgraded.

You are also given an integer k, the maximum number of upgrades you can perform. Each upgrade doubles the strength of an edge, and each eligible edge (with must_i == 0) can be upgraded at most once.

The stability of a spanning tree is defined as the minimum strength score among all edges included in it.

Return the maximum possible stability of any valid spanning tree. If it is impossible to connect all nodes, return -1.

Note: A spanning tree of a graph with n nodes is a subset of the edges that connects all nodes together (i.e. the graph is connected) without forming any cycles, and uses exactly n - 1 edges.

Example 1:

Input: n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1

Output: 2

Explanation:

Edge [0,1] with strength = 2 must be included in the spanning tree.
Edge [1,2] is optional and can be upgraded from 3 to 6 using one upgrade.
The resulting spanning tree includes these two edges with strengths 2 and 6.
The minimum strength in the spanning tree is 2, which is the maximum possible stability.

Example 2:

Input: n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2

Output: 6

Explanation:

Since all edges are optional and up to k = 2 upgrades are allowed.
Upgrade edges [0,1] from 4 to 8 and [1,2] from 3 to 6.
The resulting spanning tree includes these two edges with strengths 8 and 6.
The minimum strength in the tree is 6, which is the maximum possible stability.

Example 3:

Input: n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0

Output: -1

Explanation:

All edges are mandatory and form a cycle, which violates the spanning tree property of acyclicity. Thus, the answer is -1.

Constraints:

2 <= n <= 10⁵
1 <= edges.length <= 10⁵
edges[i] = [u_i, v_i, s_i, must_i]
0 <= u_i, v_i < n
u_i != v_i
1 <= s_i <= 10⁵
must_i is either 0 or 1.
0 <= k <= n
There are no duplicate edges.

Step 01

Brute Force Baseline

Problem summary: You are given an integer n, representing n nodes numbered from 0 to n - 1 and a list of edges, where edges[i] = [ui, vi, si, musti]: ui and vi indicates an undirected edge between nodes ui and vi. si is the strength of the edge. musti is an integer (0 or 1). If musti == 1, the edge must be included in the spanning tree. These edges cannot be upgraded. You are also given an integer k, the maximum number of upgrades you can perform. Each upgrade doubles the strength of an edge, and each eligible edge (with musti == 0) can be upgraded at most once. The stability of a spanning tree is defined as the minimum strength score among all edges included in it. Return the maximum possible stability of any valid spanning tree. If it is impossible to connect all nodes, return -1. Note: A spanning tree of a graph with n nodes is a subset of the edges that connects all nodes together (i.e. the graph is

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Binary Search · Greedy · Union-Find

Example 1

3
[[0,1,2,1],[1,2,3,0]]
1

Example 2

3
[[0,1,4,0],[1,2,3,0],[0,2,1,0]]
2

Example 3

3
[[0,1,1,1],[1,2,1,1],[2,0,1,1]]
0

Step 02

Core Insight

What unlocks the optimal approach

Sort the <code>edges</code> array in descending order of weights.
Try using binary search on <code>ans</code>.
Implement a <code>chk</code> function which first adds all the edges with <code>must = 1</code>, and then adds the edges with <code>must = 0</code>, using any remaining upgrades greedily.
Use a <code>DSU</code> with path compression and union by size/rank to maintain connected components.
Don't forget the case where you cannot form an MST because more than one component remains after processing all edges.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// package main
// 
// import (
// 	"math"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// type unionFind struct {
// 	fa []int // 代表元
// 	cc int   // 连通块个数
// }
// 
// func newUnionFind(n int) unionFind {
// 	fa := make([]int, n)
// 	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
// 	// 集合 i 的代表元是自己
// 	for i := range fa {
// 		fa[i] = i
// 	}
// 	return unionFind{fa, n}
// }
// 
// // 返回 x 所在集合的代表元
// // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
// func (u unionFind) find(x int) int {
// 	// 如果 fa[x] == x，则表示 x 是代表元
// 	if u.fa[x] != x {
// 		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
// 	}
// 	return u.fa[x]
// }
// 
// // 把 from 所在集合合并到 to 所在集合中
// // 返回是否合并成功
// func (u *unionFind) merge(from, to int) bool {
// 	x, y := u.find(from), u.find(to)
// 	if x == y { // from 和 to 在同一个集合，不做合并
// 		return false
// 	}
// 	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
// 	u.cc--      // 成功合并，连通块个数减一
// 	return true
// }
// 
// func maxStability(n int, edges [][]int, k int) int {
// 	uf := newUnionFind(n)
// 	allUf := newUnionFind(n)
// 	minS1 := math.MaxInt
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 {
// 			if !uf.merge(x, y) { // 必选边成环
// 				return -1
// 			}
// 			minS1 = min(minS1, s)
// 		}
// 		allUf.merge(x, y)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left := uf.cc - 1
// 	if left == 0 { // 只需选必选边
// 		return minS1
// 	}
// 
// 	ans := minS1
// 	// Kruskal 算法求最大生成树
// 	slices.SortFunc(edges, func(a, b []int) int { return b[2] - a[2] })
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must == 0 && uf.merge(x, y) {
// 			if left > k {
// 				ans = min(ans, s)
// 			} else {
// 				ans = min(ans, s*2)
// 			}
// 			left--
// 			if left == 0 { // 已经得到生成树了
// 				break
// 			}
// 		}
// 	}
// 	return ans
// }
// 
// func maxStability1(n int, edges [][]int, k int) int {
// 	mustUf := newUnionFind(n) // 必选边并查集
// 	allUf := newUnionFind(n)  // 全图并查集
// 	minS, maxS := math.MaxInt, 0
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 && !mustUf.merge(x, y) { // 必选边成环
// 			return -1
// 		}
// 		allUf.merge(x, y)
// 		minS = min(minS, s)
// 		maxS = max(maxS, s)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left, right := minS, maxS*2
// 	ans := left + sort.Search(right-left, func(low int) bool {
// 		low += left
// 		low++ // 二分最小的不满足要求的 low+1，那么答案就是最大的满足要求的 low
// 		u := newUnionFind(n)
// 		for _, e := range edges {
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must > 0 && s < low { // 必选边的边权太小
// 				return true
// 			}
// 			if must > 0 || s >= low {
// 				u.merge(x, y)
// 			}
// 		}
// 
// 		leftK := k
// 		for _, e := range edges {
// 			if leftK == 0 || u.cc == 1 {
// 				break
// 			}
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must == 0 && s < low && s*2 >= low && u.merge(x, y) {
// 				leftK--
// 			}
// 		}
// 		return u.cc > 1
// 	})
// 	return ans
// }

// Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
package main

import (
	"math"
	"slices"
	"sort"
)

// https://space.bilibili.com/206214
type unionFind struct {
	fa []int // 代表元
	cc int   // 连通块个数
}

func newUnionFind(n int) unionFind {
	fa := make([]int, n)
	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
	// 集合 i 的代表元是自己
	for i := range fa {
		fa[i] = i
	}
	return unionFind{fa, n}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
	// 如果 fa[x] == x，则表示 x 是代表元
	if u.fa[x] != x {
		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
	}
	return u.fa[x]
}

// 把 from 所在集合合并到 to 所在集合中
// 返回是否合并成功
func (u *unionFind) merge(from, to int) bool {
	x, y := u.find(from), u.find(to)
	if x == y { // from 和 to 在同一个集合，不做合并
		return false
	}
	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
	u.cc--      // 成功合并，连通块个数减一
	return true
}

func maxStability(n int, edges [][]int, k int) int {
	uf := newUnionFind(n)
	allUf := newUnionFind(n)
	minS1 := math.MaxInt
	for _, e := range edges {
		x, y, s, must := e[0], e[1], e[2], e[3]
		if must > 0 {
			if !uf.merge(x, y) { // 必选边成环
				return -1
			}
			minS1 = min(minS1, s)
		}
		allUf.merge(x, y)
	}

	if allUf.cc > 1 { // 图不连通
		return -1
	}

	left := uf.cc - 1
	if left == 0 { // 只需选必选边
		return minS1
	}

	ans := minS1
	// Kruskal 算法求最大生成树
	slices.SortFunc(edges, func(a, b []int) int { return b[2] - a[2] })
	for _, e := range edges {
		x, y, s, must := e[0], e[1], e[2], e[3]
		if must == 0 && uf.merge(x, y) {
			if left > k {
				ans = min(ans, s)
			} else {
				ans = min(ans, s*2)
			}
			left--
			if left == 0 { // 已经得到生成树了
				break
			}
		}
	}
	return ans
}

func maxStability1(n int, edges [][]int, k int) int {
	mustUf := newUnionFind(n) // 必选边并查集
	allUf := newUnionFind(n)  // 全图并查集
	minS, maxS := math.MaxInt, 0
	for _, e := range edges {
		x, y, s, must := e[0], e[1], e[2], e[3]
		if must > 0 && !mustUf.merge(x, y) { // 必选边成环
			return -1
		}
		allUf.merge(x, y)
		minS = min(minS, s)
		maxS = max(maxS, s)
	}

	if allUf.cc > 1 { // 图不连通
		return -1
	}

	left, right := minS, maxS*2
	ans := left + sort.Search(right-left, func(low int) bool {
		low += left
		low++ // 二分最小的不满足要求的 low+1，那么答案就是最大的满足要求的 low
		u := newUnionFind(n)
		for _, e := range edges {
			x, y, s, must := e[0], e[1], e[2], e[3]
			if must > 0 && s < low { // 必选边的边权太小
				return true
			}
			if must > 0 || s >= low {
				u.merge(x, y)
			}
		}

		leftK := k
		for _, e := range edges {
			if leftK == 0 || u.cc == 1 {
				break
			}
			x, y, s, must := e[0], e[1], e[2], e[3]
			if must == 0 && s < low && s*2 >= low && u.merge(x, y) {
				leftK--
			}
		}
		return u.cc > 1
	})
	return ans
}

# Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
# Time:  O(n + eloge)
# Space: O(n)

# union find, kruskal's algorithm, mst, maximum spanning tree, greedy
class UnionFind(object):  # Time: O(n * alpha(n)), Space: O(n)
    def __init__(self, n):
        self.set = range(n)
        self.rank = [0]*n

    def find_set(self, x):
        stk = []
        while self.set[x] != x:  # path compression
            stk.append(x)
            x = self.set[x]
        while stk:
            self.set[stk.pop()] = x
        return x

    def union_set(self, x, y):
        x, y = self.find_set(x), self.find_set(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:  # union by rank
            x, y = y, x
        self.set[x] = self.set[y]
        if self.rank[x] == self.rank[y]:
            self.rank[y] += 1
        return True


class Solution(object):
    def maxStability(self, n, edges, k):
        """
        :type n: int
        :type edges: List[List[int]]
        :type k: int
        :rtype: int
        """
        uf = UnionFind(n)
        cnt = 0
        result = float("inf")
        for u, v, s, m in edges:
            if not m:
                continue
            if not uf.union_set(u, v):
                return -1
            cnt += 1
            result = min(result, s)
        edges.sort(key=lambda x: -x[2])
        for u, v, s, m in edges:
            if m:
                continue
            if not uf.union_set(u, v):
                continue
            cnt += 1
            if cnt == (n-1)-k:
                result = min(result, s)
            elif cnt == n-1:
                result = min(result, 2*s)
        return result if cnt == n-1 else -1

// Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// package main
// 
// import (
// 	"math"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// type unionFind struct {
// 	fa []int // 代表元
// 	cc int   // 连通块个数
// }
// 
// func newUnionFind(n int) unionFind {
// 	fa := make([]int, n)
// 	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
// 	// 集合 i 的代表元是自己
// 	for i := range fa {
// 		fa[i] = i
// 	}
// 	return unionFind{fa, n}
// }
// 
// // 返回 x 所在集合的代表元
// // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
// func (u unionFind) find(x int) int {
// 	// 如果 fa[x] == x，则表示 x 是代表元
// 	if u.fa[x] != x {
// 		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
// 	}
// 	return u.fa[x]
// }
// 
// // 把 from 所在集合合并到 to 所在集合中
// // 返回是否合并成功
// func (u *unionFind) merge(from, to int) bool {
// 	x, y := u.find(from), u.find(to)
// 	if x == y { // from 和 to 在同一个集合，不做合并
// 		return false
// 	}
// 	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
// 	u.cc--      // 成功合并，连通块个数减一
// 	return true
// }
// 
// func maxStability(n int, edges [][]int, k int) int {
// 	uf := newUnionFind(n)
// 	allUf := newUnionFind(n)
// 	minS1 := math.MaxInt
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 {
// 			if !uf.merge(x, y) { // 必选边成环
// 				return -1
// 			}
// 			minS1 = min(minS1, s)
// 		}
// 		allUf.merge(x, y)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left := uf.cc - 1
// 	if left == 0 { // 只需选必选边
// 		return minS1
// 	}
// 
// 	ans := minS1
// 	// Kruskal 算法求最大生成树
// 	slices.SortFunc(edges, func(a, b []int) int { return b[2] - a[2] })
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must == 0 && uf.merge(x, y) {
// 			if left > k {
// 				ans = min(ans, s)
// 			} else {
// 				ans = min(ans, s*2)
// 			}
// 			left--
// 			if left == 0 { // 已经得到生成树了
// 				break
// 			}
// 		}
// 	}
// 	return ans
// }
// 
// func maxStability1(n int, edges [][]int, k int) int {
// 	mustUf := newUnionFind(n) // 必选边并查集
// 	allUf := newUnionFind(n)  // 全图并查集
// 	minS, maxS := math.MaxInt, 0
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 && !mustUf.merge(x, y) { // 必选边成环
// 			return -1
// 		}
// 		allUf.merge(x, y)
// 		minS = min(minS, s)
// 		maxS = max(maxS, s)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left, right := minS, maxS*2
// 	ans := left + sort.Search(right-left, func(low int) bool {
// 		low += left
// 		low++ // 二分最小的不满足要求的 low+1，那么答案就是最大的满足要求的 low
// 		u := newUnionFind(n)
// 		for _, e := range edges {
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must > 0 && s < low { // 必选边的边权太小
// 				return true
// 			}
// 			if must > 0 || s >= low {
// 				u.merge(x, y)
// 			}
// 		}
// 
// 		leftK := k
// 		for _, e := range edges {
// 			if leftK == 0 || u.cc == 1 {
// 				break
// 			}
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must == 0 && s < low && s*2 >= low && u.merge(x, y) {
// 				leftK--
// 			}
// 		}
// 		return u.cc > 1
// 	})
// 	return ans
// }

// Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3600: Maximize Spanning Tree Stability with Upgrades
// package main
// 
// import (
// 	"math"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// type unionFind struct {
// 	fa []int // 代表元
// 	cc int   // 连通块个数
// }
// 
// func newUnionFind(n int) unionFind {
// 	fa := make([]int, n)
// 	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
// 	// 集合 i 的代表元是自己
// 	for i := range fa {
// 		fa[i] = i
// 	}
// 	return unionFind{fa, n}
// }
// 
// // 返回 x 所在集合的代表元
// // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
// func (u unionFind) find(x int) int {
// 	// 如果 fa[x] == x，则表示 x 是代表元
// 	if u.fa[x] != x {
// 		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
// 	}
// 	return u.fa[x]
// }
// 
// // 把 from 所在集合合并到 to 所在集合中
// // 返回是否合并成功
// func (u *unionFind) merge(from, to int) bool {
// 	x, y := u.find(from), u.find(to)
// 	if x == y { // from 和 to 在同一个集合，不做合并
// 		return false
// 	}
// 	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
// 	u.cc--      // 成功合并，连通块个数减一
// 	return true
// }
// 
// func maxStability(n int, edges [][]int, k int) int {
// 	uf := newUnionFind(n)
// 	allUf := newUnionFind(n)
// 	minS1 := math.MaxInt
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 {
// 			if !uf.merge(x, y) { // 必选边成环
// 				return -1
// 			}
// 			minS1 = min(minS1, s)
// 		}
// 		allUf.merge(x, y)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left := uf.cc - 1
// 	if left == 0 { // 只需选必选边
// 		return minS1
// 	}
// 
// 	ans := minS1
// 	// Kruskal 算法求最大生成树
// 	slices.SortFunc(edges, func(a, b []int) int { return b[2] - a[2] })
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must == 0 && uf.merge(x, y) {
// 			if left > k {
// 				ans = min(ans, s)
// 			} else {
// 				ans = min(ans, s*2)
// 			}
// 			left--
// 			if left == 0 { // 已经得到生成树了
// 				break
// 			}
// 		}
// 	}
// 	return ans
// }
// 
// func maxStability1(n int, edges [][]int, k int) int {
// 	mustUf := newUnionFind(n) // 必选边并查集
// 	allUf := newUnionFind(n)  // 全图并查集
// 	minS, maxS := math.MaxInt, 0
// 	for _, e := range edges {
// 		x, y, s, must := e[0], e[1], e[2], e[3]
// 		if must > 0 && !mustUf.merge(x, y) { // 必选边成环
// 			return -1
// 		}
// 		allUf.merge(x, y)
// 		minS = min(minS, s)
// 		maxS = max(maxS, s)
// 	}
// 
// 	if allUf.cc > 1 { // 图不连通
// 		return -1
// 	}
// 
// 	left, right := minS, maxS*2
// 	ans := left + sort.Search(right-left, func(low int) bool {
// 		low += left
// 		low++ // 二分最小的不满足要求的 low+1，那么答案就是最大的满足要求的 low
// 		u := newUnionFind(n)
// 		for _, e := range edges {
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must > 0 && s < low { // 必选边的边权太小
// 				return true
// 			}
// 			if must > 0 || s >= low {
// 				u.merge(x, y)
// 			}
// 		}
// 
// 		leftK := k
// 		for _, e := range edges {
// 			if leftK == 0 || u.cc == 1 {
// 				break
// 			}
// 			x, y, s, must := e[0], e[1], e[2], e[3]
// 			if must == 0 && s < low && s*2 >= low && u.merge(x, y) {
// 				leftK--
// 			}
// 		}
// 		return u.cc > 1
// 	})
// 	return ans
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.