algoadvance

1. Find Pivot Index

Given an array of integers nums, write a method that returns the “pivot” index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

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

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation: 
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

• The length of nums will be in the range [0, 10^4].
• The elements of nums will be in the range [-10^4, 10^4].

Clarifying Questions

1. Can nums be empty?
2. Can there be multiple pivot indices?

Strategy

1. Calculate the total sum of the array.
2. Initialize left_sum to 0.
3. Iterate through the array while calculating the right sum as total_sum - left_sum - nums[i].
4. If left_sum equals the right sum at any index i, return i.
5. Update left_sum by adding the value of the current element nums[i].
6. If no pivot index is found, return -1.

Code

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0

    for i, num in enumerate(nums):
        right_sum = total_sum - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num

    return -1

Time Complexity

• The time complexity of this approach is O(n) where n is the length of the array. This is because we traverse the array only once.
• The space complexity is O(1) as we are using only a fixed amount of extra space for variables irrespective of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?