Spaceship on Mission

This article is part of the Scaler Topics Fortnightly Contest - 24

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

Let x1= A[0] , x2= A[2] , x3= A[4] , y1=A[1], y2=A[3], y3=A[5]
Let d(P1,P2) be the Manhattan distance between points P1=(x1,y1) and P2=(x2,y2). Then d(P1,P2)=|x1−x2|+|y1−y2|.
Note that if you are going from P1 to P2 (or to P3) along the shortest path, the Manhattan distance will be decreasing with each move. So we have to find the next cell that is closer to both P2 and P3.
Now note that if they are in the bounding box of cells P2 and P3 then there are no such “next cell”, since d(X,P2)+d(X,P3) is constant and equal to d(P1,P2) if X is in the bounding box.
Let’s look at the total distance spaceship will travel: from one side it’s d(P1,P2)+d(P1,P3). But from the other side it’s 2⋅d(P1,X)+d(X,P2)+d(X,P3).
So,d(P1,X)=(d(P1,P2)+d(P1,P3)−(d(X,P2)+d(X,P3)))/2 .But since d(X,P2)+d(X,P3)=d(P2,P3) whichever X is chosen we can calculate answer as (d(P1,P2)+d(P1,P3)−d(P2,P3))/2+1 where +1 is because we are talking about cells P1, P2 and P3 and not just points.

Time Complexity: $O(1)$

Space Complexity: $O(1)$