Intuiting our way into $$O(n)/O(1)$$
IntuitionThe obvious thing is that we need to calculate the starting money for some worst case scenario and all other orderings of the transactions will be cove
# Intuition
The obvious thing is that we need to calculate the starting money for some worst case scenario and all other orderings of the transactions will be covered by yhis.

The first step along the way is noticing that the worst case will have all losses happen before any gains. Obviously, we need to at least be able to cover all the losses, so we need the sum of the losses.
Call the losses $$L$$ and the gains $$G$$.

The next step is to decide which loss would have to be last. Since we are losing money, that would be the loss that has the highest cost, regardless of its cashback. If we take all the other losses first, then we would need the sum of all those other losses plus the cost of that last loss in order to begin that last loss transaction.
Call the sum of all losses $$s$$, and the last loss $$l$$.
The amount we have just before the last loss is $$s-(cost_l-cashback_l)$$.
The worst case is given by $$\underset{L}{max}(s-(cost_l-cashback_l)+cost_l)$$.
Some simple algebra makes that $$\underset{L}{max}(s+cashback_l)$$.
Since $$s$$ is a constant this is equal to $$s + \underset{L}{max}(cashback_l)$$.
So to make sure we can begin all the loss transactions, we need the maximum of the cashback for all losses.

After that we need to decide which gain would be the first. Since we are gaining money, that would be the gain with the highest cost.
Calling the first gain $$g$$.
The amount we have before the first gain is $$s$$.
The worst case is given by $$\underset{G}{max}(s+cost_g)$$.
Again $$s$$ is a constant so this is equal to $$s+\underset{G}{max}(cost_g)$$.

Finally we need to combine the requirement for the losses and the gains. If we have enough money for the larger of the two that's also enough money for both.
The overall worst case is given by $$s+max(\underset{L}{max}(cashback_l), \underset{G}{max}(cost_g))$$

This is enough to solve the problem in linear time, but there's an additional simplification that can be made. Notice
* For $$L$$, we need $$\underset{L}{max}(cashback_l)$$ and $$cashback_l < cost_l$$.
* For $$G$$, we need $$\underset{G}{max}(cost_g)$$ and $$cost_g < cashback_g$$.

This means across $$T=L+G$$ we can always use $$min(cost_t, cashback_t)$$ and that our worst case scenario is just $$s+\underset{T}{max}(min(cost_t, cashback_t))$$. The code is certainly smaller and cleaner if we use this fact. It is arguably less readable and whether it is faster depends on whether the implementation of `min` is faster or slower than `if ... < ... then ... else ...`. In Go it is; your mileage may vary.

# Approach
1. Initialize a `sum` of losses and a min additional `seed`, both to `0`.
2. Iterate across the transactions
    * Add the loss to `sum`, ignoring any gains.
    * Update the `seed` with `min(cost, cashback)`.
3. Return `sum + seed`.

# Complexity
- Time complexity: $$O(n)$$
We iterate through the array of transactions taking $$O(n)$$ time.
On each iteration we do 2 $$O(1)$$ operations taking $$O(1)+O(1)$$ time.
$$O(n)×(O(1)+O(1))=O(n)$$

- Space complexity: $$O(n)$$
We create 2 atomic variables outside the loop taking $$O(1)+O(1)$$ space.
On each iteration we create 2 atomic variables taking $$O(1)+O(1)$$ space, which is reclaimed at the end of each iteration.
$$(O(1)+O(1))+(O(1)+O(1))=O(1)$$

# Code
```golang []
func minimumMoney(transactions [][]int) int64 {

    var seed, sum int

    for _, t := range transactions {
        cost, cashback := t[0], t[1]
        sum += max(0, cost - cashback)
        seed = max(seed, min(cost, cashback))
    }

    return int64(sum + seed)
}
```
['Go']