724. Find Pivot Index
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 46.0%
Problem Breakdown
The problem requires finding the pivot index in an array of integers. The pivot index is defined as the point where the sum of elements on its left is equal to the sum of elements on its right. If no such index exists, return -1. The input is a list of integers, and the output is an integer representing the pivot index or -1 if none exists. Edge cases include arrays with negative numbers, single-element arrays, and arrays where no pivot index can be found.
Intuition
A brute-force approach would involve iterating through each element in the array and calculating the sum of elements to its left and right for every possible pivot index. This approach has a time complexity of O(n^2) because for each element, we are summing up elements on both sides.
The key insight is that if we know the total sum of the array, we can calculate the right sum by subtracting the current element and the left sum from this total sum. This reduces the problem to a single pass through the array, making it more efficient.
Approach
- Calculate the total sum of the array.
- Initialize a variable
left_sumto 0. - Iterate through each element in the array:
- Calculate the right sum by subtracting the current element and
left_sumfrom the total sum. - If
left_sumequals the right sum, return the current index as the pivot index. - Update
left_sumby adding the current element to it.
- Calculate the right sum by subtracting the current element and
- If no pivot index is found after iterating through the array, return -1.
Complexity Analysis
- Time Complexity: O(n) because we make a single pass through the array to calculate the total sum and another pass to find the pivot index.
- Space Complexity: O(1) as we only use a few extra variables regardless of the input size.
Solution
def pivotIndex(nums):
total_sum = sum(nums)
left_sum = 0
for i in range(len(nums)):
right_sum = total_sum - nums[i] - left_sum
if left_sum == right_sum:
return i
left_sum += nums[i]
return -1
Edge Cases Handled
- Single-element array: The algorithm correctly handles arrays with a single element by returning 0 as the pivot index since there are no elements to the left or right.
- Arrays with negative numbers: The algorithm works correctly with negative numbers because it uses subtraction and addition to calculate sums.
- No pivot index exists: If no pivot index is found, the function returns -1 as specified.