FastPrepShortest City Route with the Most Intermediate Stops
Problems/Shortest City Route with the Most Intermediate Stops

Shortest City Route with the Most Intermediate Stops

JP Morgan Chase logoJP Morgan Chase● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a JP Morgan Chase intern onsite interview. The candidate describes a route in a 2D city from a source to a destination that is short and covers many cities along the way. Their BFS heuristic guided by straight-line distance satisfied the interviewer, but we do not know it is optimal. Our version is about 60% the same as that route goal. We chose these things, and did not recover them from the interview: every pair of cities is connected, Manhattan distance, distance comes first in priority, routes are simple, ID breaks ties, and the limits and examples.

A list cities gives distinct points on a 2D plane; a city’s ID is its array index. For this exercise, assume travel is allowed directly between any two different cities and costs their Manhattan distance: |x1-x2| + |y1-y2|. A route starts at source, ends at destination, and visits each city at most once.

First minimize total travel distance. Among routes with that minimum distance, maximize the number of intermediate cities. If those quantities tie, return the lexicographically smallest sequence of city IDs, including both endpoints.

The goal is a short route through as many intermediate 2D cities as possible, using the travel graph, Manhattan costs, strict priority order and tie rule above. Physical distance is the primary objective; counting graph hops alone does not solve this contract.

Function

planCityRoute(cities: int[][], source: int, destination: int) → int[]

Examples

Example 1

cities = [[0,0],[1,0],[1,1],[2,1],[2,2]]source = 0destination = 4return = [0,1,2,3,4]

This route has Manhattan distance 4, equal to the direct distance, and visits all three intermediate cities.

Example 2

cities = [[0,0],[1,0],[0,1],[1,1]]source = 0destination = 3return = [0,1,3]

The routes via city 1 and via city 2 both have distance 2 and one intermediate city. The lexicographically smaller ID sequence goes via 1; visiting both would make a longer route.

Constraints

  • For this exercise, assume 2 <= cities.length <= 100 and cities[i].length == 2.
  • -1000 <= cities[i][j] <= 1000.
  • 0 <= source < cities.length and 0 <= destination < cities.length.
  • Cities have pairwise distinct coordinates and source != destination.

More JP Morgan Chase Onsite Interview questions

  • LFU CacheONSITE INTERVIEW · Seen Nov 2026
  • LRU CacheONSITE INTERVIEW · Seen Nov 2026
  • Employees Above Average SalaryONSITE INTERVIEW · Seen Sep 2026
  • Highest-Earning Employees By DepartmentONSITE INTERVIEW · Seen Sep 2026
  • K Largest Integers in Descending OrderONSITE INTERVIEW · Seen Aug 2026
  • Tile a Three-Row Board with DominoesONSITE INTERVIEW · Seen Jan 2026
  • Two SumONSITE INTERVIEW · Seen Nov 2025
  • Intersection of Two ListsONSITE INTERVIEW · Seen Jan 2025
  • Maximum Subarray SumONSITE INTERVIEW · Seen Jan 2025
  • Fibonacci NumberONSITE INTERVIEW · Seen Nov 2024

Similar questions at other companies

  • Parallel Courses IIISnowflake · ONSITE INTERVIEWSnowflake interview questions
  • Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Grid Robot Route with Charging PrioritiesUber · PHONE SCREEN · ONSITE INTERVIEWUber interview questions
  • Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
  • Minimum Semesters With Course CapacityAmazon · ONSITE INTERVIEW
  • Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
  • Shortest Path Visiting All NodesInMobi · ONSITE INTERVIEWInMobi interview questions
  • Minimum Distance Matching in a ForestScale AI · PHONE SCREEN · ONSITE INTERVIEWScale AI interview questions
  • Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
  • Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions

Interview reports that mention this question

  • JPMorgan Tech Intern Interviews: 43 Experiences (Part 1 of 5)

JP Morgan Chase interview experiences

  • JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
  • JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
  • JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
  • JP Morgan Chase Data and AI Intern Superday: 11 Experiences
  • JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)
All JP Morgan Chase interview questionsSee JP Morgan Chase hiring insights
Saved
class Solution {
    public int[] planCityRoute(int[][] cities, int source, int destination) {
        // Write your code here.
    }
}
Checking account…