Any one considered linear space perspective for this problem? (not solved yet but interesting!)

• The problem can be reinterpreted as a pure math problem of linear space projection.

Consider each person's ID as an index and a transaction `[i, j, y]` as number yi,j, then we can form an NxN matrix Y = (yi,j), which has property that transpose YT = -Y, where we consider if person `i` gave `j` \$`y` then it is equivalent to say person `j` gave `i` -\$`y`. Note that such matrices form a linear space (i.e., linearly closed)

• Y = {Y in RNxN: YT = -Y }.

Now let's consider what does it mean by settling the debt? When the debt is settled for person `i`, it means neither `i` owes any money from other people nor other people owes `i` any money, so we have each row sum Σj=1:Nyi,j = 0. Such special matrices from Y actually form a subspace (i.e., linearly closed)

• X = {X in Y: Xe = 0 }, with e = (1, 1, ...,1) in RN.

That is, subspace X is the subset of Y which is orthogonal to vector e.

If we define a metric ||.|| on matrices to count number of non-zero entries:

• ||Y|| = Σi,j=1:N|sgn(yi,j)|, ( sgn(.) is the sign function)

Then the debt settling problem is transformed to a linear space projection problem:

• Given a Y in space Y, find the minimum projection distance P(X) = ||Y - X||, where X in subspace X.

Note that metric ||.|| indeed defines a distance with distance inequality: ||A + B|| ≤ ||A|| + ||B||.

But I haven't figured out a way to go from here yet. Maybe I will try another day.

Anyone interested to try this way?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.