Equilibrium index of an array

Equilibrium index of an array A with length n is an index such that the sum of elements at lower indecies is equal to the sum of elements at higher indecies. Design an algorithm to find a equilibrium index of an array A in linear time with O(1) variables.

Solution:

Let LS[i] be the sum of elements A[1] to A[i] and RS[i] be the sum of elements A[i] to A[n]. If we computed LS and RS, then we can check whether LS[i – 1] equals RS[i + 1] for every 1 ≤ i ≤ n – 1. If LS[i – 1] = RS[i + 1] for some i, then i is an equilibrium index. Since LS and RS can be computed in linear time by traversing the array, this problem can be solved in linear time with linear space usage.

We can improve algorithm’s space usage by the following way. Let S be the sum of all elements in A. Since LS[i] + RS[i + 1] = S, if we have S, then we only need to store one of the arrays LS and RS. Moreover, since the algorithm checks whether LS[i] equals RS[i + 1] for i = 1 to n – 1 sequentially, the algorithm needs only the value LS[i] not the whole array LS. Since LS[i] = LS[i – 1] + A[i], LS[i] can be computed from LS[i – 1]. Thus, we can reduce the number of variables to constant.

解法：

令LS[i]表示A[1]到A[i]之和，RS[i]表示A[i]到A[n]之和。如果已經計算出LS和RS，那我們只需要對所有1 ≤ i ≤ n – 1，檢查LS[i – 1]等不等於RS[i + 1]，如果相等的話，i就是equilibrium index。 因為LS和RS可以在線性時間內計算出來，這問題可以在線性時間內解決，只是所需的空間也是線性的。

我們可以用以下技巧來減少空間使用量。令S為A中所有元素的總和。因為LS[i] + RS[i + 1] = S，如果已經計算出S，那麼我們就只需要儲存LS和RS其中之一即可。另外，因為演算法從i = 1到n – 1循序檢查 是否LS[i]等於RS[i + 1]，演算法只需要LS[i]的資訊即可，而不需要整個LS陣列。因為LS[i] = LS[i – 1] + A[i]，LS[i]可以很容易的藉由LS[i – 1]計算出。因此，演算法只需要使用常數個變數即可得到解答。

Reference: GeeksforGeeks