Minimum Speed to Arrive on Time

📋

Minimum Speed to Arrive on Time

Edge cases:

</>

IDE

def min_speed_on_time(dist: list[int], hour: float) -> int:public int minSpeedOnTime(int[] dist, double hour)int minSpeedOnTime(vector<int>& dist, double hour)function minSpeedOnTime(dist, hour)

def min_speed_on_time(dist, hour):
    # Write your solution here
    pass

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int minSpeedOnTime(vector<int>& dist, double hour) {
    // Write your solution here
    return -1;
}

function minSpeedOnTime(dist, hour) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when speed 1 sufficesNot correctly computing total time with ceil for intermediate segments or incorrect feasibility check.✅ Apply ceil to all but last segment travel times before summing and comparing to hour.

Wrong: Speed too high due to ignoring ceil roundingUsing fractional times for all segments without ceil leads to overestimating required speed.✅ Use math.ceil for all but last segment travel times to correctly compute total time.

Wrong: Speed returned when hour < n-1Not checking the minimum possible time constraint before binary search.✅ Add early return -1 if hour < dist.length - 1.

Wrong: Incorrect speed due to floating point comparison errorsComparing floating point total time and hour without tolerance or using fractional speeds.✅ Use integer speeds only and compare with a small epsilon tolerance.

Wrong: TLE on large inputsUsing linear search on speed or inefficient feasibility checks.✅ Implement binary search on answer space with O(n log(maxSpeed)) complexity.

✓

Test Cases

Focus on handling boundary inputs like empty arrays and single segments correctly.

Watch out for common algorithmic traps like ignoring ceil rounding and floating point precision.

Optimize your solution to binary search on answer space to handle large inputs efficiently.

t1_01basic

Input{"dist":[1,3,2],"hour":6}

Expected1

⏱ Performance - must finish in 2000ms

At speed 1, times are [1/1=1, 3/1=3, 2/1=2], total 6 hours exactly.

💡 Consider binary searching the speed between 1 and a large upper bound.

💡 Check if total travel time with ceil for all but last segment is within hour.

💡 Return the minimum speed that satisfies the time constraint.

Why it failed: Returned wrong speed or -1 despite speed 1 sufficing. Fix: correctly compute total time using ceil for all but last segment and compare to hour.

✓ Correctly found minimum speed matching canonical example.

t1_02basic

Input{"dist":[1,3,2],"hour":2.7}

Expected3

⏱ Performance - must finish in 2000ms

At speed 3, times are [ceil(1/3)=1, ceil(3/3)=1, 2/3=0.666...], total 2.666... ≤ 2.7.

💡 Try speeds higher than 1 to reduce total time.

💡 Remember to ceil times for all but last segment.

💡 Check speed 3 to see if total time fits within hour.

Why it failed: Incorrect speed returned due to ignoring ceil on intermediate segments or incorrect comparison with hour. Fix: apply ceil properly and compare total time to hour.

✓ Correctly computed minimum speed for fractional hour.

t2_01edge

Input{"dist":[],"hour":1}

Expected-1

⏱ Performance - must finish in 2000ms

Empty dist array means no travel needed, but problem constraints require at least one segment; return -1 as invalid input.

💡 Check how your code handles empty dist arrays.

💡 Ensure function returns -1 if no segments to travel.

💡 Add a guard clause for empty dist input.

Why it failed: Function crashes or returns invalid speed on empty dist. Fix: add check for empty dist and return -1 immediately.

✓ Properly handles empty dist input by returning -1.

t2_02edge

Input{"dist":[5],"hour":5}

Expected1

⏱ Performance - must finish in 2000ms

Single segment with hour exactly equal to dist[0], minimum speed is 1.

💡 For single segment, speed = dist[0] / hour.

💡 Since speed must be integer and at least 1, check if speed 1 suffices.

💡 Return 1 if dist[0] ≤ hour.

Why it failed: Returned -1 or speed > 1 incorrectly for single segment with hour equal to dist[0]. Fix: handle single segment case correctly without ceil.

✓ Correctly returns speed 1 for single segment equal to hour.

t2_03edge

Input{"dist":[1,1,1],"hour":2}

Expected-1

⏱ Performance - must finish in 2000ms

Hour less than number of segments - 1 (3 segments, hour=2 < 2), impossible to arrive on time.

💡 Minimum time for n segments is at least n-1 hours due to waiting.

💡 If hour < n-1, return -1 immediately.

💡 Check this boundary before binary searching.

Why it failed: Returned speed instead of -1 when hour < n-1. Fix: add early return for hour < n-1 condition.

✓ Correctly returns -1 when hour less than n-1.

t2_04edge

Input{"dist":[100000,100000],"hour":200000}

Expected1

⏱ Performance - must finish in 2000ms

Large distances with large hour; minimum speed close to 1 suffices.

💡 Check if speed 1 suffices for large hour values.

💡 Calculate total time with ceil for all but last segment.

💡 Return 1 if total time ≤ hour.

Why it failed: Returned speed > 1 incorrectly for large hour allowing speed 1. Fix: correctly compute total time and compare to hour.

✓ Correctly returns speed 1 for large hour and distances.

t3_01corner

Input{"dist":[1,3,2],"hour":1.9}

Expected-1

⏱ Performance - must finish in 2000ms

Impossible to arrive on time even at max speed; total time always exceeds hour.

💡 Check if your feasibility function correctly handles impossible cases.

💡 Verify that total time calculation uses ceil for all but last segment.

💡 Return -1 if no speed in range satisfies time constraint.

Why it failed: Returns a speed instead of -1 for impossible case. Fix: ensure binary search returns -1 if no feasible speed found.

✓ Correctly returns -1 for impossible arrival time.

t3_02corner

Input{"dist":[1,1,1],"hour":3}

Expected1

⏱ Performance - must finish in 2000ms

Greedy trap: assuming fractional speeds for all segments ignoring ceil leads to wrong speed. Minimum speed is 1.

💡 Beware of ignoring ceil on intermediate segments.

💡 Use ceil for all but last segment to avoid greedy mistakes.

💡 Check total time with ceil and last segment fractional time.

Why it failed: Returns speed > 1 due to ignoring ceil rounding on intermediate segments. Fix: apply ceil properly on all but last segment.

✓ Correctly handles ceil rounding avoiding greedy trap.

t3_03corner

Input{"dist":[100000,100000],"hour":2.01}

Expected99951

⏱ Performance - must finish in 2000ms

Tests floating point precision and 0/1 knapsack confusion; speed must be integer and minimal to fit hour with two decimals.

💡 Check floating point precision when comparing total time to hour.

💡 Ensure speed is integer and binary search handles floating hour correctly.

💡 Use a small epsilon to avoid floating point errors.

Why it failed: Returns incorrect speed due to floating point comparison errors or treating speed as fractional. Fix: use integer speeds and careful floating point comparison.

✓ Correctly handles floating point hour and integer speed constraints.

t4_01performance

Input{"dist":[100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000],"hour":1000000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and large hour; O(n log(maxSpeed)) solution must complete within 2 seconds.

💡 Use binary search on speed instead of linear search.

💡 Optimize feasibility check to O(n) per iteration.

💡 Avoid floating point errors by careful comparison.

Why it failed: TLE due to linear search or inefficient feasibility check. Fix: implement binary search on answer space with O(n log(maxSpeed)) complexity.

✓ Efficient binary search solution passes performance test.

Practice

1. Consider the following Python code implementing the optimal approach to find k closest elements to x in a sorted array. What is the returned output when calling findClosestElements([1, 3, 5], 2, 4)?

easy

A. [1, 3]

B. [3, 4]

C. [1, 5]

D. [3, 5]

Solution

1. Step 1: Initialize variables

   Array length is 3, k=2, so low=0, high=1.

2. Step 2: First iteration of binary search

   Calculate mid = (0+1)//2 = 0. Compare x - arr[mid] = 4 - 1 = 3 and arr[mid + k] - x = arr[2] - 4 = 5 - 4 = 1. Since 3 > 1, set low = mid + 1 = 1.

3. Step 3: Loop ends as low == high == 1

   Return arr[1:3] = [3, 5].

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search correctly chooses window starting at index 1 [OK]

Hint: Check mid and window edges distances carefully [OK]

Common Mistakes:

• Off-by-one error in slicing window
• Incorrect comparison direction in if condition
• Returning wrong slice boundaries

2. You are given an array that was originally sorted in ascending order but then rotated at some unknown pivot. The array may contain duplicates. Your task is to find the minimum element efficiently. Which approach best guarantees an optimal solution for this problem?

easy

A. Use a simple linear scan to find the minimum element by checking all elements.

B. Use a greedy approach that picks the smallest element seen so far while iterating from the start.

C. Use a dynamic programming approach to store minimum values for subarrays and combine results.

D. Use a modified binary search that handles duplicates by shrinking the search space when elements at mid and high are equal.

Solution

1. Step 1: Understand problem constraints

   The array is rotated and may contain duplicates, which complicates the binary search because duplicates can hide the pivot.

2. Step 2: Identify suitable algorithm

   Modified binary search that shrinks the search space when duplicates are encountered ensures correctness and efficiency on average.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Modified binary search handles duplicates correctly [OK]

Hint: Duplicates require shrinking high pointer in binary search [OK]

Common Mistakes:

• Assuming simple binary search works without handling duplicates
• Using greedy or DP unnecessarily

3. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a greedy approach by repeatedly picking the smallest element from the matrix without extra data structures.

B. Flatten the matrix into a list, sort it, and return the kth element.

C. Apply dynamic programming to build a table of smallest elements up to k.

D. Use a min-heap to merge the sorted rows, extracting the smallest elements until the kth is found.

Solution

1. Step 1: Understand problem constraints

   The matrix rows and columns are sorted, so each row is sorted and each column is sorted independently.

2. Step 2: Identify the optimal approach

   Using a min-heap to merge sorted rows efficiently extracts the smallest elements in ascending order, achieving O(k log n) time, better than flattening and sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges sorted lists optimally [OK]

Hint: Min-heap merges sorted rows efficiently [OK]

Common Mistakes:

• Assuming flatten and sort is optimal
• Confusing DP with this problem
• Thinking greedy without data structures works

4. The following code attempts to find the minimum in a rotated sorted array without duplicates. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line calculating mid = (left + right) // 2

B. Line calculating prev = mid - 1

C. Line checking if nums[mid] < nums[prev]

D. Line updating left = mid + 1

Solution

1. Step 1: Identify prev index calculation

   Prev is set to mid - 1 without modulo, which can be -1 if mid=0, causing out-of-bound or incorrect access.

2. Step 2: Correct calculation uses modulo to wrap around

   Prev should be (mid - 1 + n) % n to handle circular indexing safely.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prev index must wrap around to avoid negative index [OK]

Hint: Prev index must use modulo to avoid negative index [OK]

Common Mistakes:

• Forgetting modulo on prev index
• Assuming mid > 0 always
• Ignoring circular array property

5. Suppose the array can contain duplicate elements and you want to find the first position where the target can be inserted (i.e., the leftmost insertion point). Which modification to the binary search algorithm correctly achieves this?

hard

A. When nums[mid] >= target, recurse on the left half; else recurse on the right half.

B. Change the base case to return right instead of left when left > right.

C. When nums[mid] > target, recurse on the right half; else recurse on the left half.

D. Use linear scan after binary search to find the first occurrence.

Solution

1. Step 1: Understand requirement for leftmost insertion

   We must find the earliest index where target can be inserted, including duplicates.

2. Step 2: Modify binary search condition

   If nums[mid] >= target, recurse left to find earlier occurrence; else recurse right.

3. Step 3: Avoid linear scan for efficiency

   Linear scan after binary search defeats O(log n) goal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition ensures leftmost insertion index found efficiently [OK]

Hint: For leftmost insert, recurse left on >= target [OK]

Common Mistakes:

• Recursing right on >= target misses leftmost index
• Returning right instead of left at base case
• Using linear scan after binary search