Be careful with argument order and return values

I was working on this leetcode question https://leetcode.com/contest/weekly-contest-212/problems/path-with-minimum-effort/ using backtracking and spent some time debugging strange output. This article discusses some pitfalls when using Recursion with global variables, how to handle them, and how to change the code from global to local.
Disclaimer: Backtracking only passing 15/75 test cases and Time Limit Exceeded for the rest, the purpose of this article is to highlight possible issues with global variables rather than give the best solutions. For more beautiful solutions using Binary Search, Dijkstra and Kruskal, watch Alex’s walkthrough (beginning 7:26) at https://www.youtube.com/watch?v=AM__3Zx1XNw&t=2325s&ab_channel=AlexWice
Problem

The problem is to find the path with minimum effort after walking from top left to bottom right with each step allowing 4 directions of up, down, left, right. effort
is defined as the maximum absolute difference in values between any 2 consecutive squares.
Notebook containing implementation with global vs no global variable: https://gist.github.com/gitgithan/a818d336c2309852a21d99efd619238d
Backtracking Overview
My backtracking solution was to use a visited
2D array to track visits.
Starting from the top-left cell, we try to move in the order of down, right, up, left (this order reaches the destination faster than some other orders, so the global min can be updated earlier, and used to bound/speed up the exploration of future paths) if within rectangle bounds and not visited before. Before moving (recursing), the visit is marked so future attempts to visit will return False for if valid()
.
Along the way, the effort (intialized to 0) of the path is updated using abs difference between the cell we are going to visit and current cell. If we reach base case (bottom-right cell), return the effort.
Once a single direction of recursion is complete, we update the global minimum min_effort
(initialized to math.inf
) and unmark the cell in that direction.
Once all 4 directions from the current cell is done, we return math.inf
back up the call stack so it does not wrongly influence the min() of the caller.
BUG

This output of five 2, followed by two inf was mindboggling. It looked like the global variable min_effort
which was updated from inf to 2 after the first solution (1, down to 3, down to 5, right to 3, right to 5) went back to inf! The final answer(path of 1, 2, 3, 4, 5) was also wrongly inf instead of 1.

Those five 2 correspond to the algorithm backtracking from destination 5 to 4,3,2,8,3,5 because all these have all 4 directions either visited or out of bounds, so the next path to try is to go right from 1,0 to 1,1 (3 to 8).
How can a global variable go back to an un-updated state?
The problem is with the line min_effort = min(min_effort,find_path(...))
Because python evaluates arguments from left to right, the global variable min_effort
was already evaluated before entering the recursion, so whatever happens in the recursion (including updates to global variable) has no effect on min_effort
.
At the scope of the 3 in bottom middle of the grid, the algorithm has not yet found a successful path (the 1st path being 1,3,5,3,5), so min_effort
was still math.inf
at that moment, and min(math.inf,math.inf)
became inf.
3 Fixes
- Swap arguments
A fix is to simply swap the order of arguments to min_effort = min(find_path(...), min_effort)
. This gives the recursion a chance to update the global variable first before comparison.
- Save into variable first
If you still wanted to maintain the old order as a matter of preference, the recursion can be calculated and saved into a variable first.
recursion_res = find_path(...)
min_effort = min(min_effort, recursion_res)
- Remove global variables completely
This was prompted by Leetcode giving wrong test results running all test cases, but running the failing case individually as custom input gives the correct result. If you insist on using globals on leetcode, copy the result, clear the global, and return the copied result so the cleared global is ready for the next test case.
Two changes:
- Add the previously global variable to recursive function signature
find_path(...,min_effort)
- Return
min_effort
rather thanmath.inf
This will ensure the minimum effort path is always propagated through the recursive calls. If you ask why not return min_effort
while using global variable, that is workable too, but unnecessary, since if you avoid the gotcha mentioned above, min_effort
would have been updated to a non-inf value before the min(min_effort,find_path(...))
comparison, so even if the 2nd argument returns math.inf, the 1st argument will always be updated to the correct value once any path first reaches the destination. Also, math.inf
felt more representative of a "no solution/bad value".
However, the argument in support of return min_effort
rather than return math.inf
is that it more accurately represents the most updated program state. Also, we can totally avoid the gotcha handling (the 1st two fixes described) and use min(min_effort,find_path(...))
directly because with return min_effort
the 2nd argument will always be updated, so a "pre-recursion evaluated" min_effort
that could contain its initialized math.inf
in the 1st argument causes no harm. (exactly opposite situation of the previous paragraph).
Improving the solution
Since we are looking for the global minimum, any path can be influenced by the results of any other path. This offers a chance for the current best result to short-circuit future paths once they are found to have longer effort than the current min_effort
. This can be achieved by wrapping the backtracking section (visit,recurse,unvisit) with an extra check if updated_effort < min_effort:
to largely reduce exploration steps, using "less than" because there is no point trying something that won’t reduce the current best.
if updated_effort < min_effort:
visited[row,col] = 1
min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col))
visited[row,col] = 0
Comparing global vs local
Global pros:
- Lax return values allowed (
math.inf
ormin_effort
) - Convenient coding (less parameter passing and simpler recursive functions)
Global cons:
- Don’t gel with online coding platforms (risky for job interview automated coding assessments)
- Constantly have to be aware of side effects and variables not within current stack
- Sensitive to function argument ordering (the root of all these troubles)
Local pros:
- Easier debugging/tracing focusing on local problem space
- Less side effects
Local cons:
- More verbose function signature (more items to track means longer signature)
- Lose ability to return
math.inf
, have to returnmin_effort
to propagate updated results back to rest of program
Doing it wrong more valuable than doing it right
When using globals, if I had returned min_effort
or coded properly using fix 2 above initially, I would not have seen this gotcha at all. It’s a blessing in disguise that returning the most intuitively correct value and being lazy with (possibly) extraneous variable assignments allowed me to strengthen my understanding of python evaluation order and debugging skills.