# Array is Balanced Array or Not

balanced array is defined to be an array where for every value n in the array, -n also is in the array.

• {-2, 3, 2, -3} is a balanced array.
• So is {-2, 2, 2, 2}. But {-5, 2, -2} is not because 5 is not in the array.

I wrote the following class BalancedArray which satisfied above condition.

public class BalancedArray {
public static void main(String args[]) {
System.out.println("The result is: " + isBalanced(new int[]{-2, 3, 2, -3}));
}
public static boolean isBalanced(int[] a){
boolean status = false;
for(int i = 0; i < a.length; i++) {
if(a[i] > 0) {
for(int j = i+1; j < a.length; j++) {
if(a[i] == Math.abs(a[j])) {
status  =  true;

}
}

} else if(a[i] < 0) {
for(int k = i+1; k < a.length; k++) {
if(Math.abs(a[i]) == a[k]) {
status = true;

}
}

}
System.out.println(status);
if(status) {
status= true;
} else {
status  = false;
break;
}
}

return status;
}
}


Is this proper way to check Balanced array or I am missing some conditions to check in array??

• This isn't doing what you assume. Passing an array { 2 , 2 } will result in true Jan 21, 2016 at 14:43
• ohh, i am missing those small conditions here @Heslacher Jan 21, 2016 at 14:48
• I have rolled back the last edit. Please see what you may and may not do after receiving answers. Jan 21, 2016 at 15:01
• ohh! i have forget the rules and regulation of Code Review. @Heslacher Jan 21, 2016 at 15:06
• What about value 0 – is it self-balancing or does it need another 0 to satisfy 0==-0...? Jan 21, 2016 at 16:40

This isn't doing what you assume. Passing an array { 2 , 2 } will result in true. This is because in the inner loops you don't check if the values are "oposite" meaning having a value > 0 in the outer loop you don't check if value < 0 in the inner loop.

The if condition

  if(status) {
status= true;
} else {
status  = false;
break;
}


doesn't buy you anything but adds noise to the code. Simply write

if (!status) {
break;
}


because there is no need to set status to true if thats the value anyway.

• I add some validation when checking equals @Heslacher . Jan 21, 2016 at 15:00

An alternative way could be using a map, the average lookup time should be O(1) so this algorithm would be O(n) on average.

public static boolean isBalanced(int[] a)
{
Map<Integer, Integer> map = new HashMap<>();
for(int number : a)
{
int key = Math.abs(number);
Integer value = map.get(key);

if(value == null)
map.put(key, number);
else if (value != number)
map.put(key, 0);
}
for (int v : map.values())
{
if(v != 0) return false;
}

return true;
}


A more readable version in java 8 ( Autoboxing and unboxing may hurt the performance a lot thought.)

 public static boolean isBalanced(int[] a)
{

Map<Integer, Integer> map = Arrays.stream(a)
.boxed()
.collect(Collectors.toMap(
Math::abs,
Function.identity(),
(x, y) -> x.equals(y)? x: 0 )
);
return map.values()
.stream()
.allMatch(p -> p == 0);
}

• O(nln(n)) is too expensive :p Jan 22, 2016 at 12:37
• Yep but is better than op's though. And also I gave a O(n) (on average) solution ;).
– MAG
Jan 22, 2016 at 12:41
• Oh sorry I just noticed that I copied your solution :(. It was brilliant anyway. Good job. You should give it a nice header like The O(n) solution or something :p Jan 22, 2016 at 12:43
• 'Note that for it to be balanced the number of elements must be even' — that's not true. The problem requires that 'for every value n in the array, -n also is in the array', but it does not require for every duplicated n to contain a separate -n; array {1, -1, -1} perfectly satisfies the condition: for 1 it contains -1, for -1 it contains 1. Jan 23, 2016 at 20:37
• Oops yes you are right I misread the definition. I just edited the answer accordingly. Thanks.
– MAG
Jan 24, 2016 at 7:19
• Your boolean status is outside the loop and will remain true once set to true for any value that is balanced in the array so {2, 3, -2} also returns true from isBalanced since it is already set to true when iterating over the rest of the array for 2
• Also you don't need separate if conditions and loops for a[i] > 0 and a[i] < 0. You can use a single inner loop and check a[i] + a[k] == 0
• You can also get rid of the if else that checks the status at the end by having loop condition as i < a.length && status
• a[i] + a[k] == 0 could give a undesired result due to overflow, for example Integer.MIN_VALUE + Integer.MIN_VALUE is equal to 0
– MAG
Jan 24, 2016 at 9:21

The algorithm may have a square time complexity in the worst case. To make the job faster just sort the array with respect to absolute values; then perform a linear scan for groups of items with equal absolute value and test each group during the scan for the presence of 'minus the first item of a group'.

For example the array {-2, 3, 2, -3} might become {-2, 2, 3, -3}; the scan would then detect a group starting with -2, then find 2 equal -(-2) in this group; and similary item -3 which is 'minus the first item' for the group starting with 3.

On the other hand {-5, 2, -2} will become {2, -2, -5} or {-2, 2, -5} and the second group will fail the test, as it starts with -5 but it doesn't contain 5.

Here's a possible implementation of the scanning loop to detect groups and verify them:

    // ... once the array is sorted with respect to absolute values

boolean groupDone = false;

for(int i = 1; i < a.length; i++) {
if (Math.abs(a[i]) == groupAbs) { // same group?
groupDone = true;
}
} else {                           // a new group
if (!groupDone)    // test the previous group
break;         // failed - return the answer

groupLeader = a[i];    // the new group starts here
groupDone = false;
}
}
// on normal exit of the loop, groupDone contains a status
// of the last group (and all former groups are OK)

return groupDone;


May be checking the sum of two values equals to zero may be the better solution for the Balanced array.

public class BalancedArray {

public static void main(String args[]) {
System.out.println("The result is: " + isBalanced(new int[]{-2, 3, 2, -3}));
}

public static boolean isBalanced(int[] a) {
boolean status = false;
for (int i = 0; i < a.length; i++) {
for(int j = 0; j < a.length; j++) {
if(a[i] + a[j] == 0) {
status = true;
break;
} else {
status = false;
}

}
if(!status) {
status =  false;
break;
}

}

return status;
}
}


If sum equals zero, break the loop and continue to next increment. Than, check for every status. If status is false, exit the loop and show false.