shlogg · Early preview
Prashant Mishra @prashantrmishra

Min Capability Of Array Elements In O(nlog(Max(nums))) Time Complexity

Min capability of k subarrays: O(nlog(Max(nums))) Find min of all max values possible using binary search.

Problem
TC: O(nlog(Max(nums)))

class Solution {
    public int minCapability(int[] nums, int k) {
        int index = 0;
        int low = Integer.MAX_VALUE;
        int high = 0;
        for(int i : nums){
            low = Math.min(low, i);
            high = Math.max(high, i);
        }
        int val = Integer.MAX_VALUE;
        while(low<=high){
            int mid = (low+high)/2;
            if(isPossible(mid,nums,k)){
                //note: if mid is possible and is not present in nums[] then also it is valid as we will reduce search space low,mid-1 hence we will find the valid value...