3010. Divide an Array Into Subarrays With Minimum Cost I

Time: O(n)

Space: O(1)

Intuition

Divide array into minimum subarrays where each subarray has a minimum score (min[subarray]). Each subarray must satisfy min*length >= k.

Algorithm

1Binary search or greedy partition. For minimum subarrays: greedily extend current subarray as long as valid.

Common Pitfalls

•Check feasibility with binary search on number of partitions.

3010.cs

// Approach: First subarray always starts at index 0; take 2 smallest values from remaining.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinimumCost(int[] nums)
    {
        const int MAX = 50;
        int min1 = MAX;
        int min2 = MAX;

        for (int i = 1; i < nums.Length; ++i)
        {
            if (nums[i] < min1)
            {
                min2 = min1;
                min1 = nums[i];
            }
            else if (nums[i] < min2)
                min2 = nums[i];
        }

        return nums[0] + min1 + min2;
    }
}

Was this solution helpful?