Array and String - Find Pivot Index in Go

Submission Detail

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, 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

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

My code

func pivotIndex(nums []int) int {
    length := len(nums)
    right := make([]int, length+1)
    sum := 0

    for i := length - 1; i >= 1; i-- {
        sum += nums[i]
        right[i] = sum
    }
    sum = 0
    for j := 0; j < length; j++ {
        if sum == right[j+1] {
            return j
        }
        sum += nums[j]
    }
    return -1
}

https://go.dev/play/p/wQz4MBAEGt5

• First I tried to use two pointer method, but It cannot reflect sum of rests.
• So I thought it will be better to calculate one side in advance.
• In my case, right side will be added from the first.
• After completion of loop, it will start to compare by adding left side.
• If condition will find pivot.
• If not it will return -1.

sample 10 ms submission

func pivotIndex(nums []int) int {
    if len(nums) < 2 {
        return -1
    }

    left := 0    
    right := 0
    for i := 1; i < len(nums); i++ {
        right += nums[i]
    }

    var pivot int
    for i := 0; i < len(nums); i++ {
        if left == right {
            return pivot
        }

        pivot = i + 1
        left += nums[i]
        if pivot < len(nums) {
            right -= nums[pivot]
        }
    }

    return -1
}

• This code is is not correct becuase first edge case is not correct.
• I reported to Leetcode
• Based on problem, when pivot is 0, right is 0.
• So when length is 1, return should be 0.
• But this code will output -1 when length is 1.
• First for loop will run with allocation accomulated sum to right.
• Second for loop will run until if condition matches or when reches end of array.
• based on pivot, it left will be added and right will be deducted.

Modification

func pivotIndex(nums []int) int {
    left := 0   
    right := 0
    for i := 1; i < len(nums); i++ {
        right += nums[i]
    }
    var pivot int
    for i := 0; i < len(nums); i++ {
        if left == right {
            return pivot
        }
        pivot = i + 1
        left += nums[i]
        if pivot < len(nums) {
            right -= nums[pivot]
        }
    }
    return -1
}

sample 12 ms submission

func pivotIndex(nums []int) int {
    sum, left := 0, 0
    for i := range  nums {
        sum += nums[i]
    }

    for i := range  nums {
        if left == sum - left - nums[i] {
            return i
        }
        left += nums[i]
    }

    return -1
}

• This code also add from left to right.
• Second for loop also starts from left to right.
• left will be added after checked in if condition.
• left Initial Value is 0, so if sum has 0 then return 0.

sample 14 ms submission

func pivotIndex(nums []int) int {
    var rightSum int
    for _, v := range nums {
        rightSum += v
    }

    var leftSum int
    for i, v := range nums {
        rightSum -= v
        if leftSum == rightSum {
            return i
        }
        leftSum += v
    }

    return -1
}

• This code uses range value.
• first for loop adds all values from left to right.
• Second for loop, rightSum will minus first value so that it can represent pivot 0.
• After cheking it, left will be added.

sample 16 ms submission

func pivotIndex(nums []int) int {
    sum := make([]int, len(nums) + 1)
    sum[0] = 0

    for i := 1; i <= len(nums); i++ {
        sum[i] = sum[i - 1] + nums[i - 1]
    }

    for j := 0; j < len(nums); j++ {
        if sum[j] == sum[len(sum) - 1] - sum[j] - nums[j] {
            return j
        }
    }

    return -1
}

• I don't think sum[0] allocation 0 is not needed.
• complicated version of left == left - right sum - nums[i]

sample 6000 KB submission

func pivotIndex(nums []int) int {
    n := len(nums)
    for index, _ := range nums {
        if sum(nums[0:index]) == sum(nums[index+1:n]) {
            return index
        }
    }
    return -1
}

func sum(nums []int) int {
    sum := 0
    for _, eachNum := range nums {
        sum = sum + eachNum
    }
    return sum
}

sample 6100 KB submission

func pivotIndex(nums []int) int {
    // naive solution, for each index, add all elements to left and right of it and see if equal: if so, return that index
    for i, _ := range nums {
        suml, sumr := getSums(nums, i)
        fmt.Println(i, suml, sumr)
        if suml == sumr {
            return i
        }
    }

    if sum(nums[1:]) == 0 {
        return 0
    } else if sum(nums[:len(nums)-1]) == 0 {
        return len(nums)-1
    }

    return -1
}

func getSums(nums[]int, i int) (int, int) {
    suml := 0
    sumr := 0

    for k := 0; k < i; k++ {
        suml += nums[k]
    }

    for j := i+1; j < len(nums); j++ {
        sumr += nums[j]
    } 

    return suml, sumr
}

func sum(nums []int) int {
    res := 0

    for _, v := range nums {
        res += v
    }

    return res
}

sample 6400 KB submission

func pivotIndex(nums []int) int {

    sum := 0
    for _, v := range nums {
        sum += v
    }

    left := 0
    for i := 0; i < len(nums); i++ {
        if left == sum-nums[i] {
            return i
        }
        left += nums[i]
        sum = sum - nums[i]
    }

    return -1
}

• This is simple code.
• First for loop adds from left to right.
• If condition in second for loop will checks from pivot 0.
• after if condition, left will add from left, and sum will be realized about if condition.