Skip to main content
Talentd

Minimum Cost Path with Alternating Directions I - Solution & Explanation

MediumPremiumFree on FleetCodeMathBrainteaser7 min read
Practice this problem

Problem Statement

You are given two integers m and n representing the number of rows and columns of a grid, respectively.

The cost to enter cell (i, j) is defined as (i + 1) * (j + 1).

The path will always begin by entering cell (0, 0) on move 1 and paying the entrance cost.

At each step, you move to an adjacent cell, following an alternating pattern:

  • On odd-numbered moves, you must move either right or down.
  • On even-numbered moves, you must move either left or up.

Return the minimum total cost required to reach (m - 1, n - 1). If it is impossible, return -1.

 

Example 1:

Input: m = 1, n = 1

Output: 1

Explanation:

  • You start at cell (0, 0).
  • The cost to enter (0, 0) is (0 + 1) * (0 + 1) = 1.
  • Since you're at the destination, the total cost is 1.

Example 2:

Input: m = 2, n = 1

Output: 3

Explanation:

  • You start at cell (0, 0) with cost (0 + 1) * (0 + 1) = 1.
  • Move 1 (odd): You can move down to (1, 0) with cost (1 + 1) * (0 + 1) = 2.
  • Thus, the total cost is 1 + 2 = 3.

 

Constraints:

  • 1 <= m, n <= 106

Approach Overview

Problem Overview: You need the minimum cost path from the start to the destination while strictly alternating movement directions. Consecutive moves cannot use the same direction, so the path must follow a fixed alternating pattern such as right–down–right–down or down–right–down–right.

Approach 1: Brute Force Path Enumeration (Exponential Time, O(2^n) time, O(n) space)

A direct way is to recursively generate every valid path while enforcing the alternating direction rule. At each step, you attempt a move only if it differs from the previous direction. Track the accumulated cost and update the minimum once the destination is reached. This guarantees correctness but becomes infeasible quickly because the number of paths grows exponentially with the grid size. This approach mainly helps validate edge cases and understand how the alternating constraint restricts valid paths.

Approach 2: Brain Teaser Pattern Evaluation (O(n) time, O(1) space)

The alternating rule drastically limits the number of possible paths. Instead of exploring many routes, observe that only two valid direction sequences can exist: starting with the first direction or starting with the second direction. For example, a path might follow R → D → R → D or D → R → D → R. Once the starting direction is chosen, the entire sequence becomes fixed because every step must alternate.

Iterate along the path defined by each possible pattern and accumulate the total cost of visited cells. If a pattern cannot reach the destination due to mismatched required moves, discard it. The minimum cost among the valid patterns is the answer. This turns the problem into a simple simulation rather than a search.

This technique works because the alternating constraint removes the combinatorial explosion typically seen in grid path problems. Instead of dynamic programming over many states, you evaluate at most two deterministic paths. The reasoning is closer to a brainteaser than a traditional graph traversal. The arithmetic and step counting aspects also connect to common math interview puzzles where constraints reduce possibilities dramatically.

Recommended for interviews: The brain teaser approach is what interviewers expect. Showing the brute-force idea first demonstrates that you understand the search space, but recognizing that only two alternating patterns exist shows strong problem‑solving intuition and reduces the complexity to linear time.

Solution

Due to the movement rules given in the problem, in fact, only the following three cases can reach the target cell:

  1. A 1 times 1 grid, with a cost of 1.
  2. A grid with 2 rows and 1 column, with a cost of 3.
  3. A grid with 1 row and 2 columns, with a cost of 3.

For all other cases, it is impossible to reach the target cell, so return -1.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Path EnumerationO(2^n)O(n)Conceptual understanding or validating constraints on very small inputs
Brain Teaser Pattern EvaluationO(n)O(1)General case. Only two alternating direction sequences need evaluation

Video Solution

3596. Minimum Cost Path with Alternating Directions I (Leetcode Medium) • Programming Live with Larry • 550 views views

Frequently Asked Questions

Is Minimum Cost Path with Alternating Directions I easy or hard?
The problem is rated Medium because the main difficulty lies in recognizing the constraint that drastically reduces the number of possible paths. Once you identify that only two alternating patterns exist, the implementation becomes straightforward and runs in linear time.
Minimum Cost Path with Alternating Directions I Python/Java solution
The implementation simulates two candidate paths: one starting with the first direction and the other with the opposite direction. For each step, alternate the direction and accumulate the grid cost until the destination is reached. This logic translates directly into Python, Java, C++, Go, or TypeScript with a simple loop.
How to solve Minimum Cost Path with Alternating Directions I in O(n)?
Recognize that strict alternation eliminates most possible paths. Only two sequences exist: one starting with the first direction and the other starting with the second. Simulate both paths, accumulate the cost of visited cells, and return the minimum valid result. This converts the problem from path search to simple linear simulation.
What is the best approach for Minimum Cost Path with Alternating Directions I?
The optimal approach evaluates the two possible alternating direction patterns. Since moves must alternate, once the starting direction is chosen the entire path sequence becomes fixed. Compute the total cost for both valid patterns and return the minimum. This runs in O(n) time with O(1) extra space.
Is Minimum Cost Path with Alternating Directions I asked at Google/Amazon/Meta?
Problems involving constrained grid paths and pattern-based reasoning appear frequently in interviews at companies like Google, Amazon, and Meta. While the exact question may vary, the underlying idea of reducing a search space using mathematical observation is a common interview theme.
What data structure is used in Minimum Cost Path with Alternating Directions I?
No complex data structure is required for the optimal solution. The algorithm relies on simple iteration and integer variables to track the current position and cumulative cost. The key insight is mathematical reasoning about the limited number of valid paths.
What is the time complexity of Minimum Cost Path with Alternating Directions I?
The optimal solution runs in O(n) time where n represents the number of steps in the path. Only two deterministic paths are evaluated, so the algorithm simply iterates along each path once. Space complexity remains O(1) because no additional data structures are required.

Ready to solve this problem?

Practice Minimum Cost Path with Alternating Directions I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer