Issue
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 :)
Solution
For anyone curious, I ended up creating another solution to this.
class Solution {
public int pivotIndex(int[] nums) {
int leftSum = 0, sum = Arrays.stream(nums).sum();
for (int i = 0; i < nums.length; i++) {
if (i != 0) {
leftSum += nums[i - 1];
}
if (leftSum == sum - leftSum - nums[i]) {
return i;
}
}
return -1;
}
}
For me is easier to understand than the other answers.
Answered By - Santiagolp Answer Checked By - Robin (PHPFixing Admin)
0 Comments:
Post a Comment
Note: Only a member of this blog may post a comment.