Knowledge Guide
Home › DSA › Company Practice

easy Find Pivot Index

Problem Statement

Given an integer array nums, determine the pivot index of this array.

The pivot index divides the array in such a way that the sum of the numbers on its left side is exactly equal to the sum of the numbers on its right side.

If the index is at the beginning, the sum to its left is considered zero, similarly for an index at the end.

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

Examples

Try it yourself

Try solving this question here:

✅ Solution Find Pivot Index

Problem Statement

Given an integer array nums, determine the pivot index of this array.

The pivot index divides the array in such a way that the sum of the numbers on its left side is exactly equal to the sum of the numbers on its right side.

If the index is at the beginning, the sum to its left is considered zero, similarly for an index at the end.

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

Examples

  • Example 1:

    • Input: [1, 2, 3, 4, 3, 2, 1]
    • Expected Output: 3
    • Justification: The sum of the numbers to the left of index 3 (1 + 2 + 3) is 6, and the sum to its right (3 + 2 + 1) is also 6.

  • Example 2:

    • Input: [2, 1, 3]
    • Expected Output: -1
    • Justification: There is no pivot index that exists in the given array.

  • Example 3:

    • Input: [1, 100, 50, -51, 1, 1]
    • Expected Output: 1
    • Justification: The sum to the left of index 1 is 1, and the sum to its right (50 + (-51) + 1 + 1) is 1.

Solution

To solve this problem, we'll employ a two-step approach to ensure efficiency and simplicity. Initially, we calculate the total sum of all array elements. Knowing the total, we can iterate through the array, maintaining a running sum of elements to the left of the current index. At any point, if the left sum is equal to the total minus the left sum minus the current element, we've found our pivot index. This method is effective because it only requires a single pass through the array after calculating the total sum, making it efficient in terms of both time and space.

The reason this approach is particularly appealing is its simplicity and the fact that it leverages the arithmetic property of sums. This allows for quick determination of the pivot index without needing complex data structures or multiple passes through the array, making it an ideal choice for this problem.

Step-by-step algorithm:

  • Calculate the total sum of the array elements.
  • Initialize a variable to keep track of the sum of elements to the left of the current index (leftSum) and set it to 0.
  • Iterate through the array:
    • At each index, check if leftSum is equal to the total sum minus leftSum minus the current element. If true, return the current index as the pivot index.
    • Otherwise, add the current element to leftSum and continue.
  • If no pivot index is found during the iteration, return -1.

Algorithm Walkthrough

Using the input [1, 2, 3, 4, 3, 2, 1]:

Step 1: Calculate the Total Sum of the Array

  1. Initialize the totalSum variable to 0.
  2. Add each element in the array to totalSum:
    • After adding 1, totalSum is 1.
    • After adding 2, totalSum is 3.
    • After adding 3, totalSum is 6.
    • After adding 4, totalSum is 10.
    • After adding the second 3, totalSum is 13.
    • After adding the second 2, totalSum is 15.
    • After adding the second 1, totalSum is 16.

Step 2: Iterate Through the Array to Find the Pivot Index

  1. Initialize the leftSum variable to 0.
  2. Iterate through the array, calculating the leftSum and comparing it with the sum of elements to the right of the current index to find the pivot index.

Iteration 1: Index 0 ([1])

  • leftSum is 0.
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 0 - 1 = 15.
  • The sums are not equal, so continue.

Iteration 2: Index 1 ([1, 2])

  • Update leftSum to 1 (0 + 1).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 1 - 2 = 13.
  • The sums are not equal, so continue.

Iteration 3: Index 2 ([1, 2, 3])

  • Update leftSum to 3 (1 + 2).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 3 - 3 = 10.
  • The sums are not equal, so continue.

Iteration 4: Index 3 ([1, 2, 3, 4])

  • Update leftSum to 6 (3 + 3).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 6 - 4 = 6.
  • The sums are equal, which means we've found the pivot index at 3.

Final Result:

The pivot index for the array [1, 2, 3, 4, 3, 2, 1] is 3, as the sum of the numbers to the left of index 3 is equal to the sum of the numbers to its right, both summing to 6.

Image
Image

Code

java
public class Solution {

  // Method to find the pivot index
  public int pivotIndex(int[] nums) {
    int totalSum = 0, leftSum = 0;
    // Calculate total sum of the array
    for (int num : nums) {
      totalSum += num;
    }
    // Iterate through the array to find pivot index
    for (int i = 0; i < nums.length; i++) {
      if (leftSum == totalSum - leftSum - nums[i]) {
        return i; // Pivot index found
      }
      leftSum += nums[i];
    }
    return -1; // No pivot index found
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    System.out.println(solution.pivotIndex(new int[] { 1, 2, 3, 4, 3, 2, 1 })); // Example 1
    System.out.println(solution.pivotIndex(new int[] { 2, 1, 3 })); // Example 2
    System.out.println(
      solution.pivotIndex(new int[] { 1, 100, 50, -51, 1, 1 })
    ); // Example 3
  }
}

Complexity Analysis

Time Complexity

The time complexity for the algorithm is , where (n) is the number of elements in the input array. This efficiency is due to the algorithm requiring a single pass to calculate the total sum and another pass to find the pivot index, making the operations linear in time relative to the size of the input.

Space Complexity

The space complexity of the algorithm is . This is because the amount of extra space required does not scale with the size of the input array.

🤖 Don't fully get this? Learn it with Claude

Stuck on Find Pivot Index? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Find Pivot Index** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Find Pivot Index** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Find Pivot Index**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Find Pivot Index**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Add BinaryToeplitz Matrix →