3
\$\begingroup\$
  • Task: Find the balance point of an array; return the index that if you break the array into left and right at that point will create the same sum on both sides.
    e.g: given the array [2, 4, 5, 1, -2, 7, 2, 1, 4]
    returned value should be: 3
    left: 2, 4, 5, 1 = 12
    right: -2, 7, 2, 1, 4 = 12
public static arrayBalance(input?: number[]): any {
    let sum = 0;
    for(let i=0; i<input.length; i++) {
        let cur = input[i];
        sum += cur;
    }

    let mid = sum / 2;
    let sum2 = 0;
    let ret = 0;
    while(sum2 < mid && ret < input.length) {
        sum2 += input[ret];
        ret++;
    }

    return sum2 == mid ? (ret - 1) : -1;
}

Time complexity: \$O(2n)\$,
Space complexity: \$O(1)\$


Am I right regarding the complexities?
Do you have different implementation suggestions?

\$\endgroup\$
  • \$\begingroup\$ Downvoter, care to explain? \$\endgroup\$ – Eli Livshitz Nov 14 '19 at 17:23
  • 3
    \$\begingroup\$ Did you write this code? What should we review? \$\endgroup\$ – πάντα ῥεῖ Nov 14 '19 at 17:26
  • 2
    \$\begingroup\$ Please post 1 project at a time (unless the tasks completed are done so in a highly similar fashion perhaps, this does not apply). For a guide on posting good questions, see our relevant FAQ. \$\endgroup\$ – Mast Nov 14 '19 at 17:43
  • 1
    \$\begingroup\$ I think this should be posted as two independent questions (I haven't downvoted, but will vote to put your question on hold so you can do that in peace). \$\endgroup\$ – Toby Speight Nov 14 '19 at 17:43
  • \$\begingroup\$ Thank you for the feedback, I've broke it down into separate question: codereview.stackexchange.com/questions/232399/… @πάνταῥεῖ- yes I've wrote it. I'd be happy to get a code review and feedback. \$\endgroup\$ – Eli Livshitz Nov 14 '19 at 18:06
3
\$\begingroup\$

First, a suggestion on the interface: use null to represent no match rather than -1, since that makes it easier to force the caller to check for a no-solution case (i.e. if they try to use the unchecked return of this function as an index, a -1 will only fail at runtime, whereas null will fail at transpile time).

function arrayBalance(input: number[]): number | null {

In reading over the code I got confused by the variable names -- mid isn't actually a midpoint, it's the expected sum of each half. Between all of the variables being declared with let rather than const and the uninformative names (why is there sum and sum2?), it's hard to even tell at a glance which values are being recalculated and which are constants.

Instead of taking six lines of code to find the "half-sum" that we want each side of the "split" to have, let's just do it in one (brevity is the soul of wit, and this kind of thing is exactly what the reduce function is for), and declare it as const since it's not going to change for the rest of the function once we've computed it:

const halfSum = input.reduce((a, b) => a + b) / 2;

From here, all we need to do is find out how many array elements we need to total up to equal halfSum.

Here's how I might write the rest, signifying the running total of the "left" side of the array as leftSum and doing a simple for loop over the array indices:

let leftSum = 0;
for (let i = 0; i < input.length; i++)
{
    leftSum += input[i];
    if (leftSum == halfSum)
        return i;
}
return null;

As we iterate through i we build a sum of everything to the left of i (leftSum). Our goal is to make leftSum equal halfSum. If no solution is found within the loop we return null.

It's tempting to use inequality comparisons to try to optimize the no-solution case, but consider cases where the input array has lots of negative numbers distributed randomly! halfSum could be negative or zero, and leftSum could go up and then down and then up and then down again as you increment i, so unless you've gone through the entire array you can't ever be certain that a solution does not exist.

Note also that it's possible for there to be multiple valid solutions; this implementation will always return the lowest one in that instance, but you could write a version of this function that always goes through the entire array and returns another array of all the solutions it found.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.