Minimum Time to Complete Trips

Hey fellow developers 👋

Welcome back to our DSA learning series!

In this series, we focus on problems that may look simple at first, but often require deeper thinking to solve efficiently. We are learning DSA just like you, so our goal is always to build intuition first — before jumping into code.

In this post, we are going to explore a problem that teaches you an important concept called Binary Search on Answer — Minimum Time to Complete Trips.

---

Problem Statement

We are given an array time[], where time[i] represents how much time the i-th bus takes to complete one trip.

Our goal is to find the minimum time required to complete totalTrips trips when all buses are working in parallel.

---

Understanding the Idea

Each bus keeps running continuously.

So, in a given time T:

• A bus with time t can complete T / t trips
• All buses together can complete the sum of these trips

Our task is to find the smallest time T for which total trips ≥ totalTrips.

---

Brute Force Approach

Idea

• Start checking from time T = 1
• For each T, calculate how many trips all buses can complete
• Stop when trips ≥ required trips

---

Brute Force Code (Java)

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long T = 1;

        while (true) {
            long trips = 0;
            for (int t : time) {
                trips += T / t; // trips by this bus in T time
            }

            if (trips >= totalTrips) return T;
            T++;
        }
    }
}

---

Why trips += T / t Works

If:

time[i] = 3
T = 6

Then:

6 / 3 = 2 trips

So dividing time gives us the number of trips completed.

---

Complexity (Brute Force)

Time Complexity: O(n × ans)

• n → number of buses
• ans → minimum required time

Since ans can be very large, this approach will TLE for big inputs.

Space Complexity: O(1)

---

Optimal Approach (Binary Search on Answer)

Instead of checking every time value, we can search the answer efficiently using binary search.

---

Key Observation

Time is monotonic:

• If we can finish in T time
• Then we can also finish in T + 1, T + 2, ...

So binary search is possible on time.

---

Search Space

• Lower Bound (lb) = 1
• Upper Bound (ub) = min(time) × totalTrips

Why?

Because in the worst case, the fastest bus does all trips alone.

---

Binary Search Logic

1. Find mid
2. Check if we can finish totalTrips in mid time
3. If yes → try smaller time
4. If no → increase time

When lb == ub, we get our answer.

---

Optimal Code (Java)

class Solution {

    public static boolean isAtleast(int[] time, long givenTime, int totalTrips) {
        long trips = 0;

        for (int t : time) {
            trips += givenTime / t;
            if (trips >= totalTrips) return true;
        }

        return false;
    }

    public long minimumTime(int[] time, int totalTrips) {

        int min = Integer.MAX_VALUE;
        for (int t : time) {
            min = Math.min(min, t);
        }

        long lb = 1;
        long ub = (long) min * totalTrips;

        while (lb < ub) {
            long mid = lb + (ub - lb) / 2;

            if (isAtleast(time, mid, totalTrips)) {
                ub = mid;
            } else {
                lb = mid + 1;
            }
        }

        return lb;
    }
}

---

Complexity (Optimal)

Time Complexity: O(n log(totalTrips))

Why?

• Binary search on answer space
• Each step takes O(n) to check feasibility

So:

O(n × log(searchSpace))
≈ O(n log(totalTrips))

Space Complexity: O(1)

---

Final Thoughts

This problem is a classic example of Binary Search on Answer.

Once you learn to recognize patterns like:

false false false true true true

Binary search becomes a powerful tool in your DSA journey.

If you read till here — thank you so much!

If you found this helpful, please like and share it with your coding friends to help us build a stronger community.