PIVOT INDEX JAVA PROGRAM

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation: The pivot index is 3. Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 Right sum = nums[4] + nums[5] = 5 + 6 = 11

To find the pivot index in an array, we need to find an index such that the sum of elements to the left of the index is equal to the sum of elements to the right of the index. Here’s the Java program to find the pivot index with the best time and space complexity:

public class PivotIndex {
    public static int pivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 7, 3, 6, 5, 6};
        int result = pivotIndex(nums);
        System.out.println(result);
    }
}

Explanation:

• We first calculate the total sum of all elements in the array.
• Then, we iterate through the array and maintain a variable leftSum that stores the sum of elements to the left of the current index.
• At each index, we check if leftSum is equal to totalSum - leftSum - nums[i]. If it is, we return the current index as the pivot index.
• If no pivot index is found, we return -1.
• The time complexity of this program is O(n), where n is the number of elements in the array, as we iterate through the array twice.
• The space complexity is O(1), as we use only a constant amount of extra space regardless of the input size.