[PHP] Contiguous Subarray: Stack-based Approach [Beats 100% Runtime & 100% Memory]
Intuition\nThe problem involves finding the maximum length of a contiguous subarray with an equal number of 0s and 1s. One way to approach this is to use a stac
# Intuition\nThe problem involves finding the maximum length of a contiguous subarray with an equal number of 0s and 1s. One way to approach this is to use a stack to keep track of the cumulative sum of elements in the array along with the corresponding index. The key idea is to identify subarrays with the same cumulative sum, as they indicate equal numbers of 0s and 1s.\n\n# Approach\nThe given solution uses a stack to maintain information about the cumulative sum, its corresponding index, and the length of the subarray with equal 0s and 1s. The stack is traversed as new elements are processed to find subarrays with the same cumulative sum.\n\n1. Initialize a stack with a tuple `[0, 0, 0]`, where the elements represent cumulative sum, previous cumulative sum, and the length of the subarray.\n\n2. Iterate through the array, updating the cumulative sum (`$pre`) at each step.\n\n3. Use a pointer `$j` to traverse the stack and find the rightmost element with cumulative sum less than the current cumulative sum. This is done to identify subarrays with the same cumulative sum.\n\n4. Calculate the length of the current subarray (`$curDp`) and update the result (`$res`).\n\n5. Remove elements from the stack where the cumulative sum is greater than or equal to the current subarray\'s cumulative sum.\n\n6. Push a new tuple into the stack with the current subarray\'s cumulative sum, previous cumulative sum, and length.\n\n7. Return the final result.\n\n# Complexity\n- Time complexity: O(n), where n is the size of the input array. The algorithm processes each element in the array once.\n\n- Space complexity: O(n), as the stack can potentially have at most n elements, where n is the size of the input array.\n\n# Code\n```\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @return Integer\n     */\n    function findMaximumLength($nums) {\n        $n = count($nums);\n        $stk = [[0, 0, 0]];\n        $pre = 0;\n        $res = 0;\n\n        for ($i = 0, $j = 0; $i < $n; $i++) {\n            $pre += $nums[$i];\n            $j = min($j, count($stk) - 1);\n\n            while ($j + 1 < count($stk) && $pre >= $stk[$j + 1][0]) {\n                $j++;\n            }\n\n            list($val, $prePre, $preDp) = $stk[$j];\n            $curDp = $preDp + 1;\n            $res = $curDp;\n\n            $last = $pre - $prePre;\n            while (!empty($stk) && end($stk)[0] >= $last + $pre) {\n                array_pop($stk);\n            }\n\n            array_push($stk, [$last + $pre, $pre, $curDp]);\n        }\n\n        return $res;\n    }\n}\n```
['Stack', 'PHP']