Find Pivot Index (Leetcode 724)
Problem Link: https://leetcode.com/problems/find-pivot-index/
1st Approach (Time: O(N) and Space: O(N))
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
n=len(nums)
lans=[]
rans=[]
s=0
for i in nums:
s=s+i
lans.append(s)
print(lans)
s=0
ans=-1
for i in range(n-1,-1,-1):
if(i==n-1):
if(lans[i-1]==0):
ans=i
elif(i==0):
if(s==0):
ans=i
else:
if(s==lans[i-1]):
ans=i
s=s+nums[i]
return ans
Optimal Approach (Time: O(N) and Space: O(1))
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
totalSum=sum(nums)
leftSum=0
for i in range(len(nums)):
rightSum=totalSum-leftSum-nums[i]
if(leftSum==rightSum):
return i
leftSum=leftSum+nums[i]
Last updated