724. Find Pivot Index (https://leetcode.com/problems/find-pivot-index/): Given an array of integers nums, write a method that returns the "pivot" index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, …

724. Find Pivot Index (#1 Array + DP).java

// Array + DP solution: store the prefix sum in array and scan from left
// Time: O(n), 1ms
// Space: O(n), 42.4mb
class Solution {
    public int pivotIndex(int[] nums) {
        // Count the prefix sum of nums: prefix[i] = nums[0] + nums[1] + .. + nums[i - 1]
        int len = nums.length, sum = 0;
        int[] prefix = new int[len];
        for(int i = 0; i < len; i++) {
            prefix[i] = sum;
            sum += nums[i];
        }
        
        // Find the pivot using the sum
        for(int i = 0; i < len; i++) {
            // !!: Take care the pivot element and the last one
            if(prefix[i] == prefix[len - 1] - prefix[i] - nums[i] + nums[len - 1]) return i;
        }
        
        return -1;
    }
}

724. Find Pivot Index (#2 Array).java

// Array solution: keep the left and right sum as we scan ->
// Time: O(n), 1ms
// Space: O(1), 43mb
class Solution {
    public int pivotIndex(int[] nums) {
        // Init the left & right sum
        int left = 0, right = 0;
        for(int num : nums) right += num;
        
        // Scan -> to find where left == right
        for(int i = 0; i < nums.length; i++) {
            // @@: Update, check, update
            right -= nums[i];
            
            if(left == right) return i;
            
            left += nums[i];
        }
        
        return -1;
    }
}