Minimum Time to Repair Cars

Similar to yesterday and the day before yesterday, it is just a binary search problem, where you binary search the maximum time taken by a mechanic.

code

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 0;
        long long right = ranks[0] * (long long)cars * (long long)cars;

        long long ans = 0;
        while (left <= right) {
            long long mid = left - (left - right)/2;

            long long counter = 0;
            for (int i = 0; i < ranks.size() && counter < cars; ++i) {
                counter += sqrt(mid/ranks[i]);
            }
            if (counter >= cars) {
                ans = mid;
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }
};

complexity

• Time: O(n log (max_rank * m^2))
  • where n = ranks.size(), max_rank = max(rank) and m = cars
• Space: O(1)

We can technically speed up the time complexity, by precomputing a rank_count array of size 100. This means we do not have to iterate through the entirety of ranks and only need to iterate through a maximum of 100 values.

Code:

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        int ranksCount[101] = {0};

        int minRank = 101;
        int maxRank = 0;

        for (int rank : ranks) {
            minRank = min(minRank, rank);
            maxRank = max(maxRank, rank);
            ++ranksCount[rank];
        }

        long long left = 0;
        long long right = minRank * (long long)cars * (long long)cars;
        long long ans = 0;
        while (left <= right) {
            long long mid = left - (left - right)/2;

            long long counter = 0;
            for (int i = minRank; i <= maxRank; ++i) {
                counter += ranksCount[i] * (long long)(sqrt(mid/i));
                if (counter >= cars) break;
            }
            if (counter >= cars) {
                ans = mid;
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }
};

complexity

• Time: O(n + max_rank * log (max_rank * m^2))
  • where n = ranks.size(), max_rank = max(ranks) and m = cars
• Space: O(max_rank)

learnings

• I think I misinterpreted constant time operations; just because a variable has limits of e.g. 1 <= n <= 100 does not make a constant time operation since it is always smaller than 101

time taken

• 6 minutes and 42.67 seconds
  • definitely not only timing when I do the question quickly