Scale Engineer

Maximum Earnings From Taxi

Med
#1829Time: O(n + R) - Preprocessing the `R` rides into a map takes O(R). The main loop runs `n` times. Inside the loop, we access the map. Over all `n` iterations, the inner loop (iterating over rides ending at `i`) will execute a total of `R` times. Therefore, the total time complexity is O(n + R).Space: O(n + R) - Requires O(n) for the DP array and O(R) for the map to store the preprocessed rides.1 company
Patterns
Dynamic Programming
Algorithms
Binary SearchSorting
Data structures
ArrayHash Table
Companies
Myntra

Prompt

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi who is willing to give a tipi dollar tip.

For each passenger i you pick up, you earn endi - starti + tipi dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

 

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

 

Constraints:

  • 1 <= n <= 105
  • 1 <= rides.length <= 3 * 104
  • rides[i].length == 3
  • 1 <= starti < endi <= n
  • 1 <= tipi <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most efficient approach for the given constraints. It uses dynamic programming where the state is tied to the points on the road. We build a dp array where dp[i] stores the maximum earnings we can have by the time we reach point i. The solution is built iteratively by considering the maximum earnings from the previous point and the potential earnings from any rides that drop off a passenger at the current point.

Algorithm

  • Preprocessing: Group the rides by their end point. A HashMap<Integer, List<int[]>> is an effective way to do this, mapping each end point to a list of rides that finish there.
  • DP Initialization: Create a dp array of size n + 1. dp[i] will represent the maximum earnings achievable up to point i on the road. Initialize all dp values to 0.
  • DP Iteration: Iterate from i = 1 to n.
    • For each point i, we have two main possibilities to determine dp[i]:
      1. No ride ends at i: In this case, we just drove from point i-1 to i without a passenger. The maximum earnings are the same as the earnings up to point i-1. So, we set dp[i] = dp[i-1].
      2. One or more rides end at i: For each ride [start, end, tip] where end == i, we calculate a potential new maximum earning. This would be the earnings from this ride (end - start + tip) plus the maximum earnings we had accumulated up to the start point of this ride (dp[start]).
    • We update dp[i] to be the maximum of dp[i-1] and all potential earnings calculated from rides ending at i.
  • Result: The final answer is the value stored in dp[n], which represents the maximum earnings after reaching the final destination.

Walkthrough

This dynamic programming approach defines its state based on the location on the road. We let dp[i] be the maximum possible earnings after arriving at point i. Our goal is to compute dp[n].

The transition for dp[i] is based on what happens at point i. To arrive at point i, we could have either driven from i-1 without a passenger, or we could have just completed a ride that ended at i.

  1. Base case: dp[0] = 0. No earnings before starting.
  2. Transition: For each point i from 1 to n:
    • The default maximum earning is inherited from the previous point: dp[i] = dp[i-1].
    • We then check if any rides end at point i. To do this efficiently, we first preprocess the rides into a map where keys are end points. For every ride [start, end, tip] with end == i, we calculate a potential new maximum earning: dp[start] + (end - start + tip). This represents the earnings from an optimal path to start, followed by taking this specific ride.
    • We update dp[i] with the maximum value found among dp[i-1] and all possibilities from rides ending at i.

This ensures that at each point i, dp[i] holds the optimal earnings. The final answer is dp[n].

import java.util.*; class Solution {    public long maxTaxiEarnings(int n, int[][] rides) {        // Group rides by their end point for efficient lookup.        // The map stores: endPoint -> List of {startPoint, tip}        Map<Integer, List<int[]>> ridesByEnd = new HashMap<>();        for (int[] ride : rides) {            ridesByEnd.computeIfAbsent(ride[1], k -> new ArrayList<>()).add(new int[]{ride[0], ride[2]});        }         // dp[i] will store the maximum earnings up to point i.        long[] dp = new long[n + 1];         for (int i = 1; i <= n; i++) {            // Option 1: Don't end a ride at point i. Earnings are same as up to i-1.            dp[i] = dp[i - 1];             // Option 2: Check if any rides end at point i.            if (ridesByEnd.containsKey(i)) {                for (int[] rideInfo : ridesByEnd.get(i)) {                    int start = rideInfo[0];                    int tip = rideInfo[1];                    long profit = (long)i - start + tip;                    // Compare with current max and update if this path is better.                    dp[i] = Math.max(dp[i], dp[start] + profit);                }            }        }         return dp[n];    }}

Complexity

Time

O(n + R) - Preprocessing the `R` rides into a map takes O(R). The main loop runs `n` times. Inside the loop, we access the map. Over all `n` iterations, the inner loop (iterating over rides ending at `i`) will execute a total of `R` times. Therefore, the total time complexity is O(n + R).

Space

O(n + R) - Requires O(n) for the DP array and O(R) for the map to store the preprocessed rides.

Trade-offs

Pros

  • Most efficient time complexity for the given constraints.

  • The DP state and transition directly model the problem's progression along the road, making it intuitive.

Cons

  • The space complexity is O(n + R), which can be large if n is very large.

Solutions

class Solution { private int m ; private int [][] rides ; private Long [] f ; public long maxTaxiEarnings ( int n , int [][] rides ) { Arrays . sort ( rides , ( a , b ) -> a [ 0 ] - b [ 0 ]); m = rides . length ; f = new Long [ m ]; this . rides = rides ; return dfs ( 0 ); } private long dfs ( int i ) { if ( i >= m ) { return 0 ; } if ( f [ i ] != null ) { return f [ i ]; } int [] r = rides [ i ]; int st = r [ 0 ], ed = r [ 1 ], tip = r [ 2 ]; int j = search ( ed , i + 1 ); return f [ i ] = Math . max ( dfs ( i + 1 ), dfs ( j ) + ed - st + tip ); } private int search ( int x , int l ) { int r = m ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( rides [ mid ][ 0 ] >= x ) { r = mid ; } else { l = mid + 1 ; } } return l ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem