O(1) space, O(n) time Java w/ explanation

  • 0

    You want to keep track of the total running sum on the left side and the right side. You start by summing over the total sum. Then, subtract the left pointer from the right sum. Check for equality and return if so. Else increase the left sum and keep going until the array ends.

    public int pivotIndex(int[] nums) {
        if(nums.length == 0) return -1;
        int lSum = 0;
        int rSum = 0;
        int prev = 0;
        for(int num : nums) rSum += num;
        int i = 0;
        while(i < nums.length){
            prev = nums[i];
            rSum -= prev;
            if(lSum == rSum) return i;
            lSum += prev;
        return -1;

Log in to reply

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