bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Hard1-D Dynamic ProgrammingLC 818

Race Car

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse): When you get an instruction 'A', your car does the following: position += speed speed = 2 When you get an instruction 'R', your car does the following: If your speed is positive then speed = -1 otherwise speed = 1Your position stays the same. For example, after commands "AAR ", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1. Given a target position target, return the length of the shortest sequence of instructions to get there.

Asked at 1 company
Google
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode