Background
This problem statement is a part of Leetcode's learning card Arrays and Strings. Under the sub-heading Introduction to Array.
Problem Statement
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Note:
- The length of nums will be in the range [0, 10000].
- Each element nums[i] will be an integer in the range [-1000, 1000].
Solution Approach 1
- Reading the problem statement intuitive method that struck was to slice the list. And keep calculating the sum of those sliced sub-lists. When sum of the elements to the left-hand side of the element and right-hand side of the element matches. Return the index.
Problems with Approach 1
- This would result in an unoptimized solution. Slicing has its own time complexity depending on the length of the sublist. Overall complexity would have become quadratic.
Solution Approach 2
- Take a pen and paper and mathematically try observing the pattern.
- Calculate the total of all elements present in the list.
- Then compute the sum of all elements to the left-hand side of the current index. Store this sum for each element in a new list.
- Sum of right-hand side would be. right_hand_side = Total - value of element at current index - sum of left hand side elements at same index.
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = 0
result = -1
for x in range(0, len(nums)):
total += nums[x]
element_sum = 0
left_side_sum = [0] # Sum of elements to the left of value
for i in range(1, len(nums)):
element_sum += nums[i-1]
left_side_sum.append(element_sum)
for index in range(0, len(nums)):
right_side_sum = total - nums[index] - left_side_sum[index]
if right_side_sum == left_side_sum[index]:
result = index
break
return result
Learnings and Takeaways
- Time complexity - O(n), Space complexity - O(n)
- Time complexity of append - O(1)
- The first element of left_side_sum is initialized to 0 because there is no value to the left-hand side of leftmost element present in the list.
Top comments (0)