724. find pivot index

Finding the pivot index of an array is a common problem in computer science and can be solved in various ways. One method is to iterate through the array, keeping track of the total sum of all elements to the left and right of the current index. When the sum of elements to the left is equal to the sum of elements to the right, the current index is the pivot index.

In this article, we will discuss a specific algorithm, the ” 724. Find Pivot Index ” algorithm, which can be used to solve this problem in an efficient manner.

The 724. Find Pivot Index algorithm is a two-pass algorithm that first calculates the total sum of all elements in the array and then iterates through the array again, keeping track of the sum of elements to the left of the current index. The algorithm then compares the sum of elements to the left to the total sum minus the sum of elements to the left and the value at the current index. If these two values are equal, the current index is the pivot index.

The algorithm has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for arrays of any size.

Here is an example of how the 724. Find Pivot Index algorithm can be implemented in Python:

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total_sum - left_sum - num:
            return i
        left_sum += num
    return -1

In the example above, the function takes in an array nums as its input and returns the pivot index if one exists, and -1 if no pivot index is found. The function first calculates the total sum of all elements in the array using the built-in sum() function. It then iterates through the array, keeping track of the sum of elements to the left of the current index. If the sum of elements to the left is equal to the total sum minus the sum of elements to the left and the value at the current index, the current index is returned as the pivot index.

In conclusion, the 724. Find Pivot Index algorithm is a simple and efficient solution for finding the pivot index of an array. It has a time complexity of O(n) and a space complexity of O(1), making it suitable for arrays of any size.

To calculate the pivot index of an array of integers, we need to iterate through the array and check if the sum of all elements to the left of the current index is equal to the sum of all elements to the right of the current index. The pivot index is the index where this condition is met. It is important to note that if the current index is on the left edge of the array, then the left sum is 0 because there are no elements to the left and the same applies to the right edge of the array. The function should return the leftmost pivot index that satisfies this condition. If no such index exists, the function should 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:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

Solutions

Python3

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        s, presum = sum(nums), 0
        for i, v in enumerate(nums):
            if (presum << 1) == s - v:
                return i
            presum += v
        return -1
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        l, r = 0, sum(nums)
        for i, v in enumerate(nums):
            r -= v
            if l == r:
                return i
            l += v
        return -1

Java

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length, s = 0;
        for (int e : nums) {
            s += e;
        }
        int presum = 0;
        for (int i = 0; i < n; ++i) {
            // presum == sums - nums[i] - presum
            if (presum << 1 == s - nums[i]) {
                return i;
            }
            presum += nums[i];
        }
        return -1;
    }
}
class Solution {
    public int pivotIndex(int[] nums) {
        int l = 0, r = 0;
        for (int v : nums) {
            r += v;
        }
        for (int i = 0; i < nums.length; ++i) {
            r -= nums[i];
            if (l == r) {
                return i;
            }
            l += nums[i];
        }
        return -1;
    }
}

TypeScript

function pivotIndex(nums: number[]): number {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    for (let i = 0; i < nums.length; ++i) {
        r -= nums[i];
        if (l == r) {
            return i;
        }
        l += nums[i];
    }
    return -1;
}

C++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int s = 0;
        for (int e : nums)
            s += e;
        int presum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (presum * 2 == s - nums[i])
                return i;
            presum += nums[i];
        }
        return -1;
    }
};
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int l = 0, r = 0;
        for (int& v : nums) r += v;
        for (int i = 0; i < nums.size(); ++i)
        {
            r -= nums[i];
            if (l == r) return i;
            l += nums[i];
        }
        return -1;
    }
};

Go

func pivotIndex(nums []int) int {
	s := 0
	for _, e := range nums {
		s += e
	}
	presum := 0
	for i, e := range nums {
		if presum<<1 == s-e {
			return i
		}
		presum += e
	}
	return -1
}
func pivotIndex(nums []int) int {
	l, r := 0, 0
	for _, v := range nums {
		r += v
	}
	for i, v := range nums {
		r -= v
		if l == r {
			return i
		}
		l += v
	}
	return -1
}

Leave a Reply