__source__ = 'https://leetcode.com/problems/find-pivot-index/description/'
# Time:  O(N)
# Space: O(1)
#
# Description: Leetcode # 724. 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, we should return -1. If there are multiple pivot indexes,
# you should return the left-most pivot index.
#
# Example 1:
# Input:
# nums = [1, 7, 3, 6, 5, 6]
# Output: 3
# Explanation:
# The sum of the numbers to the left of index 3
# (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
# Also, 3 is the first index where this occurs.
# Example 2:
# Input:
# nums = [1, 2, 3]
# Output: -1
# Explanation:
# There is no index that satisfies the conditions in the problem statement.
# Note:
#
# The length of nums will be in the range [0, 10000].
# Each element nums[i] will be an integer in the range [-1000, 1000].
#
import unittest
# 40ms 98.25%
class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        S = sum(nums)
        leftsum = 0
        for i, x in enumerate(nums):
            if leftsum == (S - leftsum - x):
                return i
            leftsum += x
        return -1


class TestMethods(unittest.TestCase):
    def test_Local(self):
        self.assertEqual(1, 1)


if __name__ == '__main__':
    unittest.main()

Java = '''
# Thought: https://leetcode.com/problems/find-pivot-index/solution/
# Approach #1: Prefix Sum [Accepted]
#
# 100% 15ms
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0, leftsum = 0;
        for (int x: nums) sum += x;
        for (int i = 0; i < nums.length; i++) {
            if (leftsum == sum - nums[i] - leftsum) return i;
            leftsum += nums[i];
        }
        return -1;
    }
}
'''