package com.fishercoder.solutions;

/**
 * 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].
 */
public class _724 {
    public static class Solution1 {
        /**Space: O(n)
         * Time: O(n)*/
        public int pivotIndex(int[] nums) {
            if (nums == null || nums.length == 0) {
                return -1;
            }
            int[] sums = new int[nums.length];
            sums[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                sums[i] = sums[i - 1] + nums[i];
            }
            for (int i = 0; i < nums.length; i++) {
                if (i == 0 && 0 == sums[nums.length - 1] - sums[i] || (i > 0 && sums[i - 1] == sums[nums.length - 1] - sums[i])) {
                    return i;
                }
            }
            return -1;
        }
    }

    public static class Solution2 {
        /**Space: O(1)
         * Time: O(n)*/
        public int pivotIndex(int[] nums) {
            int total = 0;
            for (int num : nums) {
                total += num;
            }
            int sum = 0;
            for (int i = 0; i < nums.length; sum += nums[i++]) {
                if (sum * 2 == total - nums[i]) {
                    return i;
                }
            }
            return -1;
        }
    }
}

@@ -33,940 +33,8 @@
 s;%0A%0A
-/**%0A * 724. Find Pivot Index%0A *%0A * Given an array of integers nums, write a method that returns the %22pivot%22 index of this array.%0A * We define the pivot index as the index where the sum of the numbers to the left of the index is equal%0A * to the sum of the numbers to the right of the index.%0A * If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.%0A%0A Example 1:%0A Input:%0A nums = %5B1, 7, 3, 6, 5, 6%5D%0A Output: 3%0A Explanation:%0A The sum of the numbers to the left of index 3 (nums%5B3%5D = 6) is equal to the sum of numbers to the right of index 3.%0A Also, 3 is the first index where this occurs.%0A%0A Example 2:%0A Input:%0A nums = %5B1, 2, 3%5D%0A Output: -1%0A Explanation:%0A There is no index that satisfies the conditions in the problem statement.%0A%0A Note:%0A The length of nums will be in the range %5B0, 10000%5D.%0A Each element nums%5Bi%5D will be an integer in the range %5B-1000, 1000%5D.%0A */%0A
 publ
@@ -88,32 +88,44 @@
 n1 %7B%0A        /**
+%0A         * 
 Space: O(n)%0A    
@@ -133,32 +133,42 @@
     * Time: O(n)
+%0A         
 */%0A        publi
@@ -816,16 +816,28 @@
      /**
+%0A         * 
 Space: O
@@ -861,16 +861,26 @@
 me: O(n)
+%0A         
 */%0A     

refactor 724