Short Python O(n) time O(1) space with Explanation


  • 5

    As we iterate through the array of numbers, we need to keep track of the sum of the values on the current number's left and its right. The following debugger trace demonstrates the values of the variables in each loop before the left == right line

    Input: [1, 7, 3, 6, 5, 6]

    1. index: 0, num: 1, left: 0, right: 27
    2. index: 1, num: 7, left: 1, right: 20
    3. index: 2, num: 3, left: 8, right: 17
    4. index: 3, num: 6, left: 11, right: 11 <-- Found!!!

    - Yangshun

    class Solution(object):
        def pivotIndex(self, nums):
            # Time: O(n)
            # Space: O(1)
            left, right = 0, sum(nums)
            for index, num in enumerate(nums):
                right -= num
                if left == right:
                    return index
                left += num
            return -1
    

  • 2
    G

    very easy to understand, thank you!


  • 0
    J
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.