plaintext
function arrange_soldiers(n, heights)
max_val := maximum value in heights
min_val := minimum value in heights
pos_max := leftmost position of max_val
pos_min := rightmost position of min_val
swaps := pos_max + (n - 1 - pos_min)
// If max is to the right of min, they cross
if pos_max > pos_min then
swaps := swaps - 1
return swaps
You scan the array once to find positions of the maximum and minimum values. For the maximum, you want the leftmost occurrence. For the minimum, you want the rightmost. Time: . Space: .