Скачать или смотреть 🚀 Find the Pivot Index in an Array Efficiently! 🔥

🔹 Understanding the Problem:

In this problem, we are given an array of integers, and we need to find the pivot index. The pivot index is the index where the sum of all numbers on the left is equal to the sum of all numbers on the right.

📌 Key Points to Remember:

The leftmost element has no elements on the left, so its left sum is 0.
The rightmost element has no elements on the right, so its right sum is 0.
We need to return the leftmost pivot index if there are multiple valid ones.
If no pivot index exists, return -1.

🚀 Efficient Approach (O(n) Time Complexity)

We can solve this problem efficiently in O(n) time using a single loop instead of using nested loops (which would be O(n²) and inefficient).

📌 Step-by-Step Explanation of the Algorithm:

✅ Step 1: Calculate the total_sum of all elements in the array.

Since the pivot index divides the array into two parts, knowing the total sum helps us compute the right sum dynamically.

✅ Step 2: Initialize left_sum as 0.

The left_sum keeps track of the sum of elements before the current index as we iterate through the array.

✅ Step 3: Iterate Through the Array

For each index i, we check whether the left sum is equal to the right sum using the formula:

\text{left_sum} == \text{total_sum} - \text{left_sum} - \text{nums}[i]

If this condition holds true, we return i as the pivot index.

✅ Step 4: Update left_sum

After checking the condition, we update left_sum by adding nums[i] so that it reflects the correct sum for the next iteration.

✅ Step 5: If No Pivot Index Found, Return -1

📌 Example Walkthroughs

Example 1:

🔹 Input: nums = [1,7,3,6,5,6]
🔹 Calculations:

total_sum = 1 + 7 + 3 + 6 + 5 + 6 = 28

Index Left Sum Right Sum Calculation (total_sum - left_sum - num) Condition Met?
0 0 28 - 0 - 1 = 27 ❌ No
1 1 28 - 1 - 7 = 20 ❌ No
2 8 28 - 8 - 3 = 17 ❌ No
3 11 28 - 11 - 6 = 11 ✅ Yes, return 3

🔹 Output: 3

Example 2:

🔹 Input: nums = [1,2,3]
🔹 Calculations:

total_sum = 1 + 2 + 3 = 6

Index Left Sum Right Sum Calculation (total_sum - left_sum - num) Condition Met?
0 0 6 - 0 - 1 = 5 ❌ No
1 1 6 - 1 - 2 = 3 ❌ No
2 3 6 - 3 - 3 = 0 ❌ No

🔹 Output: -1 (No pivot index found)

Example 3:

🔹 Input: nums = [2,1,-1]

🔹 Calculations:

total_sum = 2 + 1 + (-1) = 2

Index Left Sum Right Sum Calculation (total_sum - left_sum - num) Condition Met?
0 0 2 - 0 - 2 = 0 ✅ Yes, return 0
🔹 Output: 0

📌 Python Code Implementation

class Solution:
def pivotIndex(self, 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

Example usage:

sol = Solution()
print(sol.pivotIndex([1,7,3,6,5,6])) # Output: 3
print(sol.pivotIndex([1,2,3])) # Output: -1
print(sol.pivotIndex([2,1,-1])) # Output: 0

🛠 Complexity Analysis:

✅ Time Complexity: O(n) – We iterate through the array only once.
✅ Space Complexity: O(1) – We use only two extra variables (total_sum and left_sum).

💡 Why This Approach Works Best?

✔ Uses only one loop (efficient).
✔ No extra space required.
✔ Simple and intuitive logic.

🚀 This is the best way to solve the pivot index problem efficiently! 🚀