Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Binary Search on Answer

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Hashing →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search-on-answer

Minimum Number of Days to Make m Bouquets

Problem (restated)

Garden blooms on bloomDay[i]. Make m bouquets of k adjacent flowers. Min days, or -1.

Intuition

If day d works, later days work. binary search d; greedy count bouquets on day d.

Approaches

Binary search day

Tested only
Time O(n log D)Space O(1)

Idea. lo=min(days), hi=max(days). canMake(d): scan adjacent groups of k blooms ≤ d.

Walkthrough. [1,10,3,10,2], m=3, k=1 → 3; m=3,k=2 → -1.

Trade-offs. Same feasibility pattern as ship/Koko.

Solution
export function minDays(bloomDay: number[], m: number, k: number): number {
  if (BigInt(m) * BigInt(k) > BigInt(bloomDay.length)) return -1;
  let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay);
  const ok = (day: number) => {
    let bouquets = 0, adj = 0;
    for (const d of bloomDay) {
      if (d <= day) { adj++; if (adj === k) { bouquets++; adj = 0; } }
      else adj = 0;
    }
    return bouquets >= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

export function minDays(bloomDay: number[], m: number, k: number): number {
  if (BigInt(m) * BigInt(k) > BigInt(bloomDay.length)) return -1;
  let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay);
  const ok = (day: number) => {
    let bouquets = 0, adj = 0;
    for (const d of bloomDay) {
      if (d <= day) { adj++; if (adj === k) { bouquets++; adj = 0; } }
      else adj = 0;
    }
    return bouquets >= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Reflection