Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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??

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

From comment to answer

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.

share|improve this answer
    
I add some validation when checking equals @Heslacher . – user3789184 Jan 21 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);
 }
share|improve this answer
    
O(nln(n)) is too expensive :p – Bruno Costa Jan 22 at 12:37
    
Yep but is better than op's though. And also I gave a O(n) (on average) solution ;). – MAG Jan 22 at 12:41
1  
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 – Bruno Costa Jan 22 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. – CiaPan Jan 23 at 20:37
    
Oops yes you are right I misread the definition. I just edited the answer accordingly. Thanks. – MAG Jan 24 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
share|improve this answer
    
+1 good point about status staying true. I missed that – Heslacher Jan 21 at 15:11
    
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 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

    int groupLeader = a[0];
    int groupAbs = Math.abs(groupLeader);
    boolean groupDone = false;

    for(int i = 1; i < a.length; i++) {
        if (Math.abs(a[i]) == groupAbs) { // same group?
            if (a[i] == -groupLeader) {
                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
            groupAbs = Math.abs(groupLeader);
            groupDone = false;
        }
    }
    // on normal exit of the loop, groupDone contains a status
    // of the last group (and all former groups are OK)

    return groupDone;
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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