educative.io

How is the local optimum the global optimum?

Courses
,
#1

The solution only checks from the begining of the array to the end of the array. How does it account for the fact that the array is circular as per the question?

Course: https://www.educative.io/courses/grokking-coding-interview-patterns-java
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-java/R8N0NQvo4W0

#3

Hello @Sriram_Balasubramani,

Let’s go over this problem in steps to answer you query. Please note that it’s given in the statement that the route is circular, so we don’t need to explicitly check that.

  1. At the start of the function, we check if it is possible to complete the journey based on total gas and cost.
  • If this check returns true, we know for sure that the journey is possible on this circular route.
  1. After that, all we need to do is to find the starting index of the journey, where the difference between the gas and the cost is positive. If, at any point, the gas in our tank drops below zero, we cannot reach the next station nor finish the circular route.

Hope this clears your confusion. Feel free to share more suggestions and queries. Thanks.