2
\$\begingroup\$

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

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

5 Answers 5

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I add some validation when checking equals @Heslacher . \$\endgroup\$ Jan 21, 2016 at 15:00
4
\$\begingroup\$

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);
 }
\$\endgroup\$
5
  • \$\begingroup\$ O(nln(n)) is too expensive :p \$\endgroup\$ Jan 22, 2016 at 12:37
  • \$\begingroup\$ Yep but is better than op's though. And also I gave a O(n) (on average) solution ;). \$\endgroup\$
    – MAG
    Jan 22, 2016 at 12:41
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Jan 22, 2016 at 12:43
  • \$\begingroup\$ '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. \$\endgroup\$
    – CiaPan
    Jan 23, 2016 at 20:37
  • \$\begingroup\$ Oops yes you are right I misread the definition. I just edited the answer accordingly. Thanks. \$\endgroup\$
    – MAG
    Jan 24, 2016 at 7:19
3
\$\begingroup\$
  • 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
\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$
    – MAG
    Jan 24, 2016 at 9:21
2
\$\begingroup\$

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;
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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