Equilibrium Index: Find index such that sum of left sub-array = right sub-array
For a given array, we need to find an index such that sum of left sub-array = right sub-array also called the Equilibrium Index. We solve this using brute force approach O(N^2) and using prefix array in linear O(N) time.
Tile Stacking Problem
We demonstrate how we will reduce the time complexity from O((k+1)^(m+1)) to O(N * M * K) to O(N * M). We have infinite number of tiles of sizes 1 to m. The task is calculate the number of different stable tower of height n with restriction that you can use at most k tiles of each size in the tower