We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Pivot Index

Number: 724

Difficulty: Easy

Paid? No

Companies: Meta, IBM, Amazon, Google, Microsoft, eBay, LinkedIn, Nvidia, Bloomberg, Salesforce, Uber, TikTok, PayPal, Citigroup, Radius, Coupang

Problem Description

Given an integer array, find the pivot index where the sum of all the numbers to the left equals the sum of all the numbers to the right. If no such index exists, return -1.

Key Insights

  • Use a prefix sum strategy by first calculating the total sum of the array.
  • As you iterate over the array, maintain the sum of numbers seen so far (left sum).
  • At any index, the right sum can be derived by subtracting the left sum and the current element from total sum.
  • When left sum equals right sum, you've found the pivot index.
  • Only one pass through the array is needed, resulting in O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We start by computing the total sum of the array. Then, we use a single loop to traverse the array and maintain a running sum (left sum). For each index, the right sum is computed as total sum minus left sum minus the current element. If the left sum equals the right sum, we return the current index as the pivot index. If no index satisfies this condition, we return -1.

Code Solutions

# Python solution with line-by-line comments

def pivotIndex(nums):
    # Calculate the total sum of the array
    total_sum = sum(nums)
    
    # Initialize left sum to 0
    left_sum = 0
    
    # Iterate over each index and element in the array
    for i, num in enumerate(nums):
        # Right sum is total sum minus left sum minus the current element
        right_sum = total_sum - left_sum - num
        
        # Check if left sum equals right sum
        if left_sum == right_sum:
            return i  # Return the pivot index
        
        # Update left sum by adding the current element
        left_sum += num
    
    # No pivot index found
    return -1

# Example usage
print(pivotIndex([1,7,3,6,5,6]))  # Output: 3
← Back to All Questions