I am solving this Leetcode problem: https://leetcode.com/problems/find-pivot-index/ And I came up with this solution:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int pivotIndex(int[] nums) {
        Integer result = null;
        List<Integer> right = new ArrayList<>(nums.length);
        List<Integer> left = new ArrayList<>(nums.length);
        int leftSum, rightSum;

        for (int i = 0; i < nums.length; i  ) {
            leftSum = 0;
            rightSum = 0;

            for (int j = 0; j < i; j  ) {
                left.add(nums[j]);
            }

            for (int num : left) {
                leftSum  = num;
            }

            for (int j = i   1; j < nums.length; j  ) {
                if (j > nums.length) {
                    right.add(0);
                } else {
                    right.add(nums[j]);
                }
            }

            for (int num : right) {
                rightSum  = num;
            }

            if (leftSum == rightSum) {
                result = i;
                return result;
            } else {
                result = -1;
                left.clear();
                right.clear();
            }
        }
        return result;
    }
}

But I'm getting Time Limit Exceeded... Can someone help me with some advise on how to make this run faster?
Before, I was instantiating a new ArrayList object at the start of the first for loop, so I changed their scope so that only one instantiation happens and just cleared the ArrayLists at the end of the for loop.
Same for leftSum and rightSum, I changed their scope for the whole method and just change their value to 0 at the start of the first for loop. I figured both these changed would make it faster but apparently didn't?
My code is slow somewhere else I can't detect it right now.

Any tips / good practices would be highly appreciated as someone who's trying to prepare for the first job interviews in this field :)

CodePudding user response：

Some point helps to improve your code.

1. Why do you need to create two new ArrayList? It takes time to create/push element to new sub list. You can just calculate left sum and right sum from nums[j].
2. You don't need else block. Just return -1 at the end of function. Because if you don't find any pivot i, then return -1 as request.

Code look like this.

public int pivotIndex(int[] nums) {
        for(int i = 0; i < nums.length; i  ) {
            int left_sum = 0;
            int right_sum = 0;
            for(int j = 0; j < i; j  ) left_sum  = nums[j];
            for(int j = i 1; j < nums.length; j  ) right_sum  = nums[j];
            if (left_sum == right_sum) return i;
        }
        return -1;
    }

CodePudding user response：

Try this.

There are no nested loops, so this is O(n).

public static int pivotIndex(int[] nums) {
    int length = nums.length;
    int pivot = 0, left = 0, right = IntStream.of(nums).skip(1).sum();
    for (;;) {
        if (left == right) return pivot;
        left  = nums[pivot];
        if (  pivot >= length) break;
        right -= nums[pivot];
    }
    return -1;
}

public static void main(String[] args) {
    System.out.println(pivotIndex(new int[] {2, 1, -1}));
    System.out.println(pivotIndex(new int[] {1, -1, 3}));
    System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6}));
}

output:

0
2
3