DDSA Solutions

2560. House Robber IV

MediumView on LeetCode
ArrayBinary Search
Time: O(n log max)
Space: O(1)

Problem Overview

Minimum operations to make all elements in each house covered.

Intuition

Minimum operations to make all elements in each house covered. Binary search on answer (number of cops).

Algorithm

  1. 1Binary search on k (number of cops / operations). Feasibility: can k operations cover all houses?

Common Pitfalls

  • •Greedy placement of security officers at every k positions. Binary search on coverage gap.
2560.cs
C#
// Approach: Binary search on capability; greedy non-adjacent selection validates feasibility.
// Time: O(n log max) Space: O(1)

public class Solution
{
    public int MinCapability(int[] nums, int k)
    {
        int l = nums.Min();
        int r = nums.Max();

        while (l < r)
        {
            int m = (l + r) / 2;
            if (NumStolenHouses(nums, m) >= k)
                r = m;
            else
                l = m + 1;
        }

        return l;
    }

    private int NumStolenHouses(int[] nums, int capacity)
    {
        int stolenHouses = 0;
        for (int i = 0; i < nums.Length; ++i)
        {
            if (nums[i] <= capacity)
            {
                ++stolenHouses;
                ++i;
            }
        }
        return stolenHouses;
    }
}
Was this solution helpful?

Related Problems